Newton-Iteration für Kubikwurzel ohne Division

Es ist ein ziemlich bekannter Trick, um eine Division bei der Berechnung von Quadratwurzeln zu vermeiden, um die Newtonsche Methode auf das Finden von anzuwenden$1/\sqrt{x}$ , und wahrscheinlich besser bekannt, wenn man die Newtonsche Methode verwendet, um Kehrwerte ohne Division zu finden .

Bei der Rettung eines StackOverflow-Threads, der die Newton-Iteration für die Kubikwurzel effizient aus der Link-Fäule aussetzt, kam mir der Gedanke, dass auch eine teilungsfreie Iteration für Kubikwurzeln möglich sein sollte.

Zum Beispiel, wenn wir lösen würden:

$$x^{-3} = a^2$$

dann ist und . Die Newton-Iteration für die obige Gleichung lautet einfach:$x = a^{-2/3}$$\sqrt[3]{a} = ax$

$$x_{n+1} = x_n - \frac{ x_n^{-3} - a^2 }{-3x_n^{-4}} = \frac{4}{3}x_n - \frac{1}{3}a^2 x_n^4$$

Auch hier vermeiden wir Divisionsoperationen, zumindest wenn die Bruchkonstanten für FP-Multiplikationen vorab ausgewertet werden.

So etwas ist möglich, aber ich habe bei meiner (zugegebenermaßen flachen) Suche im Web keine spezifische Diskussion über solche Methoden gefunden. Genauer gesagt, ich vermute, dass eine kluge Person bereits eine bessere Idee entdeckt hat und dass einer von Ihnen geschätzten Kollegen sie gesehen oder durchdacht hat.

Kubikwurzeln sind bei weitem nicht so wichtig wie Quadratwurzeln (z. B. zum Normalisieren von Vektoren), weshalb sie möglicherweise viel weniger diskutiert werden.

Wenn Sie die Newtonsche Methode auf anwenden, erhalten Sie im Allgemeinen die Iteration ( 1 - α - 1 ) x + $x^\alpha-\beta$ Sie müssen also nur die Gleichung so auswählen, dassαeine negative ganze Zahl ist. Es sind nicht nur Würfel und Quadratwurzeln, dies funktioniert auch für andere rationale Kräfte.

$$(1-\alpha^{-1})x+\frac\beta\alpha x^{1-\alpha},$$ $\alpha$

Ihr Schema benötigt nur 7 Iterationen, um im Intervall a ∈ [ 1 zur doppelten Genauigkeit zu konvergierenausgehend von der konstanten Anfangsschätzung1:$a\in[\frac12,1]$$1$

Eine weitere interessante Sache ist, was vorhandene Bibliotheken implementieren:

• MPFR erstellt Kubikwurzeln mit ganzzahligen Kubikwurzeln ( http://www.mpfr.org/algo.html , um Seite 36).
• math/special_functions/cbrt.hpp $$x_{n+1} = x_n \frac{2b+x_n^3}{b+2x_n^3}.$$ $\sim20$div{s,p}{s,d}

$a^{-2/3}$$\frac13$$x^3-a$$[\frac12,1]$