Vor gut fünf Jahren ist hier ein Code eingestellt und das recht kurzlebige Thema Beitrag "ATtiny2313 berechnet π auf 4000 Stellen" gestartet worden, wie man mit einem 8-Bit AVR-Controller bis zu 4000 "hex digits" (hexadezimale Nachkommastellen) von PI nach dem Algorithmus von Bailey-Borwein-Plouffe berechnen kann. Einen vergleichbaren Algorithmus zur Berechnung von Dezimalstellen von PI scheint es nicht zu geben, so dass man einen nachgeschalteten Algorithmus laufen lassen müßte, um "hex digits in "dezimale Nachkommastellen umzuwandeln, wenn man zur Zahl Pi nicht nur "hex cigits" berechnen möchte, sondern die Zahl mit echten Dezimalstellen darstellen möchte. Seit der Code hier 2012 gepostet wurde, scheint sich hier niemand mit dem Number-Crunching von Pi befaßt zu haben, insbesondere scheint sich niemand die Mühe gemacht zu haben, die "hex digits", die man auf 8-Bit Controllern berechnen kann, in dezimale Nachkommastellen von Pi zu konvertieren. Mich würde das mal interessieren: Wieviele Dezimalstellen (also nicht "hex digits,sondern "echte Dezimalstellen) kann man beispielsweise auf einem Atmega328 (Arduino UNO) berechnen und ausgeben? Als "hex dugits" sind 4000 Stellen möglich, wie vor fünf Jahren hier gezeigt. Aber wieviele Dezimalstellen kann man bekommen? Und wie funktioniert die Konvertierung von "hex digits" in dezimale Nachkommastellen überhaupt? Das ist vor fünf Jahren nicht mal ansatzweise diskutiert worden und es scheint seitdem auch niemanden hier interessiert zu haben. Mich würde es interessieren. Wen sonst noch?
:
Verschoben durch Moderator
Jürgen S. schrieb: > Einen vergleichbaren Algorithmus zur Berechnung von Dezimalstellen von > PI scheint es nicht zu geben, Was aktuelle Forschung angeht bin ich nicht auf dem laufenden. Zumindest war das Ziel damals auch, entsprechende Formeln für Basen zu finden, die keine Potenz von 2 sind. Ob und falls ja, inwieweit das gelungen ist, weiß ich wie gesagt nicht. > Mich würde das mal interessieren: Wieviele Dezimalstellen (also nicht > "hex digits,sondern "echte Dezimalstellen) kann man beispielsweise auf > einem Atmega328 (Arduino UNO) berechnen und ausgeben? Die Antwort wird evtl. einfacher, wenn man sich auf den maximalen Fehler beschränkt, der ja keine Aussage über die gültigen Stellen macht. Wenn man z.B. von 1 einen beliebig kleinen Wert > 0 subtrahiert, ändern sich quasi alle Nachkommastellen obwohl der Fehler beliebig klein ist. > Als "hex digits" sind 4000 Stellen möglich, wie vor fünf Jahren hier > gezeigt. Aber wieviele Dezimalstellen kann man bekommen? Der Vorteil des Algorithmus' ist zunächst, dass man fpr B=16 die erzeugten Stellen nicht speichern muss, sie können direkt ausgegeben werden. Für B=10 ist das anders. > Und wie funktioniert die Konvertierung von "hex digits" in dezimale > Nachkommastellen überhaupt? Zunächst werden alle erzeugten Ziffern B=16 gespeichert, zur Speicherersparnis idealerweise als Nibbles gepackt in Bytes. Dann implementiert man die Umwandling, z.B. indem man alle Nachkomme-Bits von B=16 durchläuft und parallel eine Berechnung in B=10 durchführt, z.B. gepacktes BCD.
1 | B=2 B=10 |
2 | .1 .5 |
3 | .01 .25 |
4 | .001 .125 |
5 | .0001 .0625 |
6 | .00001 .03125 |
Rechts wird also immer durch 2 dividiert, und falls das entsprechende Bit in B_16 gesetzt ist, addiert man den B=16 Wert in der Dezimal-Arithmetik. Zunächst fällt auf, dass die Zahl der Nachkommastellen für B=10 gleich der Nachkommastellen für B=2 ist, was das 4-fache der Stellem für B=16 ist. Selbst in gepackter Darstellung braucht man also das 4-fahe an Speicher. Zudem ist die erwartete Laufzeit zur Umwandlung quadratisch in der Anzahl der Stellen. Praktisch wird man irgendwann die Genauigkeit nicht mehr halten können, d.h. man muss die B=10 Darstellung irgendwie runden und den Rundungsfehler mitführen. Die führenden Nullen der der B=10 Darstellung kann man zwar optimiert behandeln, für das Endergebnis (pi) gilt das aber nicht mehr. Man braucht also eine geschickte Aufteilung des Speichers (RAM), so dass Summe aus * Nachkommastellen für B=16 * Nachkommastellen für B=10 * Nachkommastellen des Ergebnisses (pi) noch ins RAM passt, und zwar so, dass der Rundungsfehler möglichst klein wird. Und wenn man will, kann man dann noch versuchen, vom Rundungsfehler auf Anzahl gültiger Stellen zu schließen wobei 0 und 9 am blödesten sind, weil sich die nächst höhere Ziffer auch ändert. > Das ist vor fünf Jahren nicht mal > ansatzweise diskutiert worden und es scheint seitdem auch niemanden hier > interessiert zu haben. Mich würde es interessieren. Wen sonst noch?
> Wieviele Dezimalstellen (also nicht "hex digits,sondern "echte > Dezimalstellen) kann man beispielsweise auf > einem Atmega328 (Arduino UNO) berechnen und ausgeben? Bist du Mathe-Lehrer? Ich frage, weil mich dieser völlig praxisferne Aufgabe an die Schule erinnert. Warum willst du das wissen? Wirst du davon schöner oder reicher? Die Umwandlung von Hexadezimal in Dezimal kann man mit einer einfachen Schleife mit beliebig großen Zahlen machen - sofern du sie von "hinten" beginnend ausgeben kannst. Ansonsten brauchst du genug RAM, um das Ergebnis zu speichern. Und davon kann man, wenn es denn unbedingt sein muss, beliebig viel anschließen.
On the computation of the n'th decimal digit of various transcendental numbers, Simon Plouffe http://www.lacim.uqam.ca/~plouffe/Simon/articlepi.html "We outline a method for computing the n'th decimal (or any other base) digit of Pi in C*n^3*log(n)^3 time and with very little memory. The computation is based on the recently discovered Bailey-Borwein-Plouffe algorithm"
Jürgen S. schrieb: > Wieviele Dezimalstellen (also nicht > "hex digits,sondern "echte Dezimalstellen) kann man beispielsweise auf > einem Atmega328 (Arduino UNO) berechnen und ausgeben? > > Als "hex dugits" sind 4000 Stellen möglich, wie vor fünf Jahren hier > gezeigt. Aber wieviele Dezimalstellen kann man bekommen? Und wie > funktioniert die Konvertierung von "hex digits" in dezimale > Nachkommastellen überhaupt? Wenn du nach der Berechnung Hex in Dez wandeln möchtest, i.e. keinen Algorithmus hast, der direkt Dezimalstellen generiert und ausgibt, ohne sie weiter zu brauchen, wirst du die Zahl zwischendurch mal abspeichern müssen. So ein ATmega328 hat 2048 Byte SRAM ...
Jürgen S. schrieb: > Mich würde das mal interessieren: Wieviele Dezimalstellen (also nicht > "hex digits,sondern "echte Dezimalstellen) kann man beispielsweise auf > einem Atmega328 (Arduino UNO) berechnen und ausgeben? Praktisch unbegrenzt viele, hinreichend Zeit und eine SD-Karte als Speichererweiterung vorausgesetzt.
Was mich diesbezüglich interessieren würde wäre eine Art Benchmark gemessen an der Aufgabe "Berechne Pi auf n-Stellen genau". Diesselbe Aufgabe für alle mögliche Mikrocontroller die da so rumschwirren... Das wäre mal einen Wettbewerb hier auf mc.net wert. Wer trimmt seinen Aufbau hin a) zur Ffähigkeit dies zu berechnen und b) wer erreicht die höchste Effizienz, also benötigte Zeit/Geschwindigkeit (=Anzahl Rechenschritte)
Warum muß es unbedingt der ATmega328 sein? Nimm nen ATmega162 und pappe 64kB SRAM dran.
Stefan U. schrieb: > Bist du Mathe-Lehrer? Ich frage, weil mich dieser völlig praxisferne > Aufgabe an die Schule erinnert. Warum willst du das wissen? Wirst du > davon schöner oder reicher? Nein, ich bin kein Mathelehrer. Und von der Lösung eines kniffligen Problems werde ich weder schön noch reich. Ich bastele- rein zu Hobbyzwecken - ganz gerne mit Arduino Atmega328 Boards, für die ich auch Programme schreibe. Das "Berechnen von PI auf viele Stellen" ist eine Aufgabe, der sich schon viele gewidmet haben, Mathematiker wie auch Programmierer. Letztens ist mir hier im Forum der Code für 4000 Stellen von PI aufgefallen und ich habe ihn auf einen Arduino gepackt - und funktioniert! Erst danach habe ich entdeckt, dass der Code keine Dezimalstellen, sondern nur "hex digits" berechnet. Und dann habe ich etwas gegoogelt, und dabei etwas über den ersten vollelektronischen Universalrechner mit dem Namen "ENIAC" auf Wikipedia gefunden: https://de.wikipedia.org/wiki/ENIAC Der ENIAC hat 1949 den seinerzeitigen Weltrekord für die Berechnung von PI aufgestellt: 2037 dezimale Nachkommastellen in 70 Stunden! Dieser Rechner brachte ein Gewicht von 27 Tonnen auf die Waage und war auf einer Grundfläche von 10m x17m aufgestelt. Und seit ich von dem 1949er ENIAC-Weltrekord in der Berechnung von PI gelesen habe, geht mir die Idee durch den Kopf, ob und wie ein kleiner Atmega328 den ENIAC von 1949 bei der Berechnung von PI möglicherweise schlagen kann, und zwar möglichst gleich zweifach: Der ENIAC berechnete seinerzeit PI auf 2037 dezimale(!) Nachkommastellen genau innerhalb von 70 Stunden. Kann ein Atmega328 vielleicht sogar mehr als doppelt so viele dezimale Stellen in einem Bruchteil der Zeit errechnen und ausgeben? Seit 2012 ist klar: Es ist einem 8-Bitter möglich, mit dem Borwein-Bailey-Plouffe-Algorithmus von 1995 bis zu 4000 hex-Digits zu berechnen. Aber wieviel ist für einen Atmega328 maximal an dezimalen(!) Nachkommastellen von Pi drin? Ohne dass man eine SD-Karte zum Zwischenspeichern braucht? Und gibt es vielleicht auch noch eine andere Implementierung des Borwein-Bailey-Plouffe-Algorithmus für AVR GCC, mit dem man deutlich über die 4000 Hex-Digits hinauskommt, die der 2012 hier bereitgestellte Code maximal erzeugen kann?
Peter D. schrieb: > Warum muß es unbedingt der ATmega328 sein? > Nimm nen ATmega162 und pappe 64kB SRAM dran. Weil ich mehrere Arduino-kompatible Boards mit Atmegae328 habe. Wenn ich mehr als die 2KB RAM brauche, die ein Arduino UNO eingebaut hat, würde ich einen Arduino MEGA2560 oder einen Arduino DUE verwenden. Arduino UNO, MEGA2560 und DUE sind drei Arduino-Boards, die ich zum Basteln verfügbar habe. Ich wollte etwas Software austüfeln für die Hardware, die ich bereits hier habe, ich wollte mir zum Tüfteln mit PI keine neue Hardware extra anschaffen.
Jürgen S. schrieb: > ... ich wollte mir zum Tüfteln mit PI keine neue Hardware extra > anschaffen. Dann man los! Fange an zu tüfteln und berichte über deine Ergebnisse.
Mike B. schrieb: > Was mich diesbezüglich interessieren würde wäre eine Art Benchmark > gemessen an der Aufgabe "Berechne Pi auf n-Stellen genau". > > Diesselbe Aufgabe für alle mögliche Mikrocontroller die da so > rumschwirren... Vor einigen Wochen lief hier ein Benchmark-Thema, und in dem Thema habe ich neben den Stichworten und Verlinkungen zu Code für DHRYSTONE , WHETSTONE und LINPACK auch die Berechnung von PI erwähnt, die man als Benchmark vwerwenden könnte. Aber das hat noch weniger interessiert als DHRYSTONE, WHETSTONE und LINPACK Benchmarks. Die Arduino-IDE unterstützt neben AVR-Atmega Controllern inzwischen eine ganze Bandbreite von Mikrocontrollern, einschließlich ESP8266 und STM32. Das wäre vielleicht eher ein Thema fürdas Forum auf Arduino.cc, denn aufPlattformen, die nicht von der Arduino-IDE unterstützt werden, ist ja auch immer fraglich, ob ein bestimmter Code überhaupt direkt lauffähig ist, oder größere Änderungen erfordert. um ihn lauffähig zu machen.
Jürgen S. schrieb: > Wieviele Dezimalstellen (also nicht > "hex digits,sondern "echte Dezimalstellen) kann man beispielsweise auf > einem Atmega328 (Arduino UNO) berechnen und ausgeben? Alle.
...ich hab mal wieder viel zu kompliziert gedacht. Um in Basis B umzuwandeln genügt Multiplikation mit B und dann die VORkommastelle des Ergebnisses zu nehmen:
1 | #include <stdio.h> |
2 | #include <stdlib.h> |
3 | #include <stdbool.h> |
4 | #include <stdint.h> |
5 | |
6 | #if defined (WITH_AVRTEST)
|
7 | # include "avrtest.h"
|
8 | # undef putchar
|
9 | # define putchar(x) avrtest_putchar (x)
|
10 | #else
|
11 | # define PERF_START_CALL(x) (void) x
|
12 | # define PERF_DUMP_ALL (void) 0
|
13 | #endif // avrtest
|
14 | |
15 | // Pop 1 digit out of bytes[] and output via putchar().
|
16 | |
17 | static size_t put_digit (uint8_t *bytes, size_t n_bytes, uint8_t radix) |
18 | {
|
19 | uint8_t carry = 0; |
20 | size_t n = n_bytes; |
21 | size_t n_bytes_new = 0; |
22 | do
|
23 | {
|
24 | n--; |
25 | uint16_t accu = radix * bytes[n] + carry; |
26 | bytes[n] = (uint8_t) accu; |
27 | if (bytes[n] && !n_bytes_new) |
28 | n_bytes_new = n + 1; |
29 | carry = accu >> 8; |
30 | } while (n); |
31 | |
32 | putchar ('0' + carry); |
33 | |
34 | return n_bytes_new; |
35 | }
|
36 | |
37 | uint8_t digs256[] = |
38 | {
|
39 | 0x24, 0x3F, 0x6A, 0x88, 0x85, 0xA3, 0x08, 0xD3, |
40 | 0x13, 0x19, 0x8A, 0x2E, 0x03, 0x70, 0x73, 0x44, |
41 | 0xA4, 0x09, 0x38, 0x22, 0x29, 0x9F, 0x31, 0xD0, |
42 | 0x08, 0x2E, 0xFA, 0x98, 0xEC, 0x4E, 0x6C, 0x89, |
43 | };
|
44 | |
45 | #define BYTES digs256
|
46 | |
47 | __attribute__((noinline,noclone)) |
48 | size_t out_digits (void) |
49 | {
|
50 | uint8_t n_line = 0; |
51 | size_t n_digits = 0; |
52 | putchar ('3'); |
53 | putchar ('.'); |
54 | putchar ('\n'); |
55 | |
56 | size_t n_bytes0 = sizeof (BYTES) / sizeof (*BYTES); |
57 | for (size_t n_bytes = n_bytes0; n_bytes != 0; ) |
58 | {
|
59 | n_bytes = put_digit (BYTES, n_bytes, 10); |
60 | if (++n_line == 40) |
61 | {
|
62 | n_line = 0; |
63 | putchar ('\n'); |
64 | }
|
65 | if (++n_digits >= (size_t) (n_bytes0 * 2.408)) // log 256 / log 10 |
66 | break; |
67 | }
|
68 | putchar ('\n'); |
69 | return n_digits; |
70 | }
|
71 | |
72 | int main (void) |
73 | {
|
74 | printf ("Hex-Digits = %u\n", 2 * sizeof (BYTES) / sizeof (*BYTES)); |
75 | PERF_START_CALL (1); |
76 | size_t n_digits = out_digits(); |
77 | PERF_DUMP_ALL; |
78 | printf ("Dec-Digits = %u\n", n_digits); |
79 | return 0; |
80 | }
|
I.W. eine Schleife, die pro Durchlauf eine Ziffer zur Basis B aus bytes[] rausnuckelt und ausgibt. Weil durch die Multiplikation mit B die LSBs nach und nach 0 werden — zumindest falls B und 2 nicht teilerfremd sind, was für B=10 der Fall ist) wird auch die Anzahl zu betrachtender Bytes in bytes[] nach und nach kleiner. Ausgabe mit avrtest ist:
1 | Hex-Digits = 64 |
2 | |
3 | --- Start T1 (round 1) |
4 | 3. |
5 | 1415926535897932384626433832795028841971 |
6 | 6939937510582097494459230781640628620 |
7 | |
8 | --- Dump # 1: |
9 | Stop T1 (round 1, 0182--0186, 52582 Ticks) |
10 | Timer T1 "" (1 round): 0182--0186 |
11 | Instructions Ticks |
12 | Total: 39884 52582 |
13 | Calls (abs) in [ 1, 2] was: 1 now: 1 |
14 | Calls (rel) in [ 0, 1] was: 0 now: 0 |
15 | Stack (abs) in [04f9,04f4] was:04f9 now:04f9 |
16 | Stack (rel) in [ 0, 5] was: 0 now: 0 |
17 | |
18 | Dec-Digits = 77 |
19 | |
20 | exit status: EXIT |
21 | reason: exit 0 function called |
Es werden also 77 Dezimalen ausgegeben, was 52582 Ticks dauert. Da #Ticks ~ Ziffern^2 ist der Proportinalitätsfaktor für Dezimalstellen grob 10. Die berechneten Stellen stimmen soweit, siehe OEIS (die Ziffern sind da um 1 verrutscht, d.h. 10^-2 wird als No. -1 gelistet. Die nächsten Ziffern sind übrigens ...899... das Programm würde aber mit ...666... fortfahren, d.h. die nächste Ziffer wäre schon nicht mehr richtig. Da die Anzahl der auszugebenden Ziffern sich am Fehler orientiert, nicht an den korrekten Ziffern, ist es möglich, dass für mehr / weniger Hex-Ziffern die letzte(n) Ziffer(n) nicht mehr stimmen.
Hi ALLE schafft nur Chuck Norris :) Was mir durch den Kopf ging: Beim Berechnen der dezimalen Nachkomma-Stellen, bekomme ich 'vorne' immer mehr Nullen - Welche ich ja gar nicht im Ram halten muß. Ich muß mir doch 'nur' merken, ab der wievielten Stelle ich die berechneten Nachkomma-Ziffern dazu addieren muß. Das bis zu dieser Stelle gefundene PI müsste ich bereits ausgeben können (vll. eine Stelle weniger, falls doch ein Überlauf vorkommt) und könnte somit die Anzahl der aus dem Speicher bereits entfernten Nullen um die Anzahl der ausgegebenen Stellen verringern (und somit auch die Stelle, ab Der ich meine Nachkomma-Ziffern aufaddiere nach vorne verschieben). Bei 2k Ram sollten sich doch 'ein paar' Nachkomma-Stellen im Speicher halten lassen, bis die Länge der 'Nachkommaziffern' den möglichen Platz überschreitet - also die Nachkomma-Ziffern und die noch nicht ausgegebenen Ziffern von PI sich gegenseitig überschreiben (was wohl bei ca. der Mitte der Fall sein dürfte). Muß gleich doch Mal nach den Hex-Digits von PI suchen, klingt interessant. MfG
Jürgen S. schrieb: > Das wäre vielleicht > eher ein Thema fürdas Forum auf Arduino.cc, denn aufPlattformen, die > nicht von der Arduino-IDE unterstützt werden, ist ja auch immer > fraglich, ob ein bestimmter Code überhaupt direkt lauffähig ist, oder > größere Änderungen erfordert. um ihn lauffähig zu machen. Geht es dir um einen Algorithmus, der die Dezimalnachkommastellen berechnen kann, ohne alles zwischenzuspeichern oder geht es dir um irgendwelche Compiler- und Sprachdialekte, die ggf. ein bisschen Hirnschmalz erfordern?
Patrick J. schrieb: > ALLE schafft nur Chuck Norris :) Chuck Norris ist schon weiter. Er hat schon mehr Stellen berechnet, als ¶ überhaupt lang ist. ;-) Und er hat nordic Walking erfunden ... **hust* Gruß Jobst
Jürgen S. schrieb: > Und gibt es vielleicht auch noch eine andere Implementierung des > Borwein-Bailey-Plouffe-Algorithmus für AVR GCC, mit dem man deutlich > über die 4000 Hex-Digits hinauskommt, die der 2012 hier bereitgestellte > Code maximal erzeugen kann? Im mathematischen Sinne: ja, gibt es. Im umgangssprachlichen Sinne: nein, vermutlich nich nicht. SCNR Die Implementierung in 4000 Stellen von Pi mit ATtiny2313 ist ja ausführlichst kommentiert, auch was die Beschränkungen impliziert. Du könntest dir z.B. überlehen, wie weit du mit 32-Bit Arithmetik oder mit __uint24 kommst. Da die Beschränkung beim ATtiny2313 von der Flashgröße her kommt, ist man da auf einem größeren µC natütlich komfortabler am Werk. > Und seit ich von dem 1949er ENIAC-Weltrekord in der Berechnung von PI > gelesen habe, geht mir die Idee durch den Kopf, ob und wie ein kleiner > Atmega328 den ENIAC von 1949 bei der Berechnung von PI möglicherweise > schlagen kann, und zwar möglichst gleich zweifach: > > Der ENIAC berechnete seinerzeit PI auf 2037 dezimale(!) Nachkommastellen > genau innerhalb von 70 Stunden. > > Kann ein Atmega328 vielleicht sogar mehr als doppelt so viele dezimale > Stellen in einem Bruchteil der Zeit errechnen und ausgeben? > > Seit 2012 ist klar: Es ist einem 8-Bitter möglich, mit dem > Borwein-Bailey-Plouffe-Algorithmus von 1995 bis zu 4000 hex-Digits zu > berechnen. > Aber wieviel ist für einen Atmega328 maximal an dezimalen(!) > Nachkommastellen von Pi drin? ATmega328 hat 2 KiB RAM. Der Artikel von oben nennt einen RAM-Verbrauch von ca. 50 B (Stack, statisch), ergo locker 1900 B frei für B=256 macht 1900 · log B / log 10 also gut 4500 Ziffern in B=10. Da der Code von oben die Ziffern in-situ wandelt und die großen Ziffern zuerst rauspurzeln, braucht die Umwandlung kein extra RAM außer eben Stack (statisch) was zu vernachlässigen ist. Für 1000 Ziffern in B=16 nennt der Artikel 3 min @ 22MHz, bei quadratischer Skalierung wird das also das 15-fache an Zeit, also ca. 45 min. Die Zeit für die Konvertierung ist nicht darin enthalten und ist vermutlich merklich kleiner aber auch quadratisch. Wo die Zeit verbraten wird weiß ich nicht, aber da ein ATmega328 über MUL verfügt, dürfte die float-Arithmetik schneller werkeln.
Warum müssen es denn Dezimalstellen sein? Was ist an Hex-Stellen schlecht?
Und vor allem - wofür soll es überhaupt gut sein? Pi ist erwiesenermassen irrational und transzendent. Es sind auch schon verdammt viele Nachkommastellen berechnet worden. Wo ist denn jetzt bitte die Herausforderung, auf einem Kleinstrechenknecht mit sehr begerenzten Ressourcen x Stellen davon berechnen zu wollen? Zu zeigen, dass man auch mit wenig viel erreichen kann? Fest steht: es wird in jedem Fall nur eine rel. kleine Nachkommastellenzahl werden. 22 Billionen sollen bekannt sein - spielt es irgendeine Rolle, ob man auf einem kleinen AVR nun 4000 oder 6000 berechnen kann? Das hat nicht mal irgendeinen an den Haaren herbeigezogenen akademischen Nutzen.
Angehängte Dateien:
-
a.png
160 KB
Ich hab für den Code ausm Wiki mal einen dynamischen Call-Graph erstellt, allerdings für nur 100 Hex-Ziffern, ATmega328, mit -O2 übersetzt und an avrtest angepasst. Die meiste Zeit wird in "sigma" verbraten, wegen dem Inlining ist von den Funktionen der C-Quelle nix mehr zu sehen. Grob die Hälfte der Zeit geht auf float-Berechnungen drauf, die andere Hälfte verbraucht "sigma" selbst, vermutlich i.W. für die 16-Bit mod Arithmetik für Multiplikation und Exponentiation.
> PI mit 8-Bit Controller
Hatte erst gedacht es geht hier um einen PI-Regler stattdessen aber um
Pi :-)
H.Joachim S. schrieb: > Und vor allem - wofür soll es überhaupt gut sein? Und selbst wenn man den Sinn der Frage nicht hinterfragt - warum fragt er andere danach? Wenn es ihn interessiert, kann er es ja einfach herausfinden. Man nehme einen Arduino nano, einen C-Compiler und ein passendes Buch, z.b. das Pi-Buch von Jörg Arndt. Und los geht's. Wenn er Ergebnisse hat, kann er ja immer noch fragen, was andere davon halten.
Gab es da nicht die Monte-Carlo Methode? Wenn man die Zwischenergebnisse nicht gleich ausgibt sondern wartet bis sich z.B. die letzten 3 Ziffern für Takte x nicht mehr geändert haben. Ich meine der Speicherverbrauch war minimal. Gruß J
Axel S. schrieb: > Und selbst wenn man den Sinn der Frage nicht hinterfragt - warum fragt > er andere danach? Wenn es ihn interessiert, kann er es ja einfach > herausfinden. Ganz so einfach finde ich das nicht. Der Code zur Berechnung von 4000 hex Digits steht seit fünf Jahren hier im Forum und hatte inzwischen über 500 Downloads. Ich habe versucht herauszufinden, ob irgendjemand, auf diesem Code aufbauend oder allgemein, bereits irgendwas entwickelt hat, womit hex Digits in Dezimalstellen umgewandelt werden können, oder wenigstens Informationen hat, wie es funktioniert, aber ich konnte nichts finden und mir ist auch kein zündender Einfall gekommen, daher habe ich gefragt. Und ich danke Autor: Johann L. (gjlayde) für seine umfangreichen Ausführungen und den geposteten Beispielcode zur Konvertierung von Base-16 Dezimalstellen in Base-10 Dezimalstellen!
Johann L. schrieb: > ...ich hab mal wieder viel zu kompliziert gedacht. Um in Basis B > umzuwandeln genügt Multiplikation mit B und dann die VORkommastelle des > Ergebnisses zu nehmen: VIELEN DANK für Deine Erläuterungen und den geposteten Beispielcode! Das war SEHR HILFREICH! Und Dein Code sieht irgendwas zwischen "genial einfach" und "einfach genial" aus.Und funktioniert. Dass für die Konvertierung nicht die gesamten HEX-Digits als einzelne Bytes zwischengespeichert werden müssen, die zu Dezimalstellen konvertiert werden sollen, sondern nur ein Array mit halber Größe, hatte ich mir bereits gedacht. Aber dann war bei mir irgendwie Sense und ich bin auf keinen brauchbaren Konvertierungs-Algorithmus gekommen. Also Danke nochmals!
H.Joachim S. schrieb: >Wo ist denn jetzt bitte die Herausforderung, > auf einem Kleinstrechenknecht mit sehr begerenzten Ressourcen x Stellen davon berechnen zu wollen? Eigentlich interessierte mich nur mal, wie so ein 25 Gramm leichter Arduino UNO im Vergleich zu einem 27 Tonnen schweren ENIAC Computer von 1949 so dasteht: Kann man damit mehr Dezimalstellen von PI in weniger Zeit ausrechnen - oder nicht?Und da ein AVR GCC Programmcode für die Berechnung von 4000 HEX-Digits bereits seit Jahren vorliegt, war meine aktuelle Frage nur noch: Wie sieht es mit Dezimalstellen zur Basis-10 aus? Ist auch das auf einem kleinen AVR-Controller noch machbar, oder ist mit den Hex-Digits bereits das Ende der Fahnenstange erreicht? So wie es nach dem Beitrag von Johann L aussieht, sind die 4000 Hex-Digits noch NICHT das Ende der Fahnentange für einen Atmega328, sondern man kann durch eine Konvertierung auch Dezimalstellen bekommen, auch wenn das zusätzlichen RAM-Speicher zum temporären Zwischenspeichern von Hex-Digits vor der finalen Base-10 Konvertierung erfordert.
Na dann - frohes Schaffen. Und wenn das "Rechnegewicht" die eigentliche Herausforderung ist: Arduino-Platine weglassen, im MLF-Gehäuse dürfte der 328 im Bereich von 1g liegen, nochmal Faktor 25 gewonnnen. Halleluja.
Jürgen S. schrieb: > Eigentlich interessierte mich nur mal, wie so ein 25 Gramm leichter > Arduino UNO im Vergleich zu einem 27 Tonnen schweren ENIAC Computer von > 1949 so dasteht: Kann man damit mehr Dezimalstellen von PI in weniger > Zeit ausrechnen - oder nicht? So wie du das betreibst, ist das... > Und da ein AVR GCC Programmcode für die Berechnung von 4000 HEX-Digits > bereits seit Jahren vorliegt, ...vor allem auch ein Vergleich von Algorithmen bzw. Formeln. Auch wenn bereits ein fitter Gymnasiast die Gültigkeit der BBP-Formel nachrechnen kann, ist diese erst seit 1995 bekannt und stand den Programmierern von ENIAC nicht zur Verfügung. Vermutlich wurde eine der hinlänglich bekannten Reihenentwicklungen wie Machin verwendet. http://www.wittenberg.edu/news/2013/03_14_pi.html
1 | So while the details of the original computation for π may have |
2 | differed, given the constraints imposed by the architecture of the |
3 | ENIAC, the ENIAC's instruction mix, the mathematics used for the |
4 | computation and Reitwisener's description, I was satisfied that I had |
5 | figured out how the ENIAC had determined π which resulted in a paper |
6 | being accepted for publication. |
π/4 = 4·atan(1/5) - atan(1/239) und der Entwicklung von atan als Potenzreihe um 0. Wieviel RAM brauchtt man dazu? Ein Register für x (1/5 bzw. 1/239) ein Register für die Reihenglieder und eins für die Summe, eins für Zwischenergebnisse macht 4 Register. Bei 2 KiB RAM bleiben 512 B pro Register. Selbst wenn man es auf 3 Register schafft hat jedes nur 682 B. Wegen Rundungsfehlern etc. gehen, sagen wir mal 10 B verloren, macht höchstens 672·log 256 / log 10 = 1618 Dezimalen.
Baldrian schrieb: > Dann man los! Fange an zu tüfteln und berichte über deine Ergebnisse. Bin schon dabei! Da ich kein Mathematiker bin, habe ich mich mal nicht alleine aufs Tüfeln verlassen, sondern lieber auch nochmal gegoogelt. Und ich bin fündig geworden, offenbar auf der Webseite eines japanischen Arduinino-Programmierers, der hier ein Programm gepostet hat, das ausgehend von Hex-Digits am Ende Dezimalstellen von Pi anzeigt: http://renesasrulz.com/gadget_renesas_user_forum/f/gr-sakura---forum/4362/pi-of-1000-decimal-digits-calculation-speed Author: fujita nozomu Posted: 28 Sep 2013 7:09 Der hat offfenbar breits weniger als zwei Jahre später, nachdem hier der AVR-Code für die Berechnung von 4000 Hex-Digits von Pi gepostet worden war, mit ausdrücklichem Hinweis auf das Forum von www.mikrocontroller.net ein Arduino-Programm gepostet, das folgendes Ziel hat: Pi of 1000 decimal digits calculation speed Also ein Benchmark zur Berechnung von Pi auf eintausend Dezimalstellen( genau. Sein Code macht dabei das: Mit dem auf ww.mikrocontroller.net im Jahr 2012 geposteten Code zuerst eine gewisse Anzahl hex Digits von Pi ausrechnen, und diese hex Digits dann in Dezimalstellen konvertieren und auf Serial ausgeben. Sein Algorithmus funktioniert dabei allerdings nicht nur für 1000 Dezimalstellen von Pi, sondern auch für weniger oder mehr. Und grundlegend habe ich auch verstanden , was und wie er es macht. Sein Programm geht wie folgt vor: Er gibt vor, dass er 1000 Dezimalstellen von Pi haben möchte. Dann errechnet er, wie viele Hex-Stellen er dafür braucht. Der Faktor ist im wesentlichen 1000* (log(10)/log(2)/4) Macht 831 hex Stellen (aufgerundet). Davon muss er die Hälfte in einem Byte-Array zwischenspeichern. Macht 416 Bytes zum Zwischenspeichern (aufgerundet). Zum Schluss konvertiert er die Dezimalstellen aus den zwischengespeicherten Bytes heraus und sendet sie an die serielle Schnittstelle, so dass man sie in der Arduino.IDE auf dem seriellen Monitor sichbar gemacht bekommt. Ich habe es getestet: Der Code des Japaners, zusammen mit der Hex-Digits Berechnung aus diesem Forum funktioniert für weniger als auch für mehr als eintausend Dezimalstellen. Grenzen auf AVR: Die Dezimalstellenberechnung von Pi auf einem Arduino UNO (Atmega328) hat allerdings mehrere Grenzen: 1. Da mit dem gegebenen Algorithmus auf der AVR-GCC Plattform ein Limit bei circa 4000 Hex-Digits besteht, lassen sich auch mit längerer Rechenzeit nicht beliebig viele, sondern nur begrenzt viele Dezimalstellen von Pi errechnen. Eine weitere Grenze betrifft den limitierten RAM-Speicher: Da man die Hälfte der Hex-Digits zwischenspeichern muss, um auf Dezimalstellen zu kommen, bekommt man schon Schswierigkeiten, in einem laufenden Programm 2000 Bytes zum Zwischenspeichern von 4000 Hex-Digits verfügbar zu haben, wenn der Mikrocontroller überhaupt nur 2048 Bytes RAM hat. Also ist meine Erkenntnis bsher: Auf einem Atmega328 kann man bis zu 4000 Hex-Digits von Pi sichtbar machen, und auch bis zu 4000 (oder ein wenig mehr) an Dezimalstellen, aber 5000 Dezimalstellen von Pi sind gleich aus zwei Gründen außer Reichweite: Für 5000 Dezimalstellen von Pi müßte man deutlich mehr als 4000 Hex-Digits korrekt berechnen können, aber das gibt drAlgorithmus nicht her. Und um deutlich mehr als 4000 Hex-Digits inDezimalstellen umzuwandeln, müßte man deutlich über 2000 Bytess Zwischenspeichern können, aber das gibt das RAM eines Atmega328 nicht her. Mögliche Abhilfen zur Überwindung der Grenzen: 1. Ein geänderterAlgorithmus, der viel mehr als 4000 Hex-Digits korrekt berechnen kann. 2. Eine SD-Karte zum /paktisch unbegrenzten) Zwischenspeicherrn. Ich werde mich jedenfalls mal hinsetzen, und auf Basis des Programms-"fujita nozomu" einen Code für Arduino AVR-GCC entwickeln, der PI mit echten Dezimalstellen sichbar mahen kann. 1000, 2000, 3000 und 4000 echte Dezimalstellen(!) sollten machbar sein. Und nicht nur die 4000 Hex-Digits, die derdamals gepostete Code hergibt.
Jürgen S. schrieb: > Da man die Hälfte der Hex-Digits zwischenspeichern muss, > um auf Dezimalstellen zu kommen, bekommt man schon Schswierigkeiten, > in einem laufenden Programm 2000 Bytes zum Zwischenspeichern von > 4000 Hex-Digits verfügbar zu haben, > wenn der Mikrocontroller überhaupt nur 2048 Bytes RAM hat. Man sollte alle Hex-Ziffern speichern, welche zu berechnen ohne zu speichern ist ziemlich sinnlos... Auf einem ATmega328 ist man mit 32 KiB flash recht komfortabel unterwegs, als erstes wird mal also versuchen die 50 B Stackverbrauch beim ATtiny2313 zu drücken. Dazu übersetzt man mit -O2 nebst
1 | static float sigma (unsigned n, uint8_t j); |
2 | static float pi_n (unsigned n); |
Das static bewirkt, das aller Code — bis auf die Lib-Funktionen — in
main geilinet wird. Wegen OS_main verbraucht das Programm dann nur 27 B
Stack, was man mit nicht-Standard Mitteln noch etwas verkleinern kann.
Man kann sich auch ein Programm schreiben, dass sich "dynamisch" am
freien Speicher orientiert — abermals nicht portabel:
(1) Im Startup-Code initialisiert man das RAM mit einem Muster à la
http://rn-wissen.de/wiki/index.php?title=Speicherverbrauch_bestimmen_mit_avr-gcc#Dynamischer_RAM-Verbrauch
(2) Speicher für die zu berechnenden Hex-Ziffern wird nicht allokiert,
sondern per1 | extern uint8_t bytes[] __asm ("__heap_start"); |
deklariert.
(3) Man beginnt die Berechnung und Speicherung der Hex-Ziffern.
Dadurch wird am oberen RAM-Ende das Musters von (1) zerstört.
(4) Ist eine neues Byte für die Hex-Ziffern anzufangen, wird getestet,
ob ab dem zu speichernen bytes[] das (1) Muster noch intakt ist.
Falls ja, wird gespeichert, falls nicht, wird die Berechnung der
Hex-Ziffern beendet.
(5) Als Obergrenze für die Hex-Ziffern, gibt man 4096 vor. Für einen
ATmega328 wird diese Grenze zwar nicht erreicht, aber evtl. für
größere Devices.
(6) Es werden die Dec-Ziffern mit dem obigen Code ausgegeben, welcher
kein extra RAM benötigt.
(7) Es wird getestet, ob auf bytes[] noch ein paar Bytes des Musters aus
(1) folgen, z.B. 1 Byte weniger als in (4) gefordert. Ist das der
Fall, wird die Ausgabe als gültig markiert, ansonsten als ungültig.
Dies würde bedeuten, dass der Stack-Verbrauch in (6) weiter
angewachsen ist und möglicherweise Hex-Ziffern überschrieben
hat. Wahrscheinlich ist das nicht, da die Umwandlung nach Dec
"flach" ist und weniger Stacktiefe erfordert als das float-Zeugs.
> Also ist meine Erkenntnis bsher: Auf einem Atmega328 kann man bis zu
> 4000 Hex-Digits von Pi sichtbar machen, und auch bis zu 4000 (oder ein
> wenig mehr) an Dezimalstellen, aber 5000 Dezimalstellen von Pi sind
> gleich aus zwei Gründen außer Reichweite:
Ack.
> Für 5000 Dezimalstellen von Pi müßte man deutlich mehr als 4000
> Hex-Digits korrekt berechnen können, aber das gibt der Algorithmus
> nicht her.
Der Algorithmus schon, nicht aber die konkrete Implementierung. Man
müsste auf uint32_t oder __uint24 umsteigen und mod_pow16() entsprechend
anpassen. Außerdem zeigte sich bereits bei der vorliegenden
Implementierung die Einschränkungen von float, weshalb tame() eingeführt
wurde. Es ist auch zu analysieren, inwieweit tame() die Einschränkung
von float (i.w. nur 23 Bit Mantisse) noch zu zähmen in der Lage ist.
> Ich werde mich jedenfalls mal hinsetzen, und auf Basis des
> Programms-"fujita nozomu" einen Code für Arduino AVR-GCC entwickeln, der
> PI mit echten Dezimalstellen sichbar mahen kann.
Der Algorithmus ist der gleiche wie von mir, nur dass er
ungünstigerweise mit signed rechnet statt mit unsigned. Die Anzahl MSBs
wird nicht betrachtet, was eine einfachere aber langsamere
Implementierung gibt. Da jedoch die Zeit für Umwandlung + Ausgabe im
Vergleich zur Berechnung vernachlässigbar ist, spielt das keine Rolle
und das Nachführen von n_bytes kann man weglassen.
Es wurde schan angedeutet, aber vielleicht nicht klar genug. Man kann Nachkommastellen nicht problemlos zwischen Zahlensystemen umrechenen. Beispiel: 1/5*5 Im Dezimalsystem erhält man: 1/5=0,2 und 0,2*5=1,0 und im Hexadezimalsystem: 1/5=0,333... und 0,333...*5=0,fff... (!= 1,0) Wenn man die Anzahl der berechneten Stellen erhöht, kann man die Genauigkeit beliebig erhöhen. Aber trotzdem sind (im Hexadezimalsystem) alle Stellen falsch. Für eine Berechnung der Nachkommastellen von von Pi würde ich auf soetwas lieber verzichten. Ob es einen geeigneten Pi-Algorithmus für das Dezimalsystem gibt, ist mir unbekannt. Nein, ich bin kein Mathematiklehrer.
Pascal M. schrieb: > Es wurde schan angedeutet, aber vielleicht nicht klar genug. > Man kann Nachkommastellen nicht problemlos zwischen Zahlensystemen > umrechenen. > > Beispiel: 1/5*5 > Im Dezimalsystem erhält man: 1/5=0,2 und 0,2*5=1,0 > und im Hexadezimalsystem: 1/5=0,333... und 0,333...*5=0,fff... (!= 1,0) > > Wenn man die Anzahl der berechneten Stellen erhöht, kann man die > Genauigkeit beliebig erhöhen. > Aber trotzdem sind (im Hexadezimalsystem) alle Stellen falsch. Dies ist ein verwandtes aber anderes Problem: Die Darstellung rationaler Zahlen in einem Stellenwertsystem ist mitunter nicht eindeutig ! Falls eine rationale Zahl r ≠ 0 in gekürzter Darstellung vorliegt, d.h.
1 | r = a / b; a,b in Z\{0}; ggT (a,b) = 1
|
und ihre Darstellung soll im Stellenwertsystem zur Basis B geschehen, dann sind die r, deren b nur Primfaktoren hat, die auch in B vorkommen, nicht eindeutig dargestellt. Bekanntestes Beispiel ist r=1, welches in keinem Stellenwertsystem eine eindeutige Darstellung hat. Für B=10:
1 | r = 1.000... |
2 | = 0.999... |
Keine dieser Darstellungen ist falsch, und die erste der zweiten Vorzuziehen hat sich eben so eingebürgert weil man die "..." bei folgenden 0-en weglassen kann. In diesem Sinne ist es also nicht korrekt, zu behaupten, 9 sei nicht die erste Nachkommastelle in einer Dezimaldarstellung von 1. Und die Sprechweise, "1" sei die Darstellung der 1, ist bereits inkorrekt. Zumindest dieses Problem der Nichteindeutigkeit der Darstellung hat man bei irrationales Zahlen wie π nicht. > Für eine Berechnung der Nachkommastellen von Pi würde ich auf > soetwas lieber verzichten. Das Problem einer Folge von 9-en bzw. 0-en hat man bei der obigen Berechnung von π an zwei Stellen: Erstens bei der Umwandlung der Hex-Darstellung H nach Dezimal unter der Annahme, dass alle Nibbles von H korrekt sind. Ist H auf h Nibbles genau bestimmt, dann gilt
1 | 0 < π - H < 16^{-h}
|
Man könnte nun die Umwandlung nach Dezimal 2x durchführen, einmal mit
Abschätzung nach unten und einmal mit Abschätzung nach oben durch
16^{-h} und nur die gemeinsame Präfix an Nachkommastellen ausgeben.
Dies erforderte aber die Zwischenspeicherung der Dezimalstellen.
Alternativ könnte man die Dec-Ziffern in einen kleinen Zwischenpuffer
schreiben und nur dann ausgeben, wenn keine 9 folgt. Eine folgende 0
ist wegen der Abschätzung nach unten von π - H durch 0 kein Problem.
Wenn man also auf eine Situation wie in
https://en.wikipedia.org/wiki/Six_nines_in_pi stößt, dann würde die
"4999999" im Puffer gehalten und erst ausgegeben, nachdem die folgende 8
bestimmt wurde, und die "8" nur ausgegeben, nachdem die folgende 3
bestimmt wurde, etc. Wird die Berechnung beendet, dann wird das noch im
Puffer befindliche Zeug verworfen und fehlt in der Ausgabe.
Zweitens tritt das Problem bei der Berechnung der Nibbles von H selbst
auf, und zwar prinzipiell bei allen Nibbles, nicht nur bei den
niederwertigsten!
Dies erfordert eine Fehlerabschätzung für sigma() bzw. pi_n() und deren
Berücksichtigung in pi_dig16(). Falls das Nibble nicht stabil ist,
müsste man die Brerechnung erneut und mit größerer Genauigkeit
durchführen — oder eben die Berechnung mit einem sorry() beenden.
:
Bearbeitet durch User
Beitrag #5023518 wurde vom Autor gelöscht.
Baldrian schrieb: > Dann man los! Fange an zu tüfteln und berichte über deine Ergebnisse. So, es ist vollbracht: Ich habe einen Code fertiggestellt, der "hex digits" in Dezimalstellen umrechnen und anzeigen kann. Und so wie Johann hier vor gut fünf Jahren seinen Code "pi.c" zur Verfüng gestellt hat, um 4000 hex digits von Pi zu berechnen, im Thema: Beitrag "ATtiny2313 berechnet π auf 4000 Stellen" Genauso stelle ich hier meinen darauf aufbauenden Code zur Verfügung, der hex digits in Dezimalstellen umrechnet. Es handelt sich bei dem Code um einen "Arduino-Sketch", der von der Aruino-IDE kompiliert, auf ein Arduino-Board hochgeladen und ausgeführt werden kann. Getestet mit Arduino UNO, sollte aber mit anderen Arduino-kompatiblen Boards genau so funktionieren, ggf. mit minimalen Änderungen für Nicht-AVR Controller. Es handelt sich um ein interaktives Programm für den seriellen Monitor oder ein Terminalprogamm, es gibt ein ganz einfaches "Serial Command Menu" das über die Eingabe einzelner Buchstaben oder Ziffern bedient werden kann und über das man vorgibt, was man sehen möchte: Hex digits odr Dezimalstellen. Und wie viele davon. Die eigentliche Berechnung der Hex-Digits habe ich ausgeklammert und stattdessen eine vorberechnete Liste von 4000 Hex-Digits in den Code reingepackt, als PROGMEM-Array. Interessant wäre jetzt vielleicht noch die Kombination derbeiden Codes: Wenn ich bei meinem Programm zusätzlich zum "hex digits Mode" und "decimal digits Mode" noch einen Benchmark mode" vorsehen würde, der nicht mit vorberechneten Hex-Digits arbeitet, sondern diesezur Laufzeit selbst generiert, ann hätte man so eine Art Benchmarkprogramm für alle möglichen Arten von Arduino-kompatiblen Boards. Nicht nur für Boards mit Atmega-Controllern, sondern auch für Boards mit ARM Cortex-M Controllern, wie ATSAM3XE oder STM32-Boards. Die Arduino-IDE bringt ja inzwischen diverse Plattformen in einer einzigen IDE zusammen. Bis hin zu den chinesichen ESP8266 WIFI-Controllern. Wenn man ein Benchmark-Programm hätte, das auf allen diesen Boards läuft, könnte man direkte Gwschwindigkeitsvergleiche anstellen.
Johann L. schrieb: > Dies ist ein verwandtes aber anderes Problem: Die Darstellung rationaler > Zahlen in einem Stellenwertsystem ist mitunter nicht eindeutig ! Du hast recht. Ich habe mich geirrt.
Johann L. schrieb: > Der Algorithmus schon, nicht aber die konkrete Implementierung. Man > müsste auf uint32_t oder __uint24 umsteigen und mod_pow16() entsprechend > anpassen. Außerdem zeigte sich bereits bei der vorliegenden > Implementierung die Einschränkungen von float, weshalb tame() eingeführt > wurde. Es ist auch zu analysieren, inwieweit tame() die Einschränkung > von float (i.w. nur 23 Bit Mantisse) noch zu zähmen in der Lage ist. Hallo Johann, Du hast damit vollkommen recht. Ich habe mich in den letzten Tagen nochmal mit Deiner Implementierung befaßt und datsächlich: Mit uint32_t gibt es die Einschränkung auf ca. 4000 korrekte Hex-Digits auf Atmega nicht mehr. Nach Umsetzung auf die Arduino-Plattform und kleinen Modifikationen konnte ich heute morgen auf meinem Arduino UNO (Atmega328) problemlos korrekte hex-Digits von Pi um und bei der achttausendsten Nachkommastelle berechnen. Allerdings steigt der Zeitbedarf für die Berechnung der Hex-Digits mit uint32_t auch stark an. Bei Berechnungen um die achttausendste Stelle herum, beträgt die Rechendauer schon fast zehn Sekunden pro hex-Digit. Aber immerhin: Die Stellen kommen, und sie kommen richtig. Und auch wegen des Speicherproblems habe ich mir nochmal Gedanken gemacht und bin auf folgende mögliche Lösungen gekommen: 2. SD-Kartenmodul und SD-Karte zum Zwischenspeichern verwenden. Oder ein "FRAM"-Modul. FRAMs ist "ferro-magnetic RAM", der ähnlich wie ein EEPROM Daten nichtflüchtig speichert und die Daten beim Abschalten des Stroms über 80 Jahre lang halten soll.Im Gegensatz zu EEPROMs kann man FRAMs praktisch nicht kaputtschreiben, denn die sind milliardenfach wiederbeschreibbar.Ansteuerung per SPI. Ein 64kBit(=8kByte) FRAM kostet beim freundlichen China-Versender so um die 6 EUR. Und mit der Kombination "UNO + 8kB FRAM" sollte es dann locker möglich sein, zehntausend Dezimalstellen von PI auf einem 8-Bitter zu berechnen und am Ende auszugeben. Das überschlage ich mal wie folgt: Um am Ende 10000 Dezinalstellen zu bekommen, muss man vorher 10000/log16) =8305 (aufgerundet) hex Digits berecchnen. Wenn man diese mit 4Bit pro Digit abspeichert, erfordert das 4153 Bytes (ebenfalls aufgerundet) Zwischenspeicher. Die 10000 expandierten Dezimalstellen kann man auch wieder mit 4Bit pro Dezimalstelle abspeichern (BCD). Dasmacht 4153 Bytes Speicherbedarf für Hex-Digits und 5000 Bytes Speicher für das dezimale Endergebnis, macht zusammen 9153Bytes insgesamt. Die 8kB im FRAM-Modul sind 8192 Bytes plus 1024 Bytes hat das EEPROM im Arduino UNO (Atmega328) = 9216 Bytes nichtflüchtiger Speicher zusammen, also mehr als für 10000 Dezimalstellen von PI tatsächlich benötigt werden. Ich glaube, das gehe ich mal an und bestelle mir so ein 8kB FRAM-Modul in China, um mir dann ein PI-Gadget zu bauen, das mit inem UNO und einem FRAM-Modul die Zahl PI bis auf 10000 Dezimalstellen genau berechnen und zwischenspeichern kann. Und vielleicht dann per Tastendruck auf dieserielle Schnittstelle. Oder auf einen Thermo-Kassenbondrucker senden, um die 10000 Dezimalstellen auf einen langen Streifen Thermorolle zu drucken, z,B. 400 Zeilen a 25 Stellen. Wenn jede Zeile 5mm hoch ist, sind das2000mm, also ein Papierstreifen von zwi Meter Länge mit 10000 ausgedruckten Dezinalstellen von PI. Das erscheint mir inzwischen auch mit einem 8-Bitter machbar.
Pascal M. schrieb: > Beispiel: 1/5*5 > Im Dezimalsystem erhält man: 1/5=0,2 und 0,2*5=1,0 > und im Hexadezimalsystem: 1/5=0,333... und 0,333...*5=0,fff... (!= 1,0) 0,ffffff.... ist genauso wie 0,9999999.... natürlich genau 1. Beweise gibt es hier: https://de.wikipedia.org/wiki/0,999%E2%80%A6
Ich mache jetzt mal die Ingrid und antworte mir mal selbst: Jürgen S. schrieb: > Ich glaube, das gehe ich mal an und bestelle mir so ein 8kB FRAM-Modul > in China, um mir dann ein PI-Gadget zu bauen, das mit einem UNO und einem > FRAM-Modul die Zahl PI bis auf 10000 Dezimalstellen genau berechnen und >dauerhaft speichern kann. Abgesehen davon, dass man so ein 8KB FRAM-Modul wohl für viele Zwecke vewenden kann: OK, so ganz sicher bin ich noch nicht, ob ich das mit dem zehntausend-Dezimalstellen-Gadget tatsächlich mache,das dann das gesamte Ergebnis auch intern speichern kann aber was ich wohl definitiv angehen werde, ist ein Pogramm für die Berechnung und Ausgabe von 5000 Dezimalstellen auf einem Arduino UNO (Atmega328), OHNE dass zusätzliche Hardware zum Zwischenspeichern von Hex-Digits benötigt wird. Theoretisch sind ja alle Probleme dafür gelöst: 1. Für die Konvertierung von Hex-Digits in Dezimalstellen von PI habe ich bereits einen Arduino-Sketch/AVR-GCC-Code entwickelt und weiter oben in diesem Thema gepostet. 2. Die von Johann L. vor fünf Jahren in diesem Forum gepostete Implementierung des Borwein-Bailey-Plouffe-Algorithmus für AVR-GCC läßt sich durch Umstellung auf 32-Bit Integer-Datenytpen im Code so weit aufbohren, dass weitaus mehr als 4000 Hex-Digits von PI auf AVR-GCC korrekt berechnet werden können. 3. Und last but not least: Zum Zwischenspeichern von Hex-Digits steht auf einem Atmega328 nicht nur das 2048 Byte große RAM zur Verfügung, sondern auch ein 1024 Byte großes EEPROM. Und das zusammen reicht für 5000 Dezimalstellen von PI aus, weil einerseits nur wniger Hex-Digits berechnet weden müssen als man Dezimalstellen bekommen möchte, und andererseits, weil zum Abpspeichern einer Hex-Digit nur 4 Bits(ein Nibble, halbes Byte) und kein ganzes Byte benötigt wird. Das reicht speichermäßig Zwar nicht, um das gesamte Endergebnis am Ende zu speichern, aber immerhin, um ausreichend viele Hex-Digits zu berechnen und so lange zwischenzuspeichern, bis diese auf der seriellen Schnittstelle als Dezimalstellen ausgegeben werden können. Fünftausend Dezimalstellen(!) von PI auf einem Atmegs328 wäre dann wohl Wektrekord für8-Bit Mikrocontroller. Mit einem 8-Bitter hat es meines Wissens nach noch niemand geschafft, PI auf 5000 Dezimalstellen zu berechnen. Aber im Endeffekt ist das natürlich ohne irgendeinen praktischen Nutzen, nur eine Zahlenspielerei, da auf leistungsstarken PCsmit zig Prozessorkernen, Gigabytes RAM und Terabytes Festplattenspeicher die Zahl PI berereits auf mehrere tausend Milliarden Stellen berechnet worden ist. Da sind 5000 Stellen natürlich nur Kinkerlitzlichen im Vergleich, selbst wenn das für 8-Bitter einen Rekord darstellt. Sehen möchte das fertige Programm für 5000 Dezimalstellen von PI auf Atmega328) in diesem Forum wahrsheinlich niemand, oder? Dann poste ich es nur im Forum von Arduino.cc, da gab esin diesem Jahr schon zwei Themen, wie man aufeinem Arduino die "Nth digit of PI" berechnen kann, allerdings ohne dass der Themenstarter bezüglich "N" irgendeine Vorgabe gemacht hätte. Anyway.
Jürgen S. schrieb: > 3. Und last but not least: Zum Zwischenspeichern von Hex-Digits steht > auf einem Atmega328 nicht nur das 2048 Byte große RAM zur Verfügung, > sondern auch ein 1024 Byte großes EEPROM. Und vermutlich noch ein paar kB freies Flash, welches sich im Betrieb beschreiben lässt. Da gehen also noch ein paar 1000 Stellen ... Jürgen S. schrieb: > Mit einem 8-Bitter hat es meines > Wissens nach noch niemand geschafft, PI auf 5000 Dezimalstellen zu > berechnen. Ich habe mal davon gehört, dass jemand auf dem Prozessor der 1541-Floppy (Floppy vom C64) >100.000 Stellen berechnet und sogleich auf Floppy gespeichert hat. Gerade habe ich dazu aber nichts finden können. Es wäre aber naiv zu glauben, dass das noch niemand gemacht hat. Gruß Jobst
Jobst M. schrieb: > Und vermutlich noch ein paar kB freies Flash, welches sich im Betrieb > beschreiben lässt. Da gehen also noch ein paar 1000 Stellen ... Wie meinen? Echt jetzt? In einem laufenden Atmega328 Programm, den vom Programm nicht verwendeten Flash-Speicher beschreiben und auf diese Art quasi als zusätzlichen Variablenspeicher verwenden? Diesen Trick und wie das funktionieren soll, ohne dabei das laufende Progamm zu zerstören, kenne ich als Arduino-Programmierer bisher noch nicht. Ich würde mir, wenn der Speicher nicht reicht, entweder ein SD-Kartenmodul oder das weiter oben von mir erwähnte FRAM-Modul zusätzlich dranhängen. Oder ggf ein billiges Ein-Euro-RTC-China-Uhrenmodul mit einem AT24C32 I2C EEPROM drauf. Das hat nmit seinen 32kBit auch 4kByte Speicherplatz, was für die Speicherung von etwas über 8000 zusätzlichen Hex-Digits ausreichen würde.
Jobst M. schrieb: > Ich habe mal davon gehört, dass jemand auf dem Prozessor der 1541-Floppy > (Floppy vom C64) >100.000 Stellen berechnet und sogleich auf Floppy > gespeichert hat. laut https://de.wikipedia.org/wiki/VC1541#Spezifikationen ist da ein 6502 drauf Der sollte das als Hauptprozessor z.B. eines VC20 wohl können. Aber die Idee allein ist schonmal nett.
Jürgen S. schrieb: > In einem laufenden Atmega328 Programm, den vom Programm nicht > verwendeten Flash-Speicher beschreiben und auf diese Art quasi als > zusätzlichen Variablenspeicher verwenden? Nur einmal beschreibbar. Löschen nur Seitenweise. Jürgen S. schrieb: > Diesen Trick und wie das funktionieren soll, ohne dabei das laufende > Progamm zu zerstören, kenne ich als Arduino-Programmierer bisher noch > nicht. Doch, eigentlich schon. Ein Bootloader arbeitet so. Auch vom Arduino. Mike B. schrieb: > Aber die Idee allein ist schonmal nett. Den Prozessor der Floppy als Coprozessor zu nutzen war gängige Praxis. Gruß Jobst
Ich versteh den Antrieb immer noch nicht... Hat man einen funktionierenden Algorithmus (der wird ja sozusagen geklaut :-) ist es doch völlig unabhängig von der Bitbreite des Prozessors nur eine Frage von Rechenzeit und Speichergrösse. Wenn der Algotithmus korrekt ist, kannst du mit beliebig viel Speicher beliebig viele Stellen berechnen - wo ist der Reiz? Falls man Spass daran hat, kann man das auch als Simulation auf dem PC laufen, eine echte Hardware ist dafür nicht erforderlich. Spass ist aber auch das eigentlich nicht, da das Ergebnis schon vorher feststeht. Eher Masochismus. Aber für manche ist das ja Spass :-)
Hallo, "Sehen möchte das fertige Programm für 5000 Dezimalstellen von PI auf Atmega328) in diesem Forum wahrsheinlich niemand, oder?" also ich hätte daran bestimmt meinen Spaß. Z.B. eine Animation fürs GLCD draus machen... Mit freundlichem Gruß
Mike B. schrieb: > Jobst M. schrieb: > >> Ich habe mal davon gehört, dass jemand auf dem Prozessor der 1541-Floppy >> (Floppy vom C64) >100.000 Stellen berechnet und sogleich auf Floppy >> gespeichert hat. > > laut https://de.wikipedia.org/wiki/VC1541#Spezifikationen ist da ein > 6502 drauf > > Der sollte das als Hauptprozessor z.B. eines VC20 wohl können. Jein. Entscheidend ist nicht die Rechenleistung. Die bestimmt nur, wie lange es dauert. Und ein 6502 verliert in diesem Punkt klar gegen einen AVR8. Das Problem, das der 6502 in der VC1541 hat, ist daß ihm nur 2KB RAM zur Verfügung stehen. Und da muß alles reinpassen. Nicht nur die Dezimalstellen von Pi, sondern auch das Programm selber. Und alles, was die Floppy-Firmware an RAM braucht, um mit dem C64 zu kommunizieren. Natürlich könnte so ein Programm auch die Magnetscheibe selber als Speicher verwenden. Allerdings würde das dann noch einmal deutlich (Faktor 10000?) langsamer werden. Weil man ja potentiell alle Dezimalziffern zur Verfügung haben muß, um einen Überlauf zu berücksichtigen. Auch dann, wenn der 10000 Stellen nach dem Komma auftritt. Erinnern kann ich mich an ein Pi-Programm auch nicht. Die Floppy konnte "My bonnie is over the ocean" spielen (mit dem Schrittmotor für die Kopfbewegung als "Lautsprecher". Und es gab ein "Apfelmännchen"- Programm, das jede zweite Zeile in der Floppy gerechnet hat.
Thread beobachten
Seitenaufteilung abschaltenBitte melde dich an um einen Beitrag zu schreiben. Anmeldung ist kostenlos und dauert nur eine Minute.
Bestehender Account
Schon ein Account bei Google/GoogleMail? Keine Anmeldung erforderlich!
Mit Google-Account einloggen
Mit Google-Account einloggen
Noch kein Account? Hier anmelden.