Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

What is the fastest algorithm for finding the square root of a number?

I created one that can find the square root of "987654321" to 16 decimal places in just 20 iterations (I'm not ready to release it just yet)...

I've now tried Newton's method as well as my own method (Newtons code seen below)

What is the fastest known algorithm for taking the second root of a number?

My code for Newton's Method (*Edit: there was an error in my code, it is fixed in the comments below):

a=2//2nd root
b=97654321//base
n=1//initial guess
c=0//current iteration (this is a changing variable)
r=500000 //total number of iterations to run
while (c<r) {
    m = n-(((n^a)-b)/(a*b))//Newton's algorithm
    n=m
    c++;
    trace(m + "  <--guess   ...   iteration-->  " + c)
}
share|improve this question
4  
Your attempt with Newton's method sounds unrealistic: Newton / Heron has quadratic convergence. Even starting with $x_0=1$ gives an error $<10^{-24}$ after 20 iterations. –  Hagen von Eitzen Feb 6 '13 at 6:55
2  
There is no way it could take 100,000 iterations with Newton's method. You need more precision. –  copper.hat Feb 6 '13 at 6:59
    
Have you seen these methods ? en.wikipedia.org/wiki/Methods_of_computing_square_roots –  sonystarmap Feb 6 '13 at 7:09
1  
Jeez, you couldn't be bothered to compare your code with Hagen's answer yourself? You need a*n instead of a*b in the denominator. –  Rahul Feb 6 '13 at 7:26
2  
check out this post on SO stackoverflow.com/questions/295579/… It shows the fastest way to find the square root and to check if it an integer or not. –  gekkostate Feb 6 '13 at 11:27

9 Answers 9

up vote 8 down vote accepted

If you use Halley's method, you exhibit cubic convergence! This method is second in the class of Householder's methods.

Halley's method is: $$ x_{n+1} = x_n - \frac{2f(x_n)f'(x_n)}{2[f'(x_n)]^2-f(x_n)f''(x_n)} $$ If we let $$f(x) = x^2 - a$$ which meets the criteria, (continuous second derivative)

Then Halley's method is:

$$ x_{n+1} = x_n - \frac{\left(2x_n^3 - 2ax_n\right)}{3x_n^2 + a} $$ Which has the simplification: $$ x_{n+1} = \frac{x_n^3 + 3ax_n}{3x_n^2 + a} $$ I also will add this document which discusses extensions of the newtonian method.

There exists an extension due to Potra and Pták called the “two-step method” that may be re-written as the iterative scheme $$x_{n+1} =x_n − \frac{f(x_n)+f\left(x_n − \frac{f(x_n)}{f′(x_n)}\right)}{f'(x_n)}$$ that converges cubically in some neighborhood of of the root $x^{*}$ which does not require the computation of the second derivative.

See: On Newton-type methods with cubic convergence for more information on this topic.

As Hurkyl and others have noted, your best bet is to just use Newton's Method. These alternative methods generally come with more operations per iteration. They aren't really worth the computational cost, but they are a good comparison.

share|improve this answer
    
The householder method is the fastest known algorithm? –  Albert Renshaw Feb 6 '13 at 7:31
    
@AlbertRenshaw I'm not sure if it is the fastest algorithm_ but you should check out the article I included. Cubic convergence is really good, especially if you don't need the second derivative. –  Rustyn Feb 6 '13 at 7:40
5  
You can do even better: there's an easy way to get quartic convergence: each iteration, you do two steps of Newton's algorithm. :) Cubic convergence means you only need 2/3 as many iterations as quadratic convergence, but that isn't helpful if each iteration takes 3/2 times as long or more. –  Hurkyl Feb 6 '13 at 7:44
    
@Hurkyl I would agree, Newton's method is pretty much the most efficient route. I wanted to include other methods so that he could compare. –  Rustyn Feb 6 '13 at 7:46
1  
@Hurkyl: I've been focusing on the former actually. But after benchmarking, I found this method to be slower - the overhead of the additions, squarings and multiplications is just not worth saving a division (on x64 with SSE, that is). –  nightcracker Feb 7 '13 at 17:49

Newton's method for solving $f(x)=x^2-N=0$ leads to the recurrence $x_{n+1}=x_n-\frac{x_n^2-N}{2x_n}=\frac{x_n+N/x_n}2$, also known as Heron's method. Since $f'(x)\ne0$ at the root, the convergence is quadrattic (i.e. the number of correct decimals doubles with each step once a threshold precision is reached). The results depend on the starting value, of course. Simply guessing $x_0=1$ leads to $$x_{1} = 493827161.00000000000\\ x_{2} = 246913581.49999999899\\ x_{3} = 123456792.74999998937\\ x_{4} = 61728400.374999909634\\ x_{5} = 30864208.187499266317\\ x_{6} = 15432120.093744108961\\ x_{7} = 7716092.0468278285538\\ x_{8} = 3858110.0230600438248\\ x_{9} = 1929183.0086989850523\\ x_{10} = 964847.48170274167713\\ x_{11} = 482935.55973452582660\\ x_{12} = 242490.33277426247529 \\ x_{13} = 123281.64823302696814 \\ x_{14} = 65646.506775513694016 \\ x_{15} = 40345.773393104621684 \\ x_{16} = 32412.760144718719221 \\ x_{17} = 31441.958847358050036 \\ x_{18} = 31426.971626562861740 \\ x_{19} = 31426.968052932067262 \\ x_{20} = 31426.968052931864079 $$
with small enough error.

share|improve this answer
    
I found my error in Newtons method now! I coded it wrong, thank you! +1 Do you know of algorithms faster than this one? –  Albert Renshaw Feb 6 '13 at 7:30
    
If the representation of your number x allows this, begin with a number with half of the number of digits of x (where the digits left of the decimal point are taken). Then in Hagen's list you step in immediately at $x_{17}$ ... (take care: you've given $97654321$ while Hagen uses $987654321$ ) –  Gottfried Helms Feb 6 '13 at 8:00

Not a bona fide "alogrithm", but a cute hack nevertheless that I once used in code that required taking an inverse square root millions of times (back when I was doing computational astrophysics) is found here:

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

It does use a few iterations of Newton's method, but only after some very, very clever trickery.

I remember naively using trial-and-error optimization to find a "magic number" that would come closest to a direct square root, though of course it was much slower (still faster than just called "sqrt" from math.h) and had a higher error than the above hack.

share|improve this answer
    
Pretty neat. ${}{}{}$ –  copper.hat Feb 6 '13 at 7:35
    
The only bad line is the line with the "what the fuck?" comment –  BЈовић Feb 6 '13 at 9:57
    
That's the line where the "more magic" does its work. –  Joe Z. Feb 6 '13 at 13:46

I just noticed nobody's pointed out the following trick: to compute $1/\sqrt{n}$, Newton's method used to find a root of $f(y) = 1/y^2 - n$ gives the iteration

$$ y \leftarrow \frac{3y - ny^3}{2}$$

I believe that in some ranges, it is faster to compute an estimate of $\sqrt{n}$ by using Newton's method to first compute $1/\sqrt{n}$ then invert the answer than it is to use Newton's method directly.

It is likely faster to compute this as

$$ \frac{3y - ny^3}{2} = y - \frac{n y^2 - 1}{2}y$$

The point being that if $y$ is a good approximation of $1/\sqrt{n}$, then $n y^2 - 1$ is a good approximation of $0$, which reduces the amount of precision you need to keep around, and you can play tricks to speed up the calculation of a product if you already know many of its digits.


But it's possible you might be able to do even better by computing an approximation of both $x \sim \sqrt{n}$ and $y \sim 1/\sqrt{n}$ simultaneously. I haven't worked through the details.

The reason to hope that this might work out is that a better update calculation for $x$ may be available because $ny \sim n/x$, and then a faster way to update $y$ based on $y \sim 1/x$ rather than $y \sim 1/\sqrt{n}$.

share|improve this answer

A related problem. You can use the Taylor series of $\sqrt{x}$ at a point $a$

$$ \sqrt{x} = \sum _{n=0}^{\infty }\frac{\sqrt {\pi }}{2}\,{\frac {{a}^{\frac{1}{2}-n} \left( x-a\right)^{n}}{\Gamma\left( \frac{3}{2}-n \right)n! }}. $$

If you pick $a$ to be close to $987654321$, say $ a=987654320 $, then you get fast convergence.

share|improve this answer
    
Hey, how do you calculate $\pi$ and $\Gamma(x)$ quickly in computer? –  Frank Science Feb 6 '13 at 9:44
    
@FrankScience: well you'd hardcode Pi of course. The gamma function is the largest hurdle here, I think. –  nightcracker Feb 6 '13 at 10:59

In case you meant not the theoretical speed but the algorithm that runs the fastest on a computer, then it's the "quake 3" algorithm or one of its derivatives which, I believe, is implemented as the GCC's sqrt function at optimization levels 2 and 3. It's ironic that the determining factor here is a clever value and implementation of the initial condition rather than the actual iterative scheme. On my normal laptop it takes about 2.0e-09s to call sqrt with gcc -O2 or gcc -O3, which is about 2.8 times less than what the runner up, the standard implementation of sqrt gives.

share|improve this answer

You can get 20 exact digits with only 3 iterations, but it require a better initial guess ( do not use X0=1 ) This guess is easy to find with a simple table of square roots between 1 and 100. Then you start with 3,16 x 10^4 for X0... Apply Newton/Hero 3 times, and you get: 31426,968052931864079... that's 20 correct digits! Hello again, With my " 101 Dalmatians " algoritm, I can get 5 exact digits with 1 iteration. and 15 exact digits with only 2 Newton/Heron iterations. I use linear interpolation and second order polynomial to find a very good initial guess. I use also a "lookup" in a simple table from 1 to 101, with 4 digits accuracy. It is very fast...but an assembly langage code will do beter of course.

share|improve this answer
    
Here's a MathJax tutorial :) –  Shaun Oct 15 at 17:47

Babylonian algorithm.

To determine square root of a.

$ x_{n+1} = \frac{1}{2}(x_n + \frac{a}{x_n}) $

Exponential convergence with $x_0 \approx \sqrt{a} $. Results independent of starting value $x_0$, shows fastest possible convergence. http://en.wikipedia.org/wiki/Methods_of_computing_square_roots#Babylonian_method

share|improve this answer
1  
Babylonian method is newton's method –  Rustyn Feb 6 '13 at 7:44
    
Yes, but is it the best known? Or Householder's? –  Vigneshwaren Feb 6 '13 at 7:50
    
Babylonian will do fine. I'm not sure which is faster in the long run. –  Rustyn Feb 6 '13 at 7:55

See the following results for square root calculation with my algorithm , requires only ~ 12 iteration almost half iteration than any other standard algorithms:

Iternation# Number Square Root (16 places of decimal) 1 987654321 164609055.2777780000000000 2 987654321 54869690.4259258000000000 3 987654321 18289912.8086385000000000 4 987654321 6096685.6027850700000000 5 987654321 2032372.5317110300000000 6 987654321 677889.4417104440000000 7 987654321 227257.2910823490000000 8 987654321 79591.0491430332000000 9 987654321 37015.7432756257000000 10 987654321 31461.2083333879000000 11 987654321 31426.9680630765000000 12 987654321 31426.9680529319000000

share|improve this answer
2  
And what is your algorithm? –  rlartiga Apr 30 at 19:10
2  
What's the algorithm? –  Albert Renshaw Apr 30 at 19:42

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.