There are many methods to compute square roots. Below is a list and explanation of other methods that have been discovered throughout the history of human mathematical study.

Exponential identity

---

Pocket calculators typically implement good routines to compute the exponential function and the natural logarithm, and then compute the square root of $x$ using the identity

$\backslash sqrt\{x\}\; =\; e^\{\backslash frac\{1\}\{2\}\backslash ln\; x\}$.

The same identity is exploited when computing square roots with logarithm tables or slide rules.

Babylonian method

---

A commonly used algorithm for approximating $\backslash sqrt\; r$ is known as the "Babylonian method" and can be derived from (but predates) Newton's method. It proceeds as follows:

1. Start with an arbitrary positive start value $x$ (the closer to the root, the better).
2. Replace $x$ by the average of $x$ and r/x.
3. Repeat steps 2 and 3.

This is a quadratically convergent algorithm, which means that the number of correct digits of $r$ roughly doubles with each step. It can also be represented as:

$x\_\{n+1\}\; =\; 0.5\; (x\_n\; +\; \backslash frac\{r\}\{x\_n\})$

$\backslash lim\_\{n\; \backslash to\; \backslash infty\}\; x\_n\; =\; \backslash sqrt\; r$.

This algorithm works equally well in the p-adic numbers, but cannot be used to identify real square roots with p-adic square roots; it is easy, for example, to construct a sequence of rational numbers by this method which converges to $+3$ in the reals, but to $-3$ in the 2-adics.

A similar method is also mentioned by the Arab Mathematician Ibn al-Banna in his works.

Simple approximation

---

The simple approximation method is rather simple and can be highly inaccurate, always giving results greater than the actual value. The amount of inaccuracy for this approximation is dependent on the value of the expression d/2N , the larger the value of this expression, the more inaccurate the value of the approximated result.

Construction

If N > 0 and d > 0 then

So the solution for $\backslash sqrt\{N^2\; +\; d\}$ must be between $(N)$ and $(\; N\; +\; \backslash frac\{d\}\{N\})$

$\backslash sqrt\{N^2\; +\; d\}\; \backslash ,\; \backslash approx\; \backslash ,$average$(\; N\; ,\; N\; +\; \backslash frac\{d\}\{N\}\; )$

$\backslash sqrt\{N^2\; +\; d\}\; \backslash ,\; \backslash approx\; \backslash ,\; \backslash frac\{1\}\{2\}\; \backslash left(\; N\; +\; N\; +\; \backslash frac\{d\}\{N\}\; \backslash right)$

Thus

$\backslash sqrt\{N^2\; +\; d\}\; \backslash ,\; \backslash approx\; \backslash ,\; N\; +\; \backslash frac\{d\}\{2\backslash ,N\}$

Example:

To approximate the square root of 39, replace 39 with the sum of a known square plus $d$ (in this case $39\; =\; 36\; +\; 3$).

$\backslash sqrt\{39\}\; =\; \backslash sqrt\{36\; +\; 3\}\; \backslash ,\; \backslash approx\; \backslash ,\; 6\; +\; \backslash frac\{3\}\{12\}\; \backslash ,\; \backslash approx\; \backslash ,\; 6.25$

Bakhshali approximation

---

The Bakhshali square root approximation is a mathematical method for finding an approximation to a square root which was described in an ancient manuscript, written in ancient India sometime between the 200 BC and the 400 CE, known as the Bakhshali Manuscript because it was discovered in 1881 near the village of Bakhshali (or Bakhshalai) in the Yusufzai subdivision of the Peshawar district (now part of Pakistan). The manuscript was made out of the leaves of birch bark tree and was written in the Sarada script.

The Bakhshali square root approximation is just the simple approximation applied twice. This gives the same result as using the simple approximation as an initial value to Newton's method, then doing just one step of the Newton's method. It is just a little slower to compute than Newton's.

Let $P\; \backslash ,=\backslash ,\; \backslash frac\{d\}\{2\; N\}$

Let $A\; =\; N\; +\; P$

$\backslash sqrt\{N^2\; +\; d\}\; \backslash approx\; A\; -\; \backslash frac\{P^2\}\{2\; A\}$

When expanded, the equation becomes

$\backslash sqrt\{N^2\; +\; d\}\; \backslash approx\; N\; +\; \backslash frac\{d\}\{2\backslash ,N\}\; -\; \backslash frac\{d^2\}\{8\backslash ,N^3\; +\; 4\backslash ,N\backslash ,d\}$

Example

Find $\backslash sqrt\{9.2345\}$

Using $N=3$ and $d\; =\; 9.2345\; -\; 3^2\; =\; 0.2345$

$\backslash sqrt\{3^2\; +\; d\}\; \backslash approx\; 3\; +\; \backslash frac\{d\}\{6\}\; -\; \backslash frac\{d^2\}\{216\; +\; 12\backslash ,d\}$

$\backslash sqrt\{3^2\; +\; 0.2345\}\; \backslash approx\; 3\; +\; \backslash frac\{0.2345\}\{6\}\; -\; \backslash frac\{0.2345^2\}\{216\; +\; 12\; \backslash cdot\; 0.2345\}$

$\backslash sqrt\{3^2\; +\; 0.2345\}\; \backslash approx\; 3\; +\; 0.039083\; -\; \backslash frac\{0.055\}\{216\; +\; 2.814\}$

$\backslash sqrt\{3^2\; +\; 0.2345\}\; \backslash approx\; 3\; +\; 0.039083\; -\; 0.000251$

$\backslash sqrt\{3^2\; +\; 0.2345\}\; \backslash approx\; 3.038832$

We can get to the same result faster if we do not use the expansion:

$P\; =\; 0.2345/(2*3)\; =\; 0.039083$

$A\; =\; 3\; +\; P\; =\; 3.039083$

$result\; =\; 3\; -\; 0.039083^2/(2*A)\; =\; 3.038832$

And we can save one multiplication if instead of using this last line we compute the result directly by Newton's formula, like this:

$result\; =\; (\; A\; +\; 9.2345\; /\; A\; )/2\; =\; 3.038832$

this always gives the exact same result.

An exact long-division-like algorithm

---

This method, while much slower than the Babylonian method, has the advantage that it is exact: if the given number has a square root whose decimal representation terminates, then the algorithm terminates and produces the correct square root after finitely many steps. It can thus be used to check whether a given integer is a square number.

Write the number in decimal and divide it into pairs of digits starting from the decimal point. The numbers are laid out similar to the long division algorithm and the final square root will appear above the original number.

