brainwagon

I was dusting off some of my old code for computing pi to many decimal places, and was reminded that I’d never written similar code for computing a more basic value: the square root of two.

The usual way to do this would be to use Newton’s iteration to solve x² – 2 = 0. If you apply this, you get the following
iteration formula:

         x
          n    1
x      = -- + --
 n + 1    2   x
               n

There’s a problem with this, you have to implement reciprocals (or long division) to let the Newton’s iteration work. If instead you try to solve 1/x^2 – 1/2 = 0, you get an easier iteration that also works:

                 3
         3 x    x
            n    n
x      = ---- - --
 n + 1     2     4

Here are some digits. It appears to work.

1.
4142135623 7309504880 1688724209 6980785696 7187537694
8073176679 7379907324 7846210703 8850387534 3276415727
3501384623 0912297024 9248360558 5073721264 4121497099
9358314132 2266592750 5592755799 9505011527 8206057147
0109559971 6059702745 3459686201 4728517418 6408891986
0955232923 0484308714 3214508397 6260362799 5251407989
6872533965 4633180882 9640620615 2583523950 5474575028
7759961729 8355752203 3753185701 1354374603 4084988471
6038689997 0699004815 0305440277 9031645424 7823068492
9369186215 8057846311 1596668713 0130156185 6898723723