Here's a very quick way to generate the square root of N.
Let A_{0}=N. Then generate a sequence of numbers
A_{1}, A_{2}, A_{3}, etc.
(on your calculator, for instance) by using the formula:
A_{k+1} = 1/2 ( A_{k} + (N/A_{k}) ).
This will give a sequence that converges very quickly to
the square root of N. In fact, it converges so quickly,
that it generally doubles the number of correct digits
after each step!
This formula arises as a result of using Newton's method.
Can you figure out how?
Presentation Suggestions:
Draw a picture, if it is helpful, of how Newton's method works.
Challenge them to explore what happens if you start off
with different values of A_{0}.
The Math Behind the Fact:
Repeatedly applying a function over and over is called
iteration. Iterated functions
are studied in dynamical systems.
Newton's method is one example of how iteration can be
very useful.
How to Cite this Page:
Su, Francis E., et al. "Quick Square Roots."
Math Fun Facts.
<http://www.math.hmc.edu/funfacts>.