For each iteration:

1. Bring down the most significant pair of digits not yet used and append them to any remainder. This is the current value referred to in steps 2 and 3.
2. If $s$ denotes the part of the result found so far, determine the greatest digit $x$ that does not make $y\; =\; x(20s\; +\; x)$ exceed the current value. Place the new digit $x$ on the quotient line.
3. Subtract $y$ from the current value to form a new remainder.
4. If the remainder is zero and there are no more digits to bring down the algorithm has terminated. Otherwise continue with step 1.

Example: What is the square root of 152.2756?

1 2. 3 4 | 01 52.27 56 1 The digit 1 is a solution digit x 01 1(20*0+1)=1 +1 00 52 22 The digit 2 is a solution digit 2x 00 44 2(20*1+2)=44 + 2 08 27 243 The digit 3 is a solution digit 24x 07 29 3(20*12+3)=729 + 3 98 56 2464 The digit 4 is a solution digit 246x 98 56 4(20*123+4)=9856 4 00 00 Algorithm terminates: answer is 12.34

Although demonstrated here for base 10 numbers, the procedure works for any base, including base 2. In the description above, 20 means double the number base used, in the case of binary this would really be 100. The algorithm is in fact much easier to perform in base 2, as in every step only the two digits 0 and 1 have to be tested. Napier's bones used this algorithm. See also Shifting nth-root algorithm.

Rough estimation

---

Many of the methods used for finding the square root of a number requires an initial seed value which should ideally be close to the actual value of the square root. One way of obtaining a very rough estimate of the value of the square root is as follows.

Provided that r » 1

Steps

1. Take the integer part of the number r. Z = int(r)
2. Count the number of digits in Z. Let D be the number of digits.
3. The rough estimate is E = 3^D.

Example

r	Z	D	Estimate = 3D	Actual Value of √r
723.47	723	3	27	26.89
5396.37	5396	4	81	73.45
24956.41	24956	5	243	157.97
789345.464	789345	6	729	888.45

More accurate rough estimation

---

Similar to the rough estimation procedure above. This version is slightly more accurate because it also uses the additional information provided by the first digit of the number r. The steps are almost the same as the one for previous rough estimate. This estimate can then be improved by any iterative method.

Provided that r » 1

Steps

1. Take the integer part of the number r. Z = int(r)
2. Count the number of digits in Z. Let D be the number of digits.
3. Calculate the value of 3.16^D. Note: 3.16 ≈ √10
4. The estimate is the value obtained in step 3 multiplied by an adjustment factor based on the first (left most) digit of the number n:
   E = ADJ * 3.16^D

Table of ADJ

First Digit	1	2	3	4	5	6	7	8	9
ADJ	0.382	0.497	0.590	0.670	0.741	0.806	0.866	0.922	0.974

where the derivation of the adjustment is the average of the square root of first digit and the square root of the first digit incremented by one, all divided by √10.

The accuracy of this method is very dependant on the number's first digit. Due to logrithmic spacings, errors for numbers starting with a "1" can range up to 18 percent, while errors for numbers starting with a "9" are less than 3 percent.

Example

r	Z	D	3.16 ^ D	ADJ	Estimate (E)	Actual Value of √r
723.47	723	3	31.55	0.866	27.32	26.90
5396.37	5396	4	99.71	0.741	73.89	73.46
24956.41	24956	5	315.09	0.497	156.60	157.98
789345.464	789345	6	995.7	0.866	862.28	888.45
198764.389	198764	6	995.7	0.382	380.36	445.83

Inverse square root approximation

---

There is an algorithm for finding the inverse square root $\backslash left(\; \backslash frac\{1\}\{\backslash sqrt\{r\}\}\backslash right\; )$ very quickly.

Because $\backslash sqrt\{r\}\; =\; r\; \backslash times\; \backslash left\; (\; \backslash frac\{1\}\{\backslash sqrt\{r\}\}\; \backslash right\; )$, if we know the value of the inverse square root, we can easily get the value for the square root.

Steps for inverse square root approximation

Step 1 Start the initial value $X\_0$ an approximate value of the inverse square root which is accurate to 2 significant digits.

$X\_0\; =\; \backslash left(\; \backslash frac\{1\}\{\backslash sqrt\{r\}\}\; \backslash right\; )\_\backslash mbox\{approx\}$

Step 2 Calculate the next iteration with the following algorithm.

$X\_\{n+1\}\; =\; X\_n\; \backslash ,\; \backslash left(\; \backslash frac\{15\}\{8\}\; -\; Y\_n\; \backslash ,\; \backslash left\; (\; \backslash frac\{5\}\{4\}\; -\; \backslash frac\{3\}\{8\}\; \backslash ,\; Y\_n\; \backslash right\; )\; \backslash right\; )$ where $Y\_n\; =\; r\; \backslash ,\; X\_n^2$

Step 3 Finally obtain the value of $\backslash sqrt\{r\}$ with

$\backslash sqrt\{r\}\; =\; r\; \backslash ,\; X\_\{infinity\}$

Because $X\_\{infinity\}$ would converge to the value of the inverse square root of r.

Example

Find the $\backslash sqrt\{7\}$

Step 1 Find initial value $X\_0$ using Bakhshali square root approximation.

$\backslash sqrt\{7\}\; =\; \backslash sqrt\{2^2+3\}\; =\; \backslash sqrt\{N^2+d\}$

$P\; \backslash ,=\backslash ,\; \backslash frac\{d\}\{2\; N\}\; \backslash ,=\backslash ,\; \backslash frac\{3\}\{4\}$

$A\; =\; N\; +\; P\; \backslash ,=\backslash ,\; \backslash frac\{11\}\{4\}$

$\backslash sqrt\{N^2\; +\; d\}\; \backslash approx\; A\; -\; \backslash frac\{P^2\}\{2\; A\}\; \backslash approx\; \backslash frac\{12500\}\{4721\}\; \backslash approx\; 2.64773$

$X\_0\; =\; \backslash frac\{1\}\{2.64773\}\; =\; 0.37768$

Step 2 Calculate the next iteration with the following algorithm.

$X\_\{n+1\}\; =\; X\_n\; \backslash ,\; \backslash left(\; \backslash frac\{15\}\{8\}\; -\; Y\_n\; \backslash ,\; \backslash left\; (\; \backslash frac\{5\}\{4\}\; -\; \backslash frac\{3\}\{8\}\; \backslash ,\; Y\_n\; \backslash right\; )\; \backslash right\; )$ where $Y\_n\; =\; r\; \backslash ,\; X\_n^2$

