Content deleted Content added
→Newton–Raphson division: Split up "Variant Newton–Raphson division" subsection. The auadratic initial estimate material was moved up to join the linar estimate text in a new "Initial estimate" subsection. The remaining discusson of a cubic iteration is retitled "Cubic iteration." Rewrite "number of iterations to get P bits" equation to "number of bits after S iterations". FIXME: Is the cubic iteration exactly cubic, or is there a scaling term? |
→Cubic iteration: Yes, the error is exactly cubed. Also gave a more elementary explanation of the |
||
Line 286:
====Cubic iteration====
There is an iteration which uses three multiplications to cube the error:
:<math>
:<math>
:<math>
The ''Y<sub>i</sub>''⋅''E<sub>i</sub>'' term is new.
Expanding out the above, <math>X_{i+1}</math> can be written as
:<math>\begin{align}
X_{i+1} &= X_i + X_iE_i + X_iE_i^2 \\
&= X_i + X_i(1-DX_i) + X_i(1-DX_i)^2 \\
&= 3X_i - 3DX_i^2 + D^2X_i^3 ,
\end{align}</math>
with the result that the error term
:<math>\begin{align}
E_{i+1} &= 1 - DX_{i+1} \\
&= 1 - 3DX_i + 3D^2X_i^2 - D^3X_i^3 \\
&= (1 - DX_i)^3 \\
&= E_i^3 .
\end{align}</math>
This is 3/2 the computation of the quadratic iteration, but achieves <math>\log 3 / \log 2 \approx 1.585</math> as much convergence, so is slightly more efficient. Put another way, two iterations of this method raise the error to the ninth power at the same computational cost as three quadratic iterations, which only raise the error to the eighth power.
The number of correct bits after <math>S</math> iterations is
| |||