Hacker News Reader

Comment by jasode | Hacker News Reader

>Riemann's notes ..., there's a computation of sqrt(2) to 38 decimal places for no discernible purpose.

A while back I read about a mathematician taking an informal survey of other mathematicians. One of the questions was if they knew how to manually calculate square roots. (Apparently, the mathematician was part of an older generation that was taught this procedure in class.) Most mathematicians did not know how and a few responded with commentary such as "I don't need to know it in my work and if I had to, it's a procedure I could look up."

Unfortunately, I don't remember if I read about that in a book or a webpage (and google search doesn't find any hits) so I can't give a cite.

The mathematician doing the survey was including it as part of a larger essay. He was explaining a similar theme to the article's author: tedious manual computation exercises are overemphasized in the typical math education.

View on HN

I'm a bit surprised by this. Most mathematicians know Newton's method. And square roots are trivial to calculate using Newton's method:

(1) Goal: compute square root of x.

(2) Make a guess, g.

(3) Compute an updated guess, g' = (g + x/g) / 2.

(4) Repeat step (3) until you achieve the desired accuracy.

It's not incredibly quick, but it works and it's easy (though tedious) to carry out.

Lots of other fun approaches here: http://en.wikipedia.org/wiki/Methods_of_computing_square_roo...

>I'm a bit surprised by this. Most mathematicians know Newton's method.

The mathematician was probably talking about this procedure that does not require convergence:

http://en.wikipedia.org/wiki/Methods_of_computing_square_roo...

This is the method I also learned (at one time and then forgot). Apparently, this procedure was part of a typical math curriculum many decades ago. Like Latin and cursive handwriting, it's been deleted as a mandatory skill.

Looking over it, it just seems to be a special case of building nested intervals using the monotonicity and continuity of the sqrt function.

Not really. It's a generalization of the long-division algorithm. In that we remove lumps and then work on the remainder, ensuring that at each stage we've removed the largest lump possible given the number of digits we can have used so far. Then we recurse on the remainder.

In the square-root algorithm we remove the largest square possible at each stage, and work on the remainder. There's a hitch, because there's more detail to carry over at each stage. We do that with a linear factor of what we've already removed (that's the bit where we multiply the quotient so far by two) and then add the "epsilon" for the next lump to remove.

This can all be derived from first principles using the fact that (x+a)^2 = x^2 + 2ax + a^2. I did that when I was about 13.

I believe this is based on an old Greek method...

  #define DECK 11

  double z() {
    const double s=2.0, c=0.1;
    double arr[DECK], low=1.0, up=s, inc=c;
    int j, k;
    for(j=0; j<15; ++j) {
      for(k=0; k<DECK; ++k) {
        *(arr+k)=low+(double)k*inc;
      }
      for(k=1; k<DECK; ++k) {
        if( *(arr+k-1)*(*(arr+k-1)) <s && *(arr+k)*(*(arr+k)) >s ) {
          low=*(arr+k-1);
          up=*(arr+k);
          break;
        }
      }
      inc*=c;
    }
    if( s-low*low < up*up-s )
      return low;
    else
      return up;
  }

This particular example only works to fifteen decimal places (roughly the limit on the precision of a double).

There is a funny story about Gauss from the book Men of Mathematics, in which Gauss asked two of his students to compute a certain infinite series to 30 decimal places. After many days and nights, the students had a disagreement over what number was in the 30th decimal place, so they asked for help. After looking at the calculations for a few seconds, Gauss accurately pointed at the correct answer and went back to what he was doing.

That does not mean he did some tedious calculation fast. It is more likely that he understood some special property of those series to determine which number is incorrect.

Reply on news.ycombinator.com