Wolfram's Iteration

Wolfram's iteration is an algorithm for computing the square root of a rational number 1<=r<4 using properties of the binary representation of r. The algorithm begins with (u_0,v_0)=(r,0), and then iterates

Interpreted as a binary number, v_n then converges to sqrt(r).

For example, for r=2 (i.e., Pythagoras's constant), u_n is given by 2, 4, 16, 28, 28, 112, 92, 368, 28, ... (OEIS A095803), and v_n by 0, 4, 8, 20, 44, 88, 180, 360, 724, ... (OEIS A095804). The binary representation of successive terms of v_n (with the "binary" point shifted after the first term) are then

as illustrated above, which can be seen to produce increasing numbers of digits in the binary representation of sqrt(2),

(OEIS A004539). Interpreting the binary fractions produced at each step gives the sequence of approximations 1, 1, 5/4, 11/8, 11/8, 45/32, 45/32, 181/128, 181/128, ... (OEIS A095805 and A095806).

See also

Explore with Wolfram|Alpha

References

Referenced on Wolfram|Alpha

Cite this as:

Weisstein, Eric W. "Wolfram's Iteration." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/WolframsIteration.html

Subject classifications