PI mit 8-Bit Controller auf viele DEZIMALSTELLEN genau berechnen

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?

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"

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.

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.

...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

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.

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 per

1

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.

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:
> 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.