A Procedure to Compute the Digit Sequence of a Square Root

square root of:

7

steps

96

7

10.10100101010011111111010100111010010111110001110100110110111100100

2

r	s = digit sequence of n

This Demonstration visualizes a procedure for generating the base-2 digit sequence of a square root. From A New Kind of Science, p. 141: "To find

n

, start by setting

r=n

and

s=0

. Then at each step apply the rule

{r,s}→If[r≥s+1,{4(r-s-1),2(s+2)},{4r,2s}]

. The result is that the base-2 digits of

s

turn out to correspond exactly to the digits of

n

. If

n

is not between 1 and 4, it must be multiplied or divided by an appropriate power of 4 before starting the procedure."

The digit sequence of r is shown on the left, while the digit sequence of

s

—which corresponds exactly to

n

—is shown on the right. Black cells represent ones, and gray cells represent zeros.