I would like an efficient algorithm for square root of a positive integer. Is there a reference that compares various square root algorithms? Thanks.
$\endgroup$ 44 Answers
$\begingroup$Method 1
Newton's Method converges quadratically. $a \ge 0, x_0 \ne \sqrt{a}$
$$x_{k+1} = \dfrac{1}{2}\left(x_{k} +\dfrac{a}{x_{k}}\right)$$
Method 2
$n \ge 0, x_n \gt \sqrt{a}$ for all $n \gt 0$.
$$x^2_{k+1}-a = \left[\dfrac{x^2_{k} - a}{2x_n}\right]^2$$
Method 3
Third order method, $n \ge 0$
$$x_{n+1} = \dfrac{x_n(x_n^2 + 3a)}{2x^2_n+a}$$
Method 4
See Math World Bhaskara-Brouncker algorithm
Additional Methods (also see references)
Wiki Methods of computing square roots
$\endgroup$ 4 $\begingroup$"efficient" rather depends on what you constraints are. For instance, if you have enough memory to store some floats, but little cpu time, then you can store a look up table for all integers until some power of 10. So say you had to find $\sqrt(1632397825)$. You could write: $$\sqrt{1732397825} =\sqrt{ 17*10^8 + 32397825}\sim \sqrt{17}\cdot 10^4 + \epsilon$$
To calculate $\epsilon$, use the fact that: $$\sqrt{a^2+b}\sim a + \frac{b}{2a} - \frac{b^2}{8a^3} + ...$$ So in our example, $$\sqrt{1732397825} \sim 41622.06575$$ Quite close to the true value of: $$\sqrt{1732397825}=41622.08338$$
$\endgroup$ $\begingroup$The Newton's Method will not work if you are limited to integer arithmetic, which this problem seems to presuppose.
You know for sure that $s = \sqrt{N} \in [N/2, N]$.
Start with $x = N/2$ (integer division by 2) and check:
- if $x^2 = N$, you are done;
- if $x^2 < N$, you know that $s \in [x,N]$;
- if $x^2>N$ then you know $s \in [N/2,x]$.
Set $s$ to be the midpoint of the resulting interval and repeat the previous step.
The idea is to split the interval in half each iteration. The running time is worst-case $\log(N)$.
$\endgroup$ 2 $\begingroup$You can use the Binomial Expansion to calculate square roots and other fractional powers. Since most square roots are irrational you get an infinite series, which you truncate to give you whatever level of accuracy/precision you require.
The Binomial Expansion only converges for |x| < 1 , so to get round this restriction take out a factor p where p is the largest perfect square ( or cube and so on... ) below s the number whose fractional index you are trying to evaluate.
For example for s = 5 the largest perfect square below it is 4 so
√5 = √4*√(1+1/4) here x is 1/4 satisfying the condition for convergence.The first few terms for √5 are:
√5 = √4[1 + 1/2*1/4 - 1/2*(1/4)²/2 + …… ]
√5 = 2(1 + 1/8 - 1/64 + …… )