$Y\_0\; =\; 7\; *\; X\_0^2\; =\; 7\; *\; 0.37768^2\; =\; 0.9984952768$

$X\_1\; =\; 0.377964472606588$

$Y\_1\; =\; 7\; *\; X\_1^2\; =\; 7\; *\; 0.377964472606588^2\; =\; 0.99999999786943356769463711$

$X\_2\; =\; 0.3779644730092272272145165350918641$

$Y\_2\; =\; 7\; *\; X\_2^2\; =\; 7\; *\; 0.3779644730092272272145165350918641^2\; =\; 0.99999999786943356769463711$

$X\_3\; =\; 0.37796447300922722721451653623418$

Step 3 Finally obtain the value of $\backslash sqrt\{r\}$

$\backslash sqrt\{7\}\; \backslash approx\; 7\; *\; X\_3\; \backslash approx\; 2.64575131106459059050161575363926$

Properties

The greatest weakness of this algorithm is that it is not stable. The initial value $X\_0$ must be near the actual value for the algorithm to converge correctly. If the initial value is not close enough, the algorithm will diverge away from the actual value.

However when the algorithm converges, it converges quickly. 20 digits of accuracy can be obtained in 6 iterations.

Square roots using Newton iteration

---

Basic Newton iteration finds a single root of a function $f(x)$ given a sufficiently precise approximation to the root. The nature of which root will be given based on an approximation is dependent on the Newton fractal. The basic iteration is given by:

$x\_\{n+1\}\; =\; x\_n\; -\; \{f(x\_n)\; \backslash over\; f^\backslash prime(x\_n)\}$.

There are two widely used functions $f(x)$ and $g(x)$ used to find the square root of a number denoted by "z".

