Numerische Berechnung von pi, sqrt, sin, cos

VeryApe · Anmeldungsdatum: 10.02.2008 Beiträge: 3247

Weil ihr gerade über PI und Wurzel 2 redets.
Ich habe zuvor ein Nullstellenfindungs Programm mit Javascript geschrieben, aber DoubleFloat64bit hat klarerweise nur ne beschränkte Genauigkeit, jetzt komme ich vom Regen in die Traufe und hantiere mit BigIntegers und zwar als Bruch, da kann mir erst alles selbst erarbeiten.

Jetzt habe ich Wurzel 2 Folge mit a[0]=1/2

realisiert, aber mit jeder Iteration komme ich nicht gerade schnell in tiefere Genauigkeit.

PI habe ich mit https://crypto.stanford.edu/pbc/notes/pi/ramanujan.html
realisiert, da gehts ab pro Itertation.
https://jsfiddle.net/Veryape/y3pe2L8d/58/

Aber was wäre die schnellste wurzel2 folge für die Berechnung?

Momentan arbeite ich an sinus und cosinus, da nehme ich die Taylor Reihe, oder gibts was schnelleres?

TomS · Moderator Anmeldungsdatum: 20.03.2009 Beiträge: 18030

Generell:

Javascript im Browser? Such mal nach Algorithmen und Implementierungen der Numerical Recipes; zu meiner Zeit gab‘s die in FORTRAN und C++.

Dann: Geht es dir um eine größtmögliche Präzision, also um möglichst viele Stellen? Oder geht es dir um möglichst schnelle Konvergenz für eine feste Anzahl von Stellen? Das kann auf unterschiedliche Methoden rauslaufen.

Bzgl. numerischer Berechnungen: Es gibt ein paar allgemeingültige Fallen und Tricks. Eine Falle ist die Berechnung der Differenz kleiner Zahlen; das muss man auf jeden Fall vermeiden. Ein Trick ist das Hornerschema für Polynome und Taylorreihen:

Die iterative Berechnung erfolgt von innen nach außen:

Das einfachste Verfahren zur Quadratwurzelberechnung für allgemeine a, nicht nur speziell a = 2, ist das sogenannte Heron-Verfahren. Es gilt die Rekursion

Es konvergiert sehr schnell (recht langsam) bei guter (schlechter) Wahl des Startwertes.

Andere Verfahren findest du hier: https://en.m.wikipedia.org/wiki/Methods_of_computing_square_roots

Dein Verfahren zur Berechnung von pi nach Ramanujan ist vernünftig, wenn es um möglichst viele Stellen geht; weitere Methoden findest du hier: https://en.m.wikipedia.org/wiki/Pi#Rapidly_convergent_series

Die Berechnung von Winkelfunktionen ist die Taylorentwicklung des Sinus um x = 0 aufgrund der alternierenden Reihe geeignet. Dazu muss man mittels der Theoreme für Sinus und Cosinus dafür sorgen, dass die Berechnung einer Winkelfunktion f(a) zum Funktionswert a in die Form

mit

gebracht wird, wobei F ein Ausdruck ist, der nur von sin(x) sowie Konstanten abhängt, und wobei x möglichst nahe bei Null liegen sollte! sin(x) wird dann genau einmal numerisch berechnet.

VeryApe · Anmeldungsdatum: 10.02.2008 Beiträge: 3247

TomS · Moderator Anmeldungsdatum: 20.03.2009 Beiträge: 18030

JavaScript wird interpretiert, egal, wo‘s läuft. Wenn dir die Performance ausreicht, ist‘s OK, aber grundsätzlich ist eine compilierte Sprache immer noch schneller.

Bzgl. der Berechnung hatte ich dich wohl falsch verstanden. Ich sehe nicht, dass du die Berechungen sinnvollerweise mittels Integer-Arithmetik durchführen kannst.

Du benötigst eine Formel, die überhaupt mit Integern arbeitet. Das hast du i.A. nicht, pi ist ein Spezialfall. Selbst wenn du mit Integern und Brüchen arbeitest, hast du das Problem, dass dir Zähler und Nenner getrennt überlaufen, wenn du erst zuletzt den Bruch berechnest. Einfaches Bsp. wäre die Taylorreihe des Sinus. Und zuletzt sehe ich nicht, dass du bei deiner Berechnung mit x-Bit Integern besser sein wirst als die FPU mit x-Bit Float.

VeryApe · Anmeldungsdatum: 10.02.2008 Beiträge: 3247

TomS · Moderator Anmeldungsdatum: 20.03.2009 Beiträge: 18030

Ok, dass V8 Javascript in nativen Maschinencode compiliert wusste ich nicht.

Zu meinem Einwand bzgl. Integer: Integer-Berechnungen haben zunächst den Vorteil, dass sie - wenn im Rahmen des Datenformats möglich - exakt sind. Ob sie auch schneller sind, ist eine Frage der Implementierung. Spätestens wenn das Datenformat nicht mehr zur Prozessorarchitektur passt, sehe ich das nicht unbedingt.

Zu pi: hier liegt ein Algorithmus vor, der speziell zur bitweisen Berechnung verwendet werden kann. Wenn ein derartiger Algorithmus bekannt ist, dann mag das natürlich Vorteile haben. Aber i.A. ist das ja nicht der Fall. Schau dir die Taylorreihe zum Sinus für beliebiges x an: die Reihe konvergiert für kleines x aufgrund der alternierenden Vorzeichen extrem schnell und liefert eine sehr hohe Genauigkeit, weil das Taylorsche Restglied sehr schnell klein wird. Wenn du aber Integer-Arithmetik verwendest, dann musst du Zähler und Nenner getrennt berechnen, was evtl. deutlich früher zu einem Überlauf führt.

VeryApe · Anmeldungsdatum: 10.02.2008 Beiträge: 3247

ist überhaupt kein Problem

1000 mal sinus auf denominator 2^1024 hintereinander ausrechnen für PI/2 dauert 512ms.

dabei rechne ich das übergebene x (BigInt fraction z.B 12999212/1112121289) auf einen denominator_expanded=j*denominator (z.B j=1000) und erhalte diesen Nenner während der ganzen Berechnung, die Fehler habe ich abgeschätzt, pro Folgeglied mache ich ungefähr 1.2/denominator_expanded Fehler, da sollte für 500 Summierungen eine Erweiterung auf 1000 reichen.

für j=1000

Bei 2^1024 und PI/2 brauche ich 93 Schleifendurchgänge also 94 Folgeglieder

und PI/2 ist maximum Wert den ich für die Folge erlaube für x erlaube, größere x Werte kann man ja leicht in die Quartale umrechnen, ändert sich ja nichts ausser vielleicht das Vorzeichen.