4 ms·

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 squ

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_roots http://en.wikipedia.org/wiki/Methods_of_computing_square_roo...

jasode 12y ago
>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_roots#Digit-by-digit_calculation 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.
- wolfgke 12y ago
  Looking over it, it just seems to be a special case of building nested intervals using the monotonicity and continuity of the sqrt function.
  - ColinWright 12y ago
    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.
NAFV_P 12y ago
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).

jasode 12y ago

>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_roots#Digit-by-digit_calculation 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.

wolfgke 12y ago
Looking over it, it just seems to be a special case of building nested intervals using the monotonicity and continuity of the sqrt function.
- ColinWright 12y ago
  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.

NAFV_P 12y ago

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).