Wurzel ziehen mit Newton
-
Ich mache mir gerade darüber Gedanken, welchen Startwert man bei diesem
Verfahren wählen sollte.Gesucht: (positive) NST der Funktion f(x) = x^2 - a Newton-Iteration t_n+1 = 0.5 * (t_n + a/t_n)Die Iteration mit a zu starten führt zwar zum Erfolg, braucht natürlich für große
a länger. Welches (geschicktere) t_0 könnte man setzten?
-
Wenn a eine Ganzzahl ist, dann Position des höchstwertigen Bits von a suchen: b
t_0 = 1 << (b/2)
Höchstwertiges Bits suchen geht bei einer 32-Bit-Zahl mit 5 Vergleichen (wegen 32 = 2^5).
-
Und wenn a keine Ganzzahl ist...?