(See also: Newton's method, Integer square root.)

First method

The first method finds the square root of "z"

$f(x)\; =\; x^2\; -\; z\; \backslash ,$

Note that both $\backslash sqrt\{z\}$ and $-\; \backslash sqrt\{z\}$ are roots of the function $f(x)$. ie $f(\; \backslash sqrt\{z\}\; )\; =\; 0$.

The first derivative of $f(x)$ is $f^\backslash prime(x)\; =\; 2\; x$

Thus iteration for $x\_\{n+1\}$ is derived where:

$x\_0\; =\; 1\; \backslash ,\backslash ,\backslash ,$        and

$x\_\{n+1\}\backslash ,\backslash !$	$=\; x\_n\; -\; \{f(x\_n)\; \backslash over\; f^\backslash prime(x\_n)\}$
	$=\; x\_n\; -\; \{(x\_n^2\; -\; z)\; \backslash over\; 2\; x\_n\}$
	$=\; x\_n\; -\; \backslash frac\; \{x\_n\}\{2\}\; +\; \backslash frac\; \{z\}\{2\; \backslash ,\backslash ,\backslash ,\; x\_n\}$
	$=\; \backslash frac\; \{x\_n\}\{2\}\; +\; \backslash frac\; \{z\}\{2\; \backslash ,\backslash ,\backslash ,\; x\_n\}$.

So this simplifies to the Babylonian method described above.

Second method

The second method finds the reciprocal of the square root of "z".

$g(x)\; =\; \backslash frac\{1\}\{x^\{2\}\}\; -\; z$.

The two roots to $g(x)$ are $\backslash frac\{1\}\{\backslash sqrt\{z\}\}$ and $\backslash frac\{-1\}\{\backslash sqrt\{z\}\}$.

The derivative of $g(x)$ is $g^\backslash prime(x)\; =\; -2\; x^\{-3\}$.

Thus iteration for $x\_\{n+1\}$ is derived where:

$x\_0\; =\; 0.5$        and

$x\_\{n+1\}\; \backslash ,\backslash !$	$=\; x\_n\; -\; \{g(x\_n)\; \backslash over\; g^\backslash prime(x\_n)\}$
	$=\; x\_n\; -\; \{x\_n^\{-2\}\; -\; z\; \backslash over\; -2\; x\_n^\{-3\}\}$
	$=\; x\_n\; -\; (-1/2)\; \{x\_n^3\}\; (x\_n^\{-2\}\; -\; z)$
	$=\; x\_n\; +\; (1/2)\; (x\_n\; -\; z\; x\_n^3)$
	$=\; \backslash frac\{\; 3\; x\_n\; -\; z\; x\_n^3\; \}\{2\}$
	$=\; 1.5\; \backslash ,\; x\_n\; -\; 0.5\; \backslash ,\; z\; x\_n^3\; =\; 0.5\; \backslash ,\; x\_n\; \backslash ,\backslash ,\; (\; 3\; -\; z\; x\_n^2\; )$.

The square root of "z" can be found by multiplying the number just computed by "z", so this method does not require any division at all.

Example

Find the $\backslash sqrt\{7\}$ using both methods.

$z\; =\; 7\; \backslash ,$ Because we are looking for the square root of 7

$f(x)\backslash ,$		$g(x)\backslash ,$
$x\_0\backslash ,$	$1\backslash ,$	$x\_0\backslash ,$	$0.5\backslash ,$
$x\_1\backslash ,$	$\backslash frac\{1\}\{2\}\; +\; \backslash frac\{7\}\{2\; \backslash times\; 1\}\; =\; 4$	$x\_1\backslash ,$	$0.5\; \backslash times\; 0.5\; \backslash ,\backslash ,\; (\; 3\; -\; 7\; (0.5)^2\; )\; =\; 0.3125$	$x\_1z=\; 2.188\backslash ,$
$x\_2\backslash ,$	$\backslash frac\{4\}\{2\}\; +\; \backslash frac\{7\}\{2\; \backslash times\; 4\}\; =\; 2.875$	$x\_2\backslash ,$	$0.5\; \backslash times\; 0.3125\; \backslash ,\backslash ,\; (\; 3\; -\; 7\; (0.3125)^2\; )\; =\; 0.3619$	$x\_2z=\; 2.534\backslash ,$
$x\_3\backslash ,$	$\backslash frac\{2.875\}\{2\}\; +\; \backslash frac\{7\}\{2\; \backslash times\; 2.875\}\; =\; 2.654$	$x\_3\backslash ,$	$0.5\; \backslash times\; 0.3619\; \backslash ,\backslash ,\; (\; 3\; -\; 7\; (0.3619)^2\; )\; =\; 0.377$	$x\_3z=\; 2.639\backslash ,$
$x\_4\backslash ,$	$\backslash frac\{2.654\}\{2\}\; +\; \backslash frac\{7\}\{2\; \backslash times\; 2.654\}\; =\; 2.646$	$x\_4\backslash ,$	$0.5\; \backslash times\; 0.377\; \backslash ,\backslash ,\; (\; 3\; -\; 7\; (0.377)^2\; )\; =\; 0.378$	$x\_4z=\; 2.646\backslash ,$
$\backslash sqrt\{7\}\; \backslash approx\; 2.646$		$\backslash sqrt\{7\}\; \backslash approx\; 2.646$

Comparison

The iteration for $f(x)$ involves a division which is more time consuming than a multiplication (usually by a factor of 3 or more) in computer integer arithmetic. The iteration for $g(x)$ involves no division and is thus recommended for large integers z. However, the $f(x)$ iteration always converges, whereas the convergence of the $g(x)$ iteration is sensitive to the initial seed.

Pell's equation

---

Pell's equation yields a method for finding rational approximations of square roots of integers.

Finding square roots using mental arithmetic

---

Based on Pell's equation there is a method to calculate square roots of integers simply by subtracting odd numbers, adapted therefore for mental arithmetic.

Example: For $\backslash sqrt\{27\}$ we start with the following sequence:

27 - 1 = 26

26 - 3 = 23

23 - 5 = 18

18 - 7 = 11

11 - 9 = 2

Five steps have been taken and thus the integer part of the square root of 27 is 5. We do not proceed any further because the sixth subtraction would give a negative answer.

Now take the rest (2) and multiply it by 100 to get the starting number for the next step. Take the answer we have already got (5) and multiply it by 20, then add 1 to get the first odd number we subtract by. This gives us 2 × 100 = 200 as the starting number and 5 × 20 + 1 = 101 as the first odd number. Subtract the successive odd numbers, 103, 105, etc. until we get to a step where the next subtraction would result in a negative number. So,

200 - 101 = 99

and 99 is less than 103 so this is the place to stop and since we only took one step we get that the next digit is 1.

For the next step the starting number will be 99 × 100 = 9900 and the answer we have already got is 51 so the first odd number will be 51 × 20 + 1 = 1021

9900 - 1021 = 8879

8879 - 1023 = 7856

7856 - 1025 = 6831

6831 - 1027 = 5804

5804 - 1029 = 4775

4775 - 1031 = 3744

3744 - 1033 = 2711

2711 - 1035 = 1676

1676 - 1037 = 639

We took nine steps so the next digit is 9.

Continuing with this procedure, the next starting number will be 639 × 100 = 63900 and the first odd number will be 519 × 20 + 1 = 10381 63900 - 10381 = 53519 53519 - 10383 = 43136 43136 - 10385 = 32751 32751 - 10387 = 22364 22364 - 10389 = 11975 11975 - 10391 = 1584 We took six steps so the next digit is 6.

The result gives us 5.196 as an approximation of the square root of 27.

Another(more accurate) way of appling this is to multiply the number(in this case 27) by $10^\{(2y)\}$ (where y is the number of decimal places required) and apply this formula, then dividing the result by $10^y$, though this would complicate the math and the equation would probably not be suitable for mental arithmetic.

Approximating with a random method for arbitrarily large integers

---

The idea of this method for finding the integer part of the square root of $n$ is to choose a random integer in the range $*$, and square it. If it is greater than $n$ and smaller than the right bound of the range, it becomes the new right bound. If the number squared is less than n and greater than the left bound of the range, it becomes the new left bound. In this way a computer can find a good approximation to the square root for any size number very quickly. Here is Maple code that does the job:

intsqrt := proc(z) local A,B,a,b,c,e,r; A := 1; B:= z; e := z-1; while (e>1) do r := rand(A+1..B-1): a := r(e); if (a > A and a^2 < z) then A := a; end; if (a < B and a^2 > z) then B := a; end; e := B-A; end; printf("Integer part of sqrt is %d.\n", A); end proc:

Finding square roots using basic arithmetic

---

If you have access to a calculator capable of addition, subtraction, multiplication and division then the following method can be used to find the square root of a number. Note that this algorithm does not always terminate when attempting to determine the next digit. For example: 2, 3 and 7 do not terminate on the first digit.

Find $\backslash sqrt\{r\}$

$A\_\{base\}\; =\; r\; \backslash qquad\; \backslash qquad\; \backslash qquad\; \backslash qquad\; at\; \backslash quad\; the\; \backslash quad\; very\; \backslash quad\; start$

$B\_\{base\}\; =\; SOLN\; \backslash times\; 20\; +\; 1\; \backslash qquad\; where\; \backslash quad\; SOLN=0\; \backslash quad\; at\; \backslash quad\; the\; \backslash quad\; very\; \backslash quad\; start$

The starting values are

$$

\begin{matrix}D_0 & = & 9 \\ A_0 & = & A_{base} + D_0 \, (D_0 - 1) \\ B_0 & = & B_{base} + 2 \, (D_0 - 1) \end{matrix}

Now find new values for each variable

$A\_n\; =\; A\_\{base\}\; +\; D\_n\; \backslash ,\; (\; D\_n\; -\; 1\; )$

$B\_n\; =\; B\_\{base\}\; +\; 2\; \backslash ,\; (\; D\_n\; -\; 1\; )$

$D\_\{n+1\}\; =\; floor\; (\; A\_n\; \backslash div\; B\_n\; )$

We found a digit when the value of    “$D\_n$”    is equal to the value of    “$floor\; (\; A\_n\; \backslash div\; B\_n\; )$”

After a new digit has been found.

New $A\_\{base\}\; =\; 100\; \backslash ,\; (\; A\_n\; -\; B\_n\; \backslash times\; D\_n\; )$

New $B\_\{base\}\; =\; SOLN\; \backslash times\; 20\; +\; 1$

The step are shown in the table below

Find $\backslash sqrt\{27\}$
$A\_\{base\}\; =\; Z\; =\; 27$ and $B\_\{base\}\; =\; 0\; \backslash times\; 20\; +\; 1\; =\; 1$
$n$	$D\_n$	$A\_n$	$B\_n$	$floor\; (\; A\_n\; \backslash div\; B\_n\; )$	Remarks	SOLN
n=0	$9$	$27\; +\; 9\; \backslash times\; 8\; =\; 99$	$1\; +\; 2\; \backslash times\; 8\; =\; 17$	$5$
n=1	$5$	$27\; +\; 5\; \backslash times\; 4\; =\; 47$	$1\; +\; 2\; \backslash times\; 4\; =\; 9$	$5$	STOP	$5$
$A\_\{base\}\; =\; 100\; \backslash ,\; (47\; -\; 9\; \backslash times\; 5\; )\; =\; 200$ and $B\_\{base\}\; =\; 5\; \backslash times\; 20\; +\; 1\; =\; 101$
n=0	$9$	$200\; +\; 9\; \backslash times\; 8\; =\; 272$	$101\; +\; 2\; \backslash times\; 8\; =\; 117$	$2$
n=1	$2$	$200\; +\; 2\; \backslash times\; 1\; =\; 202$	$101\; +\; 2\; \backslash times\; 1\; =\; 103$	$1$
n=2	$1$	$200\; +\; 1\; \backslash times\; 0\; =\; 200$	$101\; +\; 2\; \backslash times\; 0\; =\; 101$	$1$	STOP	$51$
$A\_\{base\}\; =\; 100\; \backslash ,\; (200\; -\; 101\; \backslash times\; 1\; )\; =\; 9900$ and $B\_\{base\}\; =\; 51\; \backslash times\; 20\; +\; 1\; =\; 1021$
n=0	$9$	$9900\; +\; 9\; \backslash times\; 8\; =\; 9972$	$1021\; +\; 2\; \backslash times\; 8\; =\; 1037$	$9$	STOP	$519$
$A\_\{base\}\; =\; 100\; \backslash ,\; (9972\; -\; 1037\; \backslash times\; 9\; )\; =\; 63900$ and $B\_\{base\}\; =\; 519\; \backslash times\; 20\; +\; 1\; =\; 10381$
n=0	$9$	$63900\; +\; 9\; \backslash times\; 8\; =\; 63972$	$10381\; +\; 2\; \backslash times\; 8\; =\; 10397$	$6$
n=1	$6$	$63900\; +\; 6\; \backslash times\; 5\; =\; 63930$	$10381\; +\; 2\; \backslash times\; 5\; =\; 10391$	$6$	STOP	$5196$
$A\_\{base\}\; =\; 100\; \backslash ,\; (63930\; -\; 10391\; \backslash times\; 6\; )\; =\; 158400$ and $B\_\{base\}\; =\; 5196\; \backslash times\; 20\; +\; 1\; =\; 103921$
n=0	$9$	$158400\; +\; 9\; \backslash times\; 8\; =\; 158472$	$103921\; +\; 2\; \backslash times\; 8\; =\; 103937$	$1$
n=1	$1$	$158400\; +\; 1\; \backslash times\; 0\; =\; 158400$	$103921\; +\; 2\; \backslash times\; 0\; =\; 103921$	$1$	STOP	$51961$
$\backslash sqrt\{27\}\; \backslash approx\; 5.1961$

Continued fraction methods

---

Quadratic irrationals, that is numbers involving square roots in the form (a + √b)/c, have periodic continued fractions. This makes them easy to calculate recursively given the period. For example, to calculate √2, we make use of the fact that √2 − 1 = 2, 2, 2, 2, 2, ..., and use the recurrence relation

a_{n + 1} = 1/(2 + a_n) with a₀ = 0

to obtain √2 − 1 to some specific precision specified through n levels of recurrence, and add 1 to the result to obtain √2.

Steps for finding continued fractions

Find $\backslash sqrt\{r\}$ using continued fractions

$\backslash sqrt\{r\}\; =\; N\_0\; +\; \backslash frac\{1\}\{N\_1\; +\; \backslash frac\{1\}\{N\_2\; +\; \backslash frac\{1\}\{N\_3+\backslash ,\backslash cdots\}\}\}$

Let $\backslash sqrt\{r\}=\backslash sqrt\{N\_0^2\; +\; d\}=\; N\_0\; +\; \backslash frac\{1\}\{X\_0\}\; \backslash qquad\; where\; \backslash quad\; X\_0\; >\; 1\; \backslash qquad\; \backslash mbox\{\; and\; \}\; \backslash quad\; N\_0\; \backslash in\; \backslash mathbb\{Z^+\}$

thus

$\backslash sqrt\{r\}\; =\; N\_0\; +\; \backslash frac\{1\}\{X\_0\}$

$X\_0\; =\; N\_1\; +\; \backslash frac\{1\}\{X\_1\}$

$X\_1\; =\; N\_2\; +\; \backslash frac\{1\}\{X\_2\}$

$X\_2\; =\; N\_3\; +\; \backslash frac\{1\}\{X\_3\}$

Step 0. We shall assume that r is not a perfect square. In other words:

Step 1. Find $N\_0$ using some other method. The best method is $N\_0\; =\; intsqrt(r)$ using some other algorithm to determine the integer square root.

$N\_0\; =\; intsqrt(r)$

Step 2. Find the highest lower bound (L) and lowest upper bound (U) for $\backslash sqrt\{r\}$ where both (L) and (U) are integers.

Hence

$L\; \backslash qquad\; =\; \backslash qquad\; N\_0$

$U\; \backslash qquad\; =\; \backslash qquad\; N\_0\; +\; 1$

Step 3. Write $X\_0$ in terms of $\backslash sqrt\{r\}$.

$X\_0\; =\; \backslash frac\{1\}\{\backslash sqrt\{r\}-N\_0\}\; \backslash qquad\; from\; \backslash qquad\; \backslash sqrt\{r\}\; =\; N\_0\; +\; \backslash frac\{1\}\{X\_0\}$

$X\_0\; =\; \backslash frac\{1\}\{\backslash sqrt\{r\}-N\_0\}\; \backslash times\; \backslash frac\{\backslash sqrt\{r\}+N\_0\}\{\backslash sqrt\{r\}+N\_0\}\; =\; \backslash frac\{\backslash sqrt\{r\}+N\_0\}\{r-N\_0^2\}\; =\; \backslash frac\{\backslash sqrt\{r\}+N\_0\}\{d\}\; =\; \backslash frac\{\backslash sqrt\{r\}+M\_0\}\{D\_0\}$

$\backslash mbox\; \{\; where\; \}\; \backslash quad\; M\_0\; =\; N\_0$

and

$\backslash mbox\; \{\; where\; \}\; \backslash quad\; D\_0\; =\; d$

$X\_0\; =\; \backslash frac\; \{\backslash sqrt\{r\}\; +\; M\_0\; \}\; \{D\_0\}$

$\backslash downarrow$

$\backslash mbox\{\; substitute\; \}\; \backslash quad\; \backslash sqrt\{r\}\; \backslash quad\; \backslash mbox\{\; with\; \}\; \backslash quad\; L\; \backslash quad\; \backslash mbox\{\; or\; \}\; \backslash quad\; U$

$\backslash downarrow$

$X\_\{0\; LowerBound\}\; =\; \backslash frac\{\backslash sqrt\{r\}+M\_0\}\{D\_0\}\; =\; \backslash frac\{L+M\_0\}\{D\_0\}\; =\; \backslash frac\{\; N\_0\; +\; M\_0\; \}\{D\_0\}\; \backslash qquad\; \backslash mbox\{\; Calc\; the\; numeric\; value\; \}$

and

$X\_\{0\; UpperBound\}\; =\; \backslash frac\{\backslash sqrt\{r\}+M\_0\}\{D\_0\}\; =\; \backslash frac\{U+M\_0\}\{D\_0\}\; =\; \backslash frac\{\; (N\_0\; +\; 1)\; +\; M\_0\; \}\{D\_0\}\; \backslash qquad\; \backslash mbox\{\; Calc\; the\; numeric\; value\; \}$

Step 4. Substitute $X\_0$ with $N\_1\; +\; \backslash frac\{1\}\{X\_1\}$

after substitution

Since $\backslash frac\{1\}\{X\_1\}$ is less than one, we can determine $N\_1$ from the numeric values of $X\_\{0\; LowerBound\}$ and $X\_\{0\; UpperBound\}$ because $N\_1\; \backslash \; \backslash in\; \backslash \; \backslash mathbb\{Z^+\}$ (ie. $N\_1$ is an integer). Determine the numeric value of $N\_1$.

Step 5. Once we know the value of $N\_1$, we can rework the equation for $X\_1$

$X\_0\; =\; N\_1\; +\; \backslash frac\{1\}\{X\_1\}\; \backslash quad\; \backslash longrightarrow\; \backslash quad\; X\_1\; =\; \backslash frac\{1\}\{X\_0\; -\; N\_1\}$

$X\_1\; =\; \backslash frac\{1\}\{\; \backslash frac\; \{\; \backslash sqrt\{r\}\; +\; M\_0\; \}\; \{\; D\_0\; \}\; -\; N\_1\; \}\; =\; \backslash frac\{1\}\{\; \backslash frac\; \{\; \backslash sqrt\{r\}\; +\; M\_0\; -\; D\_0\; \backslash ,\; N\_1\; \}\; \{\; D\_0\; \}\; \}\; =\; \backslash frac\; \{\; D\_0\; \}\; \{\; \backslash sqrt\{r\}\; +\; M\_0\; -\; D\_0\; \backslash ,\; N\_1\; \}$

$X\_1\; =\; \backslash frac\; \{\; D\_0\; \}\; \{\; \backslash sqrt\{r\}\; +\; (\; M\_0\; -\; D\_0\; \backslash ,\; N\_1\; )\; \}\; \backslash times\; \backslash frac\; \{\; \backslash sqrt\{r\}\; -\; (\; M\_0\; -\; D\_0\; \backslash ,\; N\_1\; )\; \}\; \{\; \backslash sqrt\{r\}\; -\; (\; M\_0\; -\; D\_0\; \backslash ,\; N\_1\; )\; \}\; =\; \backslash frac\; \{\; D\_0\; (\; \backslash sqrt\{r\}\; -\; (\; M\_0\; -\; D\_0\; \backslash ,\; N\_1\; )\; )\; \}\; \{\; r\; -\; (\; M\_0\; -\; D\_0\; \backslash ,\; N\_1\; )^2\; \}$

$X\_1\; =\; \backslash frac\; \{\; \backslash sqrt\{r\}\; -\; (\; M\_0\; -\; D\_0\; \backslash ,\; N\_1\; )\; \}\; \{\; \backslash frac\; \{\; r\; -\; (\; M\_0\; -\; D\_0\; \backslash ,\; N\_1\; )^2\; \}\; \{\; D\_0\; \}\; \}\; =\; \backslash frac\; \{\; \backslash sqrt\{r\}\; +\; M\_1\; \}\; \{\; D\_1\; \}$

$\backslash mbox\; \{\; where\; \}\; \backslash quad\; M\_1\; =\; -\; (\; M\_0\; -\; D\_0\; \backslash ,\; N\_1\; )$

and

$\backslash mbox\; \{\; where\; \}\; \backslash quad\; D\_1\; =\; \backslash frac\; \{\; r\; -\; (\; M\_0\; -\; D\_0\; \backslash ,\; N\_1\; )^2\; \}\; \{\; D\_0\; \}$

Step 6. Write $X\_1$ in terms of $\backslash sqrt\{r\}$.

$X\_1\; =\; \backslash frac\; \{\backslash sqrt\{r\}\; +\; M\_1\; \}\; \{D\_1\}$

$\backslash downarrow$

$\backslash mbox\{\; substitute\; \}\; \backslash quad\; \backslash sqrt\{r\}\; \backslash quad\; \backslash mbox\{\; with\; \}\; \backslash quad\; L\; \backslash quad\; \backslash mbox\{\; or\; \}\; \backslash quad\; U$

$\backslash downarrow$

$X\_\{1\; LowerBound\}\; =\; \backslash frac\{\backslash sqrt\{r\}+M\_1\}\{D\_1\}\; =\; \backslash frac\{L\; +\; M\_1\}\{D\_1\}\; =\; \backslash frac\{\; N\_0\; +\; M\_1\; \}\{D\_1\}\; \backslash qquad\; \backslash mbox\{\; Calc\; the\; numeric\; value\; \}$

and

$X\_\{1\; UpperBound\}\; =\; \backslash frac\{\backslash sqrt\{r\}+M\_1\}\{D\_1\}\; =\; \backslash frac\{U\; +\; M\_1\}\{D\_1\}\; =\; \backslash frac\{\; (N\_0\; +\; 1)\; +\; M\_1\; \}\{D\_1\}\; \backslash qquad\; \backslash mbox\{\; Calc\; the\; numeric\; value\; \}$

Step 7. Substitute $X\_1$ with $N\_2\; +\; \backslash frac\{1\}\{X\_2\}$

after substitution

Since $\backslash frac\{1\}\{X\_2\}$ is less than one, we can determine $N\_2$ from the numeric values of $X\_\{1\; LowerBound\}$ and $X\_\{1\; UpperBound\}$ because $N\_2\; \backslash \; \backslash in\; \backslash \; \backslash mathbb\{Z^+\}$ (ie. $N\_2$ is an integer). Determine the numeric value of $N\_2$.

Step 8. Once we know the value of $N\_2$, we can rework the equation for $X\_2$

$X\_1\; =\; N\_2\; +\; \backslash frac\{1\}\{X\_2\}\; \backslash quad\; \backslash longrightarrow\; \backslash quad\; X\_2\; =\; \backslash frac\{1\}\{X\_1\; -\; N\_2\}$

$X\_2\; =\; \backslash frac\{1\}\{\; \backslash frac\; \{\; \backslash sqrt\{r\}\; +\; M\_1\; \}\; \{\; D\_1\; \}\; -\; N\_2\; \}\; =\; \backslash frac\{1\}\{\; \backslash frac\; \{\; \backslash sqrt\{r\}\; +\; M\_1\; -\; D\_1\; \backslash ,\; N\_2\; \}\; \{\; D\_1\; \}\; \}\; =\; \backslash frac\; \{\; D\_1\; \}\; \{\; \backslash sqrt\{r\}\; +\; M\_1\; -\; D\_1\; \backslash ,\; N\_2\; \}$

$X\_2\; =\; \backslash frac\; \{\; D\_1\; \}\; \{\; \backslash sqrt\{r\}\; +\; (\; M\_1\; -\; D\_1\; \backslash ,\; N\_2\; )\; \}\; \backslash times\; \backslash frac\; \{\; \backslash sqrt\{r\}\; -\; (\; M\_1\; -\; D\_1\; \backslash ,\; N\_2\; )\; \}\; \{\; \backslash sqrt\{r\}\; -\; (\; M\_1\; -\; D\_1\; \backslash ,\; N\_2\; )\; \}\; =\; \backslash frac\; \{\; D\_1\; (\; \backslash sqrt\{r\}\; -\; (\; M\_1\; -\; D\_1\; \backslash ,\; N\_2\; )\; )\; \}\; \{\; r\; -\; (\; M\_1\; -\; D\_1\; \backslash ,\; N\_2\; )^2\; \}$

$X\_2\; =\; \backslash frac\; \{\; \backslash sqrt\{r\}\; -\; (\; M\_1\; -\; D\_1\; \backslash ,\; N\_2\; )\; \}\; \{\; \backslash frac\; \{\; r\; -\; (\; M\_1\; -\; D\_1\; \backslash ,\; N\_2\; )^2\; \}\; \{\; D\_1\; \}\; \}\; =\; \backslash frac\; \{\; \backslash sqrt\{r\}\; +\; M\_2\; \}\; \{\; D\_2\; \}$

$\backslash mbox\; \{\; where\; \}\; \backslash quad\; M\_2\; =\; -\; (\; M\_1\; -\; D\_1\; \backslash ,\; N\_2\; )$

and

$\backslash mbox\; \{\; where\; \}\; \backslash quad\; D\_2\; =\; \backslash frac\; \{\; r\; -\; (\; M\_1\; -\; D\_1\; \backslash ,\; N\_2\; )^2\; \}\; \{\; D\_1\; \}$

Step 9. Repeat step 6 , 7 and 8 .

Quadratic equation method

---

The solution to a properly setup quadratic equation can be used to find $\backslash sqrt\{r\}$ where 1 < r < 100

$\backslash sqrt\{105.3\}\; =\; \backslash sqrt\{1.053\}\; \backslash times\; 10$

For square root of values less than 1, use the following identity:

$\backslash sqrt\{0.1053\}\; =\; \backslash sqrt\{10.53\}\; \backslash ,\backslash div\backslash ,\; 10$

For square root of values greater than 100, use the following identity:

Using the equation $\backslash sqrt\{r\}\; \backslash ,=\backslash ,\; N\; +\; \backslash frac\{1\}\{X\}$      where $X\; >\; 1$ and $N\; \backslash in\; \backslash \{1,2,3,4,5,6,7,8,9\backslash \}$

$\backslash sqrt\{r\}\; \backslash ,=\backslash ,\; N\; +\; \backslash frac\{1\}\{X\}$

$r\; \backslash ,=\backslash ,\; \{\; \backslash left(\; N\; +\; \backslash frac\{1\}\{X\}\; \backslash right\; )\; \}^2$

$r\; \backslash ,=\backslash ,\; N^2\; +\; \backslash frac\{2\backslash ,N\}\{X\}\; +\; \backslash frac\{1\}\{X^2\}$

$0\; \backslash ,=\backslash ,\; \backslash left(\; N^2\; -\; r\; \backslash right)\; +\; \backslash frac\{2\backslash ,N\}\{X\}\; +\; \backslash frac\{1\}\{X^2\}$

$\backslash left(\; N^2\; -\; r\; \backslash right)\; +\; \backslash frac\{2\backslash ,N\}\{X\}\; +\; \backslash frac\{1\}\{X^2\}\; \backslash ,=\backslash ,\; 0$

$\backslash left(\; N^2\; -\; r\; \backslash right)\; \backslash ,\; X^2\; +\; \backslash left(\; 2\backslash ,N\; \backslash right)\; X\; +\; 1\; \backslash ,=\backslash ,\; 0$

Solve for $X$ using quadratic equation formula, choose the solution that satisfy the restriction $X\; >\; 1$.

The final solution is:

$\backslash sqrt\{r\}\; \backslash ,=\backslash ,\; N\; +\; \backslash frac\{1\}\{X\}$

The obvious problem is that we cannot evaluate the solutions to the quadratic equation without the usage of the square root function. However we can make the snake bite its own tail.

$\backslash left(\; N^2\; -\; r\; \backslash right)\; \backslash ,\; X^2\; +\; \backslash left(\; 2\backslash ,N\; \backslash right)\; X\; +\; 1\; \backslash ,=\backslash ,\; 0$

Let $r\; \backslash ,\; =\; \backslash ,\; N^2\; +\; d$

Thus $d\; \backslash ,\; =\; \backslash ,\; r\; -\; N^2$

And $-\; d\; \backslash ,\; =\; \backslash ,\; N^2\; -\; r$

So the quadratic equation becomes:

$\backslash left(\; -\; d\; \backslash right)\; \backslash ,\; X^2\; +\; \backslash left(\; 2\backslash ,N\; \backslash right)\; X\; +\; 1\; \backslash ,=\backslash ,\; 0$

Solving for X as far as possible brings

$X\; \backslash ,\; =\; \backslash ,\; \backslash frac\{N\; +\; \backslash sqrt\{N^2\; +\; d\}\}\{d\}$

Reciprocal

$\backslash frac\{1\}\{X\}\; \backslash ,\; =\; \backslash ,\; \backslash frac\{d\}\{N\; +\; \backslash sqrt\{N^2\; +\; d\}\}$

So the final solution becomes

$\backslash sqrt\{r\}\; \backslash ,=\backslash ,\; N\; +\; \backslash frac\{1\}\{X\}$

$\backslash sqrt\{r\}\; \backslash ,=\backslash ,\; N\; +\; \backslash frac\{d\}\{N\; +\; \backslash sqrt\{N^2\; +\; d\}\}$

$\backslash sqrt\{r\}\; \backslash ,=\backslash ,\; N\; +\; \backslash frac\{d\}\{N\; +\; \backslash sqrt\{r\}\}$

Lets go deeper by substituting √r on the right hand side with its own definition.

$\backslash sqrt\{r\}\; \backslash ,=\backslash ,\; N\; +\; \backslash frac\{d\}\{N\; +\; \backslash left(\; N\; +\; \backslash frac\{d\}\{N\; +\; \backslash sqrt\{r\}\}\; \backslash right)\; \}$

Renormalise

$\backslash sqrt\{r\}\; \backslash ,=\backslash ,\; N\; +\; \backslash frac\{d\}\{2\; N\; +\; \backslash frac\{d\}\{N\; +\; \backslash sqrt\{r\}\}\; \}$

Deeper still

$\backslash sqrt\{r\}\; \backslash ,=\backslash ,\; N\; +\; \backslash frac\{d\}\{2\; N\; +\; \backslash frac\{d\}\{2\; N\; +\; \backslash frac\{d\}\{N\; +\; \backslash sqrt\{r\}\}\; \}\; \}$

And so on and so forth

$\backslash sqrt\{r\}\; \backslash ,=\backslash ,\; N\; +\; \backslash frac\{d\}\{2\; N\; +\; \backslash frac\{d\}\{2\; N\; +\; \backslash frac\{d\}\{2\; N\; +\; \backslash frac\{d\}\{N\; +\; \backslash sqrt\{r\}\}\; \}\; \}\; \}$

Example

Find $\backslash sqrt\{923.45\}$

Using identity $\backslash sqrt\{923.45\}\; \backslash ,=\backslash ,\; \backslash sqrt\{9.2345\}\; \backslash times\; 10$

First find $\backslash sqrt\{9.2345\}$.

$\backslash sqrt\{r\}\; \backslash ,=\backslash ,\; N\; +\; \backslash frac\{1\}\{X\}$

$\backslash sqrt\{9.2345\}\; \backslash ,=\backslash ,\; N\; +\; \backslash frac\{1\}\{X\}$

Hence $N\; \backslash ,=\backslash ,\; 3\; \backslash ,\backslash !$ because

$\backslash left(\; N^2\; -\; r\; \backslash right)\; \backslash ,\; X^2\; +\; \backslash left(\; 2\backslash ,N\; \backslash right)\; X\; +\; 1\; \backslash ,=\backslash ,\; 0$

$\backslash left(\; 3^2\; -\; 9.2345\; \backslash right)\; \backslash ,\; X^2\; +\; \backslash left(\; 2\; \backslash ,\; \backslash cdot\; \backslash ,\; 3\; \backslash right)\; X\; +\; 1\; \backslash ,=\backslash ,\; 0$

$-0.2345\; \backslash ,\; X^2\; +\; 6\; \backslash ,\; X\; +\; 1\; \backslash ,=\backslash ,\; 0$

Using the quadratic equation formula, we get the two solutions. soln1 = - 0.165 or soln2 = 25.7519

Choose soln2 as it satisfy the restriction $X\; >\; 1$.

Hence $X\; =\; 25.7519$

$\backslash sqrt\{9.2345\}\; \backslash ,=\backslash ,\; 3\; +\; \backslash frac\{1\}\{25.7519\}\; \backslash ,=\backslash ,\; 3.03883$

Alternatively

$\backslash sqrt\{r\}\; \backslash ,=\backslash ,\; N\; +\; \backslash frac\{d\}\{2\; N\; +\; \backslash frac\{d\}\{2\; N\; +\; \backslash frac\{d\}\{N\; +\; N\}\; \}\; \}$

$\backslash sqrt\{9.2345\}\; \backslash ,=\backslash ,\; 3\; +\; \backslash frac\{0.2345\}\{6\; +\; \backslash frac\{0.2345\}\{6\; +\; \backslash frac\{0.2345\}\{3\; +\; 3\}\; \}\; \}$

$\backslash sqrt\{9.2345\}\; \backslash ,\backslash approx\backslash ,\; 3\; +\; \backslash frac\{0.2345\}\{6\; +\; \backslash frac\{0.2345\}\{6\; +\; \backslash frac\{0.2345\}\{3\; +\; 3\}\; \}\; \}$

$\backslash sqrt\{9.2345\}\; \backslash ,\backslash approx\backslash ,\; 3.03883$

And the final solution is

$\backslash sqrt\{923.45\}\; \backslash ,=\backslash ,\; \backslash sqrt\{9.2345\}\; \backslash times\; 10\; \backslash ,=\backslash ,\; 30.3883$

Approximations that depend on IEEE representation

---

On computers, a very rapid Newton's method based approximation to the square root can be obtained for floating point numbers when computers use an IEEE (or sufficiently similar) representation.

float fastsqrt(float val) { int tmp = *(int *)&val; tmp -= 1<<23; /* Remove IEEE bias from exponent (-2^23) */ /* tmp is now an appoximation to logbase2(val) */ tmp = tmp >> 1; /* divide by 2 */ tmp += 1<<23; /* restore the IEEE bias from the exponent (+2^23) */ return *(float *)&tmp; }

In the above, the operations to add and remove the IEEE bias can be combined into a single operation. An additional adjustment can be made in the same operation to reduce the maximum relative error. So, the three operations, not including the cast, can be rewritten as: tmp = (1<<23) + (tmp >> 1) - 1<<22 + m;

Where m is some magic number that corresponds to a calculation involving an initial guess used in the Newton's approximation.

A variant of the above routine can be used to compute the inverse square root $x^\{-\{1\backslash over2\}\}$ instead, which has been attributed to the programmers of the game Doom. As an approximation, it produced a relative error of less than 4%, and in computer graphics it is a very efficient way to normalize a vector.

See also

---

• Integer square root
• Shifting nth-root algorithm
• N-th root algorithm

Root-finding algorithms

Calcolo della radice quadrata