27Mar/090

## Computing the Square Root of Two

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} - 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