Digit sequences for various square roots, given at the top in base 10 and at the bottom in base 2. Despite their simple definition, all these sequences seem for practical purposes random.

But how is such randomness produced? The picture at the top of the facing page shows an example of a procedure for generating the base 2 digit sequence for the square root of a given number n.

The procedure is only slightly more complicated than the one for division discussed above. It involves two numbers r and s, which are initially set to be n and 0, respectively. At each step it compares the values of r and s, and if r is larger than s it replaces r and s by 4r - 4s - 1 and 2s + 1 respectively; otherwise it replaces them just by 4r and 2s. And it then turns out that the base 2 digits of s correspond exactly to the base 2 digits of √n—with one new digit being generated at each step.

As the picture shows, the results of the procedure exhibit considerable complexity. And indeed, it seems that just like so many other examples that we have discussed in this book, the procedure for generating square roots is based on simple rules but nevertheless yields behavior of great complexity.