Square roots

[PhDP]

...are computer using the Newton-Raphson method to evaluate square roots ?

[Klaynos]

I'm assuming you mean when you put them in a calculator or whatever?

 

Well tbh I don't know, are there any other computational methods for finding square roots other than minimising? If not then they might use the N-R method, but there's lots of others, my fitting code atm uses the Broyden-Fletcher-Goldfarb-Shanno (BFGS) method

[PhDP]

... well for example, if I ask Java, or Mathematica, to find a square root. Are they using the Newton-Raphson ?

[5614]

Does the Mathematica help file (or some other relevant documentation) not tell you? Also Mathematica will call on a square root function (from a standard library), whenver you type in sqrt (or whatever the command is), can you not view the code of the function and thus try to deduce what method it is using?

 

Although it may be obvious from what I just said, I'm not familiar with Mathematica yet, but have used other similar software packages (Matlab, Maple etc.).

[Klaynos]

I don't know and can't find it in the java docs atm :|

 

But it could be done using that or one of any number of optimising methods... or it could be done using log...

[John Cuthber]

I once asked a mathematician and he said he thought they used these.

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

However I have practically no idea what they are or how they work.

[Klaynos]

ah, polynomial sets like that scare the living daylights out of me...

[D H]

Computers almost exclusively use the IEEE floating point standard to represent real numbers. The number is represented in the form sign*(1+fraction)*2^(exponent). Except for very tiny numbers, the "1+" of the mantissa is implied (i.e., not stored). I won't deal with those tiny ("unnormalized") numbers.

 

The very first thing that is done is a gross check on the number. Negative numbers and numbers that are "Not a Number" don't have a square root. The result is "Not a Number". The square root of a positive infinity is positive infinity. The square root of zero is zero. That just leaves positive numbers to deal with.

 

Using the fact that the square root of x*2^(2n) is sqrt(x)*2^n, the first thing that is done is to scale the number by an even power of two to place the result between 0.25 and 1 (or 0.5 and 2, or 1 and 4; it doesn't matter). Then an initial guess of the square root is made. This guess is polished off by Newton's method.

 

The better the guess, the less polishing needed. Newton's method exhibit quadratic convergence near the root. I suspect that most developers use either a Chebychev polynomial or a rational polynomial. What constitutes a good guess function is just a bit of art and a bit of math. The function should use a minimal number of operations to yield a minimax estimate. The minimax criterion for things like sqrt, sin, etc is not RMS (root mean square). A function can have a low RMS error over a range but still might well perform poorly in some subrange. The minimax criterion is instead worst-case error. Chebychev approximations typically come very close to the optimal minimax polynomial. Rational polynomials with the same computation cost are often better than the optimal minimax polynomial, but finding the optimal minimax rational polynomial is an absolute bear of a problem. All of this work is done by the algorithm designer; once built the coefficients are just magic numbers (defined constants) in the function implementation.