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?
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)
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().
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.
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.
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.
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
staticfloatsigma(unsignedn,uint8_tj);
2
staticfloatpi_n(unsignedn);
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 per
1
externuint8_tbytes[]__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.
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.