Square Root Algorithm

Solution 1:

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

Solution 2:

"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$$