Showing Text From Page | View full page with images

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 4(r–s–1) and 2(s+2) 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 Sqrt[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.