Matroids Matheplanet Forum Index
Moderiert von matroid
Mathematik » Numerik & Optimierung » Suche Algorithmus für asin(x) oder atan(x) bei 1 Mrd. Stellen
Autor
Universität/Hochschule Suche Algorithmus für asin(x) oder atan(x) bei 1 Mrd. Stellen
hyperG
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 03.02.2017
Mitteilungen: 1587
  Themenstart: 2019-04-16

Da asin und atan untrennbar mit Wurzeln verbunden sind, ist es egal, für welchen der beiden Funktionen optimiert wird. Das Argument habe ich bereits durch zig Formeln auf etwa 0.01 verkleinert. Weitere Verkleinerungen bringen nichts, da jede Wurzel auch wieder auf 1 Mrd. Stellen berechnet werden muss. (außerdem wird durch Fehlerfortpflanzung alles nur ungenauer) Fast jeder kennt die Reihen ArcTan[z] == Sum[((-1)^k z^(2 k + 1))/(2 k + 1), k=... wo man mit 1000 Termen etwa 4000 Nachkommastellen genau ist. Selten: ArcTan[z] == Sum[(((-1)^k Fibonacci[2 k + 1])/(5^k (2 k + 1))) ((2 z)/(1 + Sqrt[1 + (4/5) z^2]))^(2 k + 1), k=0... bringt bei 1000 Termen nur etwas mehr: 4286 Nachkommastellen. Hypergeometrische Funktionen: - nur für "glatte Argumente" schnell - bei 1 Mrd. Stellen-Argumente leider noch langsamer. Alles bis 100 Mio. machbar, ABER danach gerät man an zig Grenzen: - die GMP-DLLs rechnen ab 300 Mio. Stellen falsch (und so auch alle anderen Programme wie Julia usw.) - Mathematica kommt ab 1 Mrd. Stellen an die RAM-Grenze von 32 GB. Gibt es nicht schnellere iterative Algorithmen (analog zur Newton-Iteration), die quadratisch konvergieren?


   Profil
rlk
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 16.03.2007
Mitteilungen: 11208
Wohnort: Wien
  Beitrag No.1, eingetragen 2019-04-16

Hallo Gerd, etwas ähnliches hatten wir schon in https://matheplanet.at/matheplanet/nuke/html/viewtopic.php?topic=232446&post_id=1692900 diskutiert, dort kam auch der Arkustangens vor. Kennst Du schon den AGM-Algorithmus [1, (43)-(47)]? [1] Weisstein, Eric W. "Inverse Tangent." From MathWorld--A Wolfram Web Resource. http://mathworld.wolfram.com/InverseTangent.html Servus, Roland


   Profil
hyperG
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 03.02.2017
Mitteilungen: 1587
  Beitrag No.2, vom Themenstarter, eingetragen 2019-04-17

Hallo, Danke für den LINK. Ja, ich kenne AGM-Algorithmen und wollte mich schon freuen, da AGM-Iterationen normalerweise quadratisch konvergieren. ABER: Formel (46) verwendet (wegen nur "AGM-like") nicht das übliche geometr. Mittel mit a[i], sondern a[i+1], was eine extrem langsamere Konvergenz ergibt: für n Stellen braucht man etwa n*1.666666 Wurzel-Iterationen, was alles unbrauchbar macht :-(


   Profil
hyperG
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 03.02.2017
Mitteilungen: 1587
  Beitrag No.3, vom Themenstarter, eingetragen 2021-11-17

Ich möchte nochmal die Iterationen unter Fast Multiple-Precision Evaluation of Elementary Functions ansprechen, da ich keine richtigen Vorteile für die Berechnung von mehr als 1 Mio. Nachkommastellen sehe: - die atan-Iteration hat dort auf Seite 249 eine log-Funktion :-( - S. 247: 2 Iterationen mit der Abhängigkeit U(m)=log(T(m)) Zwar kann man asin nach log Funktionen umstellen: \sourceon nameDerSprache ArcSin[z] == Pi/2 + 2 (Sqrt[z - 1]/Sqrt[1 - z]) ArcSinh[Sqrt[(z - 1)/2]] =Pi/2 + (2 Sqrt[-1 + z] Log[(Sqrt[-1 + z] + Sqrt[1 + z])/Sqrt[2]])/Sqrt[1 - z] \sourceoff aber so wie ich U(m) verstanden habe, gilt: \sourceon nameDerSprache log(x)=16/E^(2*Pi^2/(4*U(x))) \sourceoff und man holt sich zur zweifachen Iteration für U noch eine Exponentialfunktion hinzu...


Wahlurne Für hyperG bei den Matheplanet-Awards stimmen
   Profil
Delastelle
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 17.11.2006
Mitteilungen: 1888
  Beitrag No.4, eingetragen 2021-11-18

Hallo hyperG! Geht es eigentlich um atan(x) oder atan(z)? Um etwas reelles oder komplexes? Mir erscheint der reelle atan nicht so interessant - atan hat einen recht einfachen Verlauf. Viele Grüße Ronald


Wahlurne Für Delastelle bei den Matheplanet-Awards stimmen
   Profil
hyperG
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 03.02.2017
Mitteilungen: 1587
  Beitrag No.5, vom Themenstarter, eingetragen 2021-11-18

\quoteon(2021-11-18 13:16 - Delastelle in Beitrag No. 4) ... Um etwas reelles oder komplexes? ... \quoteoff Natürlich reell, da wir hier nicht von ein "paar 1000", sonder von 1 Mrd. Dezimalstellen reden! Das verstehen viele nicht, dass der Rechenaufwand & der RAM-Verbrauch fast exponentiell ansteigen. Durch das Kopieren aus https://functions.wolfram.com/ElementaryFunctions/ArcTan/ kam das "z" herein, weil die universellen Gesetze natürlich auch für komplexe Zahlen gelten. Ich kann zwar eine reelle Wurzel mit 1 Mrd. Stellen zwar unter 30 s berechnen (was viele 16 Kern Rechner nicht mal hinbekommen), aber wenn man wie im Beitrag 2 beschrieben n*1.666666 Wurzel-Iterationen benötigt, bedeutet das über 1520 Jahre!! Man muss also sehr effektive Algorithmen verwenden -> und wie im Beitrag 3 dachte ich nun, dass "Fast Multiple-Precision Evaluation of Elementary Functions" was "brauchbares" sei. Beim genauen Hinsehen tauchten jedoch lauter "höhere Funktionen" auf, die alles wieder unbrauchbar machen: - bei atan(x) steht nach der eigentlichen Iteration (die wegen 2 Wurzeln pro Iteration und langsamer als Newton-Iteration ewig braucht) noch eine log-Funktion -> da kann man auch gleich ohne eine langsame Iteration mit 1 elementaren Funktion das hier berechnen: asin(x)=Pi/2 + (2 Sqrt[-1 + x] Log[(Sqrt[-1 + x] + Sqrt[1 + x])/Sqrt[2]])/Sqrt[1 - x] Mit U(m) soll man log(x) berechnen können, aber: - auch wieder Iterationen mit Wurzeln - dann das Ganze 2 mal - und am Ende dann noch exp-Funktion (bekannte schnelle Reihe) Die Reihenentwicklung und auch die hypergeometrischen Funktionen kommen wenigstens mit den Grundrechenarten aus. Leider muss man zunächst die Argumente mit weiteren Tricks sehr klein machen, um die Iterationsanzahl gegenüber der Stellenanzahl wenigstens zu zehnteln. Je mehr man jedoch die Argumente verkleinert, um so ungenauer wird das Ganze! (nicht das einer denkt, dass man einfach das Argument auf 1/1Mrd. verkleinert und mit wenigen Iterationen dann aus dieser 1 "effektiven Stelle" später 1 Mrd. richtige Stellen berechnen kann. Bei https://en.wikipedia.org/wiki/Logarithm findet man noch was mit schnellem AGM -> aber das hintere Argument ist 2^2 Mrd. groß, was unmöglich genau zu berechnen ist. Dann noch in der deutschen Version ein Binärziffern-Algorithmus. Zwar schnell, aber das Umrechnen einer Binärzahl mit 3 Mrd. Stellen in eine Dezimalzahl, ist auch nicht ohne...


Wahlurne Für hyperG bei den Matheplanet-Awards stimmen
   Profil
hyperG hat die Antworten auf ihre/seine Frage gesehen.

Wechsel in ein anderes Forum:
 Suchen    
 
All logos and trademarks in this site are property of their respective owner. The comments are property of their posters, all the rest © 2001-2022 by Matroids Matheplanet
This web site was originally made with PHP-Nuke, a former web portal system written in PHP that seems no longer to be maintained nor supported. PHP-Nuke is Free Software released under the GNU/GPL license.
Ich distanziere mich von rechtswidrigen oder anstößigen Inhalten, die sich trotz aufmerksamer Prüfung hinter hier verwendeten Links verbergen mögen.
Lesen Sie die Nutzungsbedingungen, die Distanzierung, die Datenschutzerklärung und das Impressum.
[Seitenanfang]