## Wednesday, January 17, 2007

### Computing Square Roots

My daughter learned about square roots and she did her homework taking those roots using a calculator. She asked me how to compute the square root without using a calculator.

I actually learned this procedure in the mid-70's, probably the last generation to do so. But unlike long division or Euclid's Algorithm, I quickly forgot how to compute square roots since the process was quite cumbersome, one didn't have to take square roots that often and reasonably priced calculators appeared soon thereafter. Almost no one even 50 years ago used the manual method for square roots, using slide rules or log tables instead.

I rarely even use calculators today. I find square roots like I find out anything else, praying to the Google Gods.

1. Sans computer, I often find myself using the manual method to calculate square roots (or any kind of root). It usually only takes a few iterations to have a fairly high degree of accuracy. Oftentimes it's faster than hunting around for a calculator or walking over to the PC.

2. But surely there are still some interesting theoretical aspects to calculating roots, no? For example, what is the complexity of comparing two expressions involving sums of roots, etc.

3. When I saw the title of this post I was hoping to read about a a breakthrough in the Sum of Square Roots problem. Alas, it was not to be. So yes, to answer Kurt's question, there are still significant open problems.

4. There is only one and its a she:

5. I also learned this method, and it is definitely the best if you don't have any electronics handy. About a decade ago, I taught a class using Abelson and Sussman's Structure and Interpretation of Computer Programs (the best programming book ever written, IMHO), and to test the use of lazy streams I implemented this method in Scheme (sqrt.scm using stream.scm). It originally ran under PC Scheme.

6. Uh, whatever happened to the most obvious guess-and-verify with a dash of binary search or interpolation search? I feel it's OK if children don't remember the sqrt algorithm, but faced with a non-electronics situation, I'd hope that they have enough mathematical intuition to do a decent guess and verify...

7. In India, we still dont use a calculator till we start BS as freshmen. In 11th and 12th, we use something called Clark's tables. Using logarithm tables to calculate roots, power, multiplication, etc.

A graphical calculator is unheard of !

8. I learned the method from a 1928 Audels New Electric Library book. This was a series of self sudy books to learn electronins (well, electricity) my father had. It was clear how to generalize the algo to nth roots. I've impressed many a junior engineer with the fact this algo even exists.

9. It's just Newton's Method, dude...

10. I feel it's OK if children don't remember the sqrt algorithm, but faced with a non-electronics situation, I'd hope that they have enough mathematical intuition to do a decent guess and verify...

What do you think about other rote hand algorithms, such as long division and the usual shift-and-add method of multiplication? I ask because there are movements afoot to forgo teaching these in favor of developing the grade school student's "mathematical intuition." I think it's a terrible idea to do this.

11. I agree with comment 9: Using Newton's
method to compute square roots is fast
and easy. To find the square root
of a, make an inital guess x_1, and
use the iteration formula that x_{n+1}
is the average of x_n and a/x_n.
The number of significant digits doubles with each iteration.

12. After praying books.google.com god, we get:
which gives a description of sqrt algorithm -

13. In response to the comment
I feel it's OK if children don't remember the sqrt algorithm, but faced with a non-electronics situation, I'd hope that they have enough mathematical intuition to do a decent guess and verify...

What do you think about other rote hand algorithms, such as long division and the usual shift-and-add method of multiplication? I ask because there are movements afoot to forgo teaching these in favor of developing the grade school student's "mathematical intuition." I think it's a terrible idea to do this.

As long as a student understands why she is doing what she is doing, any algorithm is fine -- in other words, if you're going to hand-execute an algorithm, you should at least have a good sense of the proof of correctness of the algorithm, at least intuitively. I think the correctness of the shift-and-add multiplication algorithm is relatively easy to see, for someone at the 4th -- 6th grade level. The correctness of long division (and of the sqrt algorithm) is a lot less obvious, and this is why I feel that recursive doubling or binary search or other forms of guess-and-verify are more reasonable, since the student has a better chance of internalizing the correctness argument with every execution. For the same reason, I think I like multiplying by appealing to the distributivity of multiplication over addition, as in 378 * 74 = (300 + 70 + 8) * (70 + 4) = 300*70 + 300*4 + 70*70 + 70*4 + 8*70 + 8*4 = whatever... while executing this, a student can mentally compute the area of a rectangle with 378 x 74 cells, which he slices as 300+70+8 in one direction, and dices as 70+4 in the other...

Teaching the long division or sqrt algorithm is a great exercise in developing the notion of a correctness proof (at least, an argument of correctness), and is probably a good topic for early high school, about 9th or 10th grade.

Siva

14. Siva says,

Teaching the long division or sqrt algorithm is a great exercise in developing the notion of a correctness proof ..., and is probably a good topic for early high school, about 9th or 10th grade.

The sqrt algorithm is perhaps appropriate for 9th or 10th grade, but long division? Long division (and shift-and-add multiplication as well) should be taught much earlier and learned by rote. Let the correctness idea come later. The great benefit of this approach is that the student can do these operations quickly and without thinking. They can then use these skills (for example) in further mathematical discovery, such as prime factorizations of numbers.

15. The technique isn't Newton's method.
Newton's method is slow by hand because of all those divisions by x_n; the method Lance links to (which my middle-school math teacher enjoyed showing when he could) is much better optimized for pencil-and-paper work. Check it out if you've never seen it.

Googling finds another exposition with a good discussion in the comments of when this method makes more sense and when Newton's method (apparently aka "the Babylonian method" when specialized to square roots) does.

16. ..and the BBC's take on it.

17. Is it possible to download pages of square/square roots and cube roots tables from the 'CRC' Mathematical Tables? Are they available on Google? I want my students to learn from them.