Feeds:
Posts

## Square Root Algorithm

The “Babylonian Algorithm” for approximating square roots is a great example of a recursive function or iterative calculation.  I first encountered this method in an undergraduate Real Analysis I took at University of Maine in 2002.  The basic idea is that we make a guess for the square root of a number (let’s say $\sqrt{60}$).  So we could guess $\sqrt{60} \approx 7.5$.  Then we divide $60 \div 7.5 = 8$ and then average our guess with the result of the division $\frac{7.5+8}{2} =7.75$ and then follow the process all over again $60 \div 7.75 \approx 7.742$ and $\frac{7.75+7.742}{2} \approx 7.746$ and continue this process until the desired accuracy is achieved.  $7.746$ is actually a pretty good result for $\sqrt{60}$.

I programmed this loop onto a TI84 calculator for fun and it works quite well. Pseudocode for this looks like:

Input A

A/2 = B

While abs(A-B^2) > 0.01 do

A/B=C

(B+C)/2=B

else

Display B

Then I wondered if I could do something similar for other roots.  I tried a fifth root program, but changed the “A/B = C” to “A/B^4=C” and tried to run the program, but it ended up in an infinite loop.  Somehow the process was skipping over the fifth root I was looking for.  I started with $\sqrt[5]{32}$ just to keep it simple.  The algorithm started with large values but as it got closer to 2, it failed converge on the desired answer.  Here’s the pseudocode for my first try:

Input A

(A+1)/2 = B

While abs(A-B^5) > 0.01 do

A/B^4=C

(B+C)/2=B

else

Display B

If you try this algorithm starting with:

32/2.3^4 = 1.1435

(2.3+1.1435)/2 = 1.72175

So far so good, 1.72175 is closer than 1.1435, but when we do 32/1.72175^4 we get 3.6414 which is farther away than 2.3 was.  So I decided to take a weighted average and made the algorithm:

Input A

(A+1)/2 = B

While abs(A-B^5) > 0.01 do

A/B^4=C

(4*B+C)/5=B

else

Display B

And it worked like a charm!  Then I extended this to other roots as:

Input A

Input R

(A+1)/2 = B

While abs(A-B^R) > 0.01 do

A/B^(R-1)=C

(R-1)*B+C)/R=B

else

Display B

And again – it works great!  I haven’t figured out the problem with the original fifth root algorithm I tried, but I think that the A/B^4 introduces something that throws it off.

## Proto-Calculus

The New York Times has an interesting article about Mesopotamian mathematics.  Two-thousand-year-old clay tablets excavated in the late 19th century appear to show astronomical calculations based on the movement of the planet Jupiter.  Babylonian astronomers created a velocity-time graph and appear to have calculated the distance traveled as the area under the curve.

The original article by Mathieu Ossendrijver is posted at Science magazine.