Pi auf viele Stellen berechnet

17/10/2013 - 17:10 von wernertrp | Report spam
Wenn irrationale Zahlen mit dem Computer berechnet werden z.B. auf sehr viele Stellen
z.B. pi, wieviel Speicherplatz (zirka Angabe) wird dann minimal für wieviel Stellen benötigt.

Ist das mehr eine Frage an Programmierer oder Mathematiker ?
 

Lesen sie die antworten

#1 Christian Gollwitzer
17/10/2013 - 20:23 | Warnen spam
Am 17.10.13 17:10, schrieb wernertrp:
Wenn irrationale Zahlen mit dem Computer berechnet werden z.B. auf sehr viele Stellen
z.B. pi, wieviel Speicherplatz (zirka Angabe) wird dann minimal für wieviel Stellen benötigt.

Ist das mehr eine Frage an Programmierer oder Mathematiker ?




Ist eher Informatik, allerdings werden viele Mathematiker damit was
anfangen können.

Die Antwort hàngt vom verwendeten Algortihmus ab. In der Tat beschàftigt
sich ein Teil der Informatik mit genau soclhen Fragen, nàmlich die
Komplexitàtsanalyse. Dabei geht es darum, Nàherungsformeln für einen
gegeben Algorithmus anzugeben, wieviele Schritte er braucht und wieviel
Speicherplatz benötigt wird. Meist wird nur die sog. "asymptotische
Komplexitàt" berechnet, das ist die Frage, wie sich bei Erhöhung der
Anforderung - etwa Verdopplung - der Resourcenverbrauch veràndert.

Ein Algorithmus mit linearem Speicherverbrauch, geschrieben O(N),
braucht für doppelt so viele Stellen ungefàhr doppelt so viel Speicher.
Das ist nàherungsweise für große N zu verstehen, so dass ein konstanter
Bedarf an Zwischenspeicher etc. vernachlàssigt wird. Diese O()-notation
ist durch einen Grenzwert genau definiert. Ein O(N^2)-Algorithmus würde
für die Berechnung von doppelt so vielen Stellen dann viermal so viel
Platz brauchen.

Konkret für pi gibt es sogenannte digit extraction Algorithmen.

en.wikipedia.org/wiki/Bailey–Borwein–Plouffe_formula

Hierbei sollte - wenn ich nichts übersehen habe - der Speicherverbrauch
für die k-te Stelle zur Basis 16 lediglich O(log(k)) sein (um k selbst
zu speichern), wobei man schon O(k) Speicher braucht, wenn man das
Ergebnis für alle Ziffern abspeichern will. Möchte man die Ziffern nur
als Strom vorbeihuschen lassen, dann hat man eben O(log(k)).

Christian

Ähnliche fragen