## Wednesday, February 18, 2009

### Incredibly simple ways to get rational approximations to square roots

Over at The Universe of Discourse, Mark Dominus talks about Archimedes and the square root of three pointing out that Archimedes needn't have had some mystical way of finding rational approximations to surds in order to figure that 265/153 is very close to the square root of three.

He points out that there's a simple enough pattern that Archimedes could have spotted and soon figured it out. That is true enough, but Archimedes could have got by, while being even less clever than that.

Let's consider a few simple facts:
(i) if a and b are close to the ratio √3:1 then 3b and a are also close to that ratio, with the error in the opposite direction and of similar magnitude
(ii) Hence (a+3b):(b+a) will be substantially closer* to √3:1 than a:b is

*(in fact it improves the error in the approximation of 3 by a2/b2 by a factor that rapidly goes to 2+√3, but Archimedes needn't have figured that fact out - he only needs to have noticed that 3b:a is also an approximation of √3:1, and (a+3b):(b+a) always seems to be a better approximation than he started with)

If we proceed in this fashion from the very ordinary starting point of 2:1 (and eliminate common factors as they pop up), we rapidly hit on Archimedes' ratio.

`  2    1   (a:b)  3    2   (3b:a)  5    3   (a+3b:b+a), which becomes our new a:b  9    5  7    4   (dividing out a common factor of 2 here) 12    7 19   11 33   19 26   15   (taking out another factor of 2) 45   26 71   41123   71 97   56  (taking out a third factor of 2)168   97265  153  `

And you're there after maybe a couple of minutes of very simple computation, even if you're a much worse computer (in the original sense) than Archimedes doubtless was.

Not in the least mysterious, and a bonehead like me figured it out almost immediately. I'll wager a master like Archimedes realized something like this in even less time than it took me. It's so simple, he probably wouldn't have even bothered to write it down.

__________

(Later edit:)
What I have above appears to be basically the Bablyonian Method, on which Brent at The Math Less Traveled writes here.

I must have seen mention of this before (at least the phrase "Babylonian Method" sounds somewhat familiar). I have no doubt Archimedes was familiar with some version of it.

#### 2 comments:

1. I don't know how common the TI 89 [Texas Instruments] calculator is outside the US, but here's a program to do this method:

arch(r,a,b)
Prgm
1->n
While n<8
a+r*b->t
a+b->z
gcd(t,z)->g
t/g->a
z/g->b
Disp a,b
n+1->n
EndWhile
EndPrgm

Then from the home screen you need to type: arch(r,a,b), where r is the number you want the square root of, and a and b are your starting numbers. Of course a and b should be 3,1 if you're finding say, sqrt(7), since the result is closer to 3 than to 2.

Question: Can you explain the bit about the error improves by a factor approaching 2 + sqrt(3)?

2. If you're finding sqrt(7), you might start with 2 if, say, you're starting off your thinking from a continued-fraction-approximation perspective, but it doesn't matter much to the algorithm, which tends to improve any reasonable approximation and will take 2:1 to 3:1 in the first few steps anyway.

on the rate of improvement:

If you compute the error after each addition step and take ratios of absolute values of successive errors, the ratio rapidly goes to that ratio. I haven't done the algebra to prove it converges at that rate.