Square root algorithms

There are many methods to compute square roots.

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

${\sqrt {x}}=e^{{\frac {1}{2}}\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 ${\sqrt {r}}$ is known as the "Babylonian method" and is based on 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. go to 2

This is a quadratically convergent algorithm, which means that the number of correct digits of $r$ roughly doubles with each step.

This could be represented as

$x_{n+1}=0.5(x_{n}+{\frac {r}{x_{n}}})$

where $\lim _{n\to \infty }x_{n}={\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.

Simple approximation

The simple approximation is rather simple and can be highly inaccurate. 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

$N^{2}\quad <\quad N^{2}+d\quad <\quad N^{2}+2\,d+{\frac {d^{2}}{N^{2}}}$

$N^{2}\quad <\quad N^{2}+d\quad <\quad N^{2}+2\left(N\right)\left({\frac {d}{N}}\right)+\left({\frac {d}{N}}\right)^{2}$

$N^{2}\quad <\quad N^{2}+d\quad <\quad \left(N+{\frac {d}{N}}\right)^{2}$

$N\quad <\quad {\sqrt {N^{2}+d}}\quad <\quad N+{\frac {d}{N}}$

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

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

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

Thus

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

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 by the name of "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 Sarada script.

The Bakhshali square root approximation is just the simple approximation applied twice.

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

Let $A=N+P$

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

When expanded, the equation becomes

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

Bakhshali approximation example

Find ${\sqrt {9.2345}}$

Using $N=3$ and $d=9.2345-3^{2}=0.2345$

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

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

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

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

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

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 use 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. Calculate the value of 3^D.
4. The rough estimate is half the value obtained in step 3. E = (3^D) / 2

Example

r	Z	D	3 ^ D	Estimate (E)	Actual Value of √r
723.47	723	3	27	13.5	26.89
5396.37	5396	4	81	40.5	73.45
24956.41	24956	5	243	121.5	157.96
789345.464	789345	6	729	364.5	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 be taken one extra step further by applying the Bakhshali square root approximation.

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 obtain in step 3 multiple by an adjustment factor based on the first (left most) digit of the number n. E = ADJ * 3.16^D
5. Applying the Bakhshali square root approximation to the estimate E.

$c=r-E^{2}$

$P={\frac {c}{2E}}$

$A=E+P$

$B=A-{\frac {P^{2}}{2A}}$

Table of ADJ

First Digit	1	2	3	4	5	6	7	8	9
ADJ	0.32	0.45	0.55	0.63	0.71	0.78	0.84	0.90	0.95

Example

r	Z	D	3.16 ^ D	ADJ	Estimate (E)	Bakhshali (B)	Actual Value of √r
723.47	723	3	31.55	0.84	26.50	26.89	26.89
5396.37	5396	4	99.71	0.71	70.79	73.46	73.45
24956.41	24956	5	315.09	0.45	141.79	157.98	157.96
789345.464	789345	6	995.7	0.84	836.37	888.45	888.45

Inverse square root approximation

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

Because ${\sqrt {r}}=r\times \left({\frac {1}{\sqrt {r}}}\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}=\left({\frac {1}{\sqrt {r}}}\right)_{\mbox{approx}}$

Step 2 Calculate the next iteration with the following algorithm.

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

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

${\sqrt {r}}=r\,X_{\infty }$

Because $X_{\infty }$ is the inverse square root of r.

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}) \over f^{\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".

First method

The first method finds the square root of "z"

$f(x)=x^{2}-z\,$

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

The first derivative of $f(x)$ is $f^{\prime }(x)=2x$

Thus iteration for $x_{n+1}$ is derived where:

$x_{0}=1\,\,\,$        and

$x_{n+1}\,\!$	$=x_{n}-{f(x_{n}) \over f^{\prime }(x_{n})}$
	$=x_{n}-{(x_{n}^{2}-z) \over 2x_{n}}$
	$=x_{n}-{\frac {x_{n}}{2}}+{\frac {z}{2\,\,\,x_{n}}}$
	$={\frac {x_{n}}{2}}+{\frac {z}{2\,\,\,x_{n}}}$.

Second method

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

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

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

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

Thus iteration for $x_{n+1}$ is derived where:

$x_{0}=0.5$        and

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

Example

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

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

$f(x)\,$		$g(x)\,$
$x_{0}\,$	$1\,$	$x_{0}\,$	$0.5\,$
$x_{1}\,$	${\frac {1}{2}}+{\frac {7}{2\times 1}}=4$	$x_{1}\,$	$0.5\times 0.5\,\,(3-7(0.5)^{2})=0.312$	${\frac {1}{x_{1}}}=3.2\,$
$x_{2}\,$	${\frac {4}{2}}+{\frac {7}{2\times 4}}=2.875$	$x_{2}\,$	$0.5\times 0.312\,\,(3-7(0.312)^{2})=0.362$	${\frac {1}{x_{2}}}=2.762\,$
$x_{3}\,$	${\frac {2.875}{2}}+{\frac {7}{2\times 2.875}}=2.654$	$x_{3}\,$	$0.5\times 0.362\,\,(3-7(0.362)^{2})=0.376$	${\frac {1}{x_{3}}}=2.652\,$
$x_{4}\,$	${\frac {2.654}{2}}+{\frac {7}{2\times 2.654}}=2.645$	$x_{4}\,$	$0.5\times 0.376\,\,(3-7(0.376)^{2})=0.378$	${\frac {1}{x_{4}}}=2.645\,$
${\sqrt {7}}\approx 2.645$		${\sqrt {7}}\approx 2.645$

Comparison

The iteration for $f(x)$ involves a division which is more time consuming than a multiplication in computer integer arithmetic. The iteration for $g(x)$ involves no division and is thus recommended for large integers z.

This iteration using "g" involves only a squaring and two multiplications, as opposed to a division in the case of f. In practical implementations of large integer square roots, the iteration involving g is faster for large integers z since division is at best $O(M(n))$, a constant times the time function of multiplication. The constant term is almost always 3 or more, meaning that a single division can almost never be faster than 3 multiplications.

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 simply by subtracting odd numbers.

Example: For ${\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.

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 ${\sqrt {r}}$

$A_{base}=r\qquad \qquad \qquad \qquad at\quad the\quad very\quad start$

$B_{base}=SOLN\times 20+1\qquad where\quad SOLN=0\quad at\quad the\quad very\quad start$

The starting values are

$D_{0}=9$

$A_{0}=A_{base}+D_{0}\,(D_{0}-1)$

$B_{0}=B_{base}+2\,(D_{0}-1)$

Now find new values for each variable

$A_{n}=A_{base}+D_{n}\,(D_{n}-1)$

$B_{n}=B_{base}+2\,(D_{n}-1)$

$D_{n+1}=floor(A_{n}\div B_{n})$

We found a digit when the value of    “$D_{n}$”    is equal to the value of    “$floor(A_{n}\div B_{n})$”

After a new digit has been found.

New $A_{base}=100\,(A_{n}-B_{n}\times D_{n})$

New $B_{base}=SOLN\times 20+1$

The step are shown in the table below

Find ${\sqrt {27}}$
$A_{base}=Z=27$ and $B_{base}=0\times 20+1=1$
$n$	$D_{n}$	$A_{n}$	$B_{n}$	$floor(A_{n}\div B_{n})$	Remarks	SOLN
n=0	$9$	$27+9\times 8=99$	$1+2\times 8=17$	$5$
n=1	$5$	$27+5\times 4=47$	$1+2\times 4=9$	$5$	STOP	$5$
$A_{base}=100\,(47-9\times 5)=200$ and $B_{base}=5\times 20+1=101$
n=0	$9$	$200+9\times 8=272$	$101+2\times 8=117$	$2$
n=1	$2$	$200+2\times 1=202$	$101+2\times 1=103$	$1$
n=2	$1$	$200+1\times 0=200$	$101+2\times 0=101$	$1$	STOP	$51$
$A_{base}=100\,(200-101\times 1)=9900$ and $B_{base}=51\times 20+1=1021$
n=0	$9$	$9900+9\times 8=9972$	$1021+2\times 8=1037$	$9$	STOP	$519$
$A_{base}=100\,(9972-1037\times 9)=63900$ and $B_{base}=519\times 20+1=10381$
n=0	$9$	$63900+9\times 8=63972$	$10381+2\times 8=10397$	$6$
n=1	$6$	$63900+6\times 5=63930$	$10381+2\times 5=10391$	$6$	STOP	$5196$
$A_{base}=100\,(63930-10391\times 6)=158400$ and $B_{base}=5196\times 20+1=103921$
n=0	$9$	$158400+9\times 8=158472$	$103921+2\times 8=103937$	$1$
n=1	$1$	$158400+1\times 0=158400$	$103921+2\times 0=103921$	$1$	STOP	$51961$
${\sqrt {27}}\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 = [0; 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 ${\sqrt {r}}$ using continued fractions

${\sqrt {r}}=N_{0}+{\frac {1}{N_{1}+{\frac {1}{N_{2}+{\frac {1}{N_{3}+\,\cdots }}}}}}$

Let ${\sqrt {r}}={\sqrt {N_{0}^{2}+d}}=N_{0}+{\frac {1}{X_{0}}}\qquad where\quad X_{0}>1\qquad {\mbox{ and }}\quad N_{0}\in \mathbb {Z^{+}}$

thus

${\sqrt {r}}=N_{0}+{\frac {1}{X_{0}}}$

$X_{0}=N_{1}+{\frac {1}{X_{1}}}$

$X_{1}=N_{2}+{\frac {1}{X_{2}}}$

$X_{2}=N_{3}+{\frac {1}{X_{3}}}$

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

${\sqrt {r}}={\sqrt {N_{0}^{2}+d}}\qquad {\mbox{ and }}\quad N_{0}\in \mathbb {Z^{+}} \quad {\mbox{ and }}0<d<1$

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 ${\sqrt {r}}$ where both (L) and (U) are integers.

$L\qquad <\qquad {\sqrt {r}}\qquad <\qquad U$

Hence

$L\qquad =\qquad N_{0}$

$U\qquad =\qquad N_{0}+1$

Step 3. Write $X_{0}$ in terms of ${\sqrt {r}}$.

$X_{0}={\frac {1}{{\sqrt {r}}-N_{0}}}\qquad from\qquad {\sqrt {r}}=N_{0}+{\frac {1}{X_{0}}}$

$X_{0}={\frac {1}{{\sqrt {r}}-N_{0}}}\times {\frac {{\sqrt {r}}+N_{0}}{{\sqrt {r}}+N_{0}}}={\frac {{\sqrt {r}}+N_{0}}{r-N_{0}^{2}}}={\frac {{\sqrt {r}}+N_{0}}{d}}={\frac {{\sqrt {r}}+M_{0}}{D_{0}}}$

${\mbox{ where }}\quad M_{0}=N_{0}$

and

${\mbox{ where }}\quad D_{0}=d$

$X_{0}={\frac {{\sqrt {r}}+M_{0}}{D_{0}}}$

$\downarrow$

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

$\downarrow$

$X_{0LowerBound}={\frac {{\sqrt {r}}+M_{0}}{D_{0}}}={\frac {L+M_{0}}{D_{0}}}={\frac {N_{0}+M_{0}}{D_{0}}}\qquad {\mbox{ Calc the numeric value }}$

and

$X_{0UpperBound}={\frac {{\sqrt {r}}+M_{0}}{D_{0}}}={\frac {U+M_{0}}{D_{0}}}={\frac {(N_{0}+1)+M_{0}}{D_{0}}}\qquad {\mbox{ Calc the numeric value }}$

Step 4. Substitute $X_{0}$ with $N_{1}+{\frac {1}{X_{1}}}$

$X_{0LowerBound}\quad <\quad X_{0}\quad <\quad X_{0UpperBound}$

after substitution

$X_{0LowerBound}\quad <\quad N_{1}+{\frac {1}{X_{1}}}\quad <\quad X_{0UpperBound}$

Since ${\frac {1}{X_{1}}}$ is less than one, we can determine $N_{1}$ from the numeric values of $X_{0LowerBound}$ and $X_{0UpperBound}$ because $N_{1}\ \in \ \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}+{\frac {1}{X_{1}}}\quad \longrightarrow \quad X_{1}={\frac {1}{X_{0}-N_{1}}}$

$X_{1}={\frac {1}{{\frac {{\sqrt {r}}+M_{0}}{D_{0}}}-N_{1}}}={\frac {1}{\frac {{\sqrt {r}}+M_{0}-D_{0}\,N_{1}}{D_{0}}}}={\frac {D_{0}}{{\sqrt {r}}+M_{0}-D_{0}\,N_{1}}}$

$X_{1}={\frac {D_{0}}{{\sqrt {r}}+(M_{0}-D_{0}\,N_{1})}}\times {\frac {{\sqrt {r}}-(M_{0}-D_{0}\,N_{1})}{{\sqrt {r}}-(M_{0}-D_{0}\,N_{1})}}={\frac {D_{0}({\sqrt {r}}-(M_{0}-D_{0}\,N_{1}))}{r-(M_{0}-D_{0}\,N_{1})^{2}}}$

$X_{1}={\frac {{\sqrt {r}}-(M_{0}-D_{0}\,N_{1})}{\frac {r-(M_{0}-D_{0}\,N_{1})^{2}}{D_{0}}}}={\frac {{\sqrt {r}}+M_{1}}{D_{1}}}$

${\mbox{ where }}\quad M_{1}=-(M_{0}-D_{0}\,N_{1})$

and

${\mbox{ where }}\quad D_{1}={\frac {r-(M_{0}-D_{0}\,N_{1})^{2}}{D_{0}}}$

Step 6. Write $X_{1}$ in terms of ${\sqrt {r}}$.

$X_{1}={\frac {{\sqrt {r}}+M_{1}}{D_{1}}}$

$\downarrow$

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

$\downarrow$

$X_{1LowerBound}={\frac {{\sqrt {r}}+M_{1}}{D_{1}}}={\frac {L+M_{1}}{D_{1}}}={\frac {N_{0}+M_{1}}{D_{1}}}\qquad {\mbox{ Calc the numeric value }}$

and

$X_{1UpperBound}={\frac {{\sqrt {r}}+M_{1}}{D_{1}}}={\frac {U+M_{1}}{D_{1}}}={\frac {(N_{0}+1)+M_{1}}{D_{1}}}\qquad {\mbox{ Calc the numeric value }}$

Step 7. Substitute $X_{1}$ with $N_{2}+{\frac {1}{X_{2}}}$

$X_{1LowerBound}\quad <\quad X_{1}\quad <\quad X_{1UpperBound}$

after substitution

$X_{1LowerBound}\quad <\quad N_{2}+{\frac {1}{X_{2}}}\quad <\quad X_{1UpperBound}$

Since ${\frac {1}{X_{2}}}$ is less than one, we can determine $N_{2}$ from the numeric values of $X_{1LowerBound}$ and $X_{1UpperBound}$ because $N_{2}\ \in \ \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}+{\frac {1}{X_{2}}}\quad \longrightarrow \quad X_{2}={\frac {1}{X_{1}-N_{2}}}$

$X_{2}={\frac {1}{{\frac {{\sqrt {r}}+M_{1}}{D_{1}}}-N_{2}}}={\frac {1}{\frac {{\sqrt {r}}+M_{1}-D_{1}\,N_{2}}{D_{1}}}}={\frac {D_{1}}{{\sqrt {r}}+M_{1}-D_{1}\,N_{2}}}$

$X_{2}={\frac {D_{1}}{{\sqrt {r}}+(M_{1}-D_{1}\,N_{2})}}\times {\frac {{\sqrt {r}}-(M_{1}-D_{1}\,N_{2})}{{\sqrt {r}}-(M_{1}-D_{1}\,N_{2})}}={\frac {D_{1}({\sqrt {r}}-(M_{1}-D_{1}\,N_{2}))}{r-(M_{1}-D_{1}\,N_{2})^{2}}}$

$X_{2}={\frac {{\sqrt {r}}-(M_{1}-D_{1}\,N_{2})}{\frac {r-(M_{1}-D_{1}\,N_{2})^{2}}{D_{1}}}}={\frac {{\sqrt {r}}+M_{2}}{D_{2}}}$

${\mbox{ where }}\quad M_{2}=-(M_{1}-D_{1}\,N_{2})$

and

${\mbox{ where }}\quad D_{2}={\frac {r-(M_{1}-D_{1}\,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 ${\sqrt {r}}$ where 1 < r < 100

For square root of values greater than 100, use the following identity: ${\sqrt {105.3}}={\sqrt {1.053}}\times 10$ For square root of values less than 1, use the following identity: ${\sqrt {0.1053}}={\sqrt {10.53}}\,\div \,10$

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

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

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

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

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

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

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

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

The final solution is:

${\sqrt {r}}\,=\,N+{\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.

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

Let $r\,=\,N^{2}+d$

Thus $d\,=\,r-N^{2}$

And $-d\,=\,N^{2}-r$

So the quadratic equation becomes:

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

Solving for X as far as possible brings

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

Reciprocal

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

So the final solution becomes

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

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

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

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

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

Renormalise

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

Deeper still

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

And so on and so forth

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

Example using the quadratic equation method

Find ${\sqrt {923.45}}$

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

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

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

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

Hence $N\,=\,3\,\!$ because $\!\;3^{2}\;<\;9.2345\;<\;4^{2}$

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

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

$-0.2345\,X^{2}+6\,X+1\,=\,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$

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

Alternatively

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

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

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

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

And the final solution is

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

See also

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