A weird algorithm for finding the square root of any integer

Question

A weird algorithm for finding the square root of any integer goes as the following:

example $√25$: $25 - 1 -3 - 5 - 7 - 9 = 0$

We have deducted 5 numbers (-1, -3, -5, -7, -9) without resulting in a negative number, and thus the answer is 5

example $√27$: $27 - 1 -3 - 5 - 7 - 9 = 2$

We have deducted 5 numbers (-1, -3, -5, -7, -9) without resulting in a negative number, and thus the answer is 5.?, but in this case we have a remainder of 2 and thus we have to complete a decimal for 5.?

We have two ways to deal with the remainder:

First way: We can multiply $27 * 100$, or $27 * 10000$ or $27 * 1000000$ (every additional 00 will result in a more precise answer:

$2700 - 1 -3 -5 -7 -9 -11 -13 -15 -17 -19 -21 -23 -25 -27 -29 -31 -33 -35 -37 -39 - 41 -43 -45 -47 -49 -51 -53 -55 -57 -59 -61 -63 -65 -67 -69 -71 -73 -75 -77 -79 -81 -83 -85 - 87 -89 -91 -93 -95 -97 -99 -101 = 99$

We have deducted 51 numbers and there for we know the first decimal for √27 = 5.1?

the more 00's we put at the end of 27, the more decimals we will get.

Second way: $27−1−3−5−7−9=2$ We take the remainder of 2 and divide it by what would of been the next number to deduct in the sequences. In this case it would of been 11

$2/11 = 0.18181818181818....$

Here is the funny thing: We then take the result and we can add it to what would of been the next number to deduct in the sequence minus 1. In this case 11-1 = 10 and 10 + 0.18181818181818 = 10.181818181818

$2/10.181818181818181818 = 0.19642857142857142$

and we repeat the process until there is no more change:

$2/10.19642857142857142 = 0.19614711033274956$

$2/10.19614711033274956 = 0.19615252490553076$

$2/10.19615252490553076 = 0.1961524207405411$

$2/10.1961524207405411 = 0.19615242274445532$

$2/10.19615242274445532 = 0.19615242270590422$

At the end when there is no more change (and without rounding the results to begin with)

$√27 = 5.196152422706631880582....$

The first way is self explanatory, but the second way is very weird. Why is it that first we divide by what would be the next number in the sequence and then we can take the decimal and add it to the next number minus 1? And why repeating the step of adding the result decimal to the next number in the sequence minus 1, acts as a sieve for sharpening the answer?

Answer 1

We aim to find the root of $f(x) = (x+a)^2 - b$, where $a$ is the integer part of the square root (which is easier to find) and $x$ would be the fractional part of the square root.

We have

$$x^2 + 2ax + a^2-b = 0$$

$$x = \frac {b-a^2}{2a+x}$$

So we can set up the iteration

$$x_{n+1} = \frac {b-a^2}{2a + x_n}$$

Note that $a$ is the integer part of the square root (which is equal to the numbers we deducted), and we take $x_0 = 0$. Then each iteration we use the remainder $(b-a^2)$ and divide it by twice that number ($2a$, which happens to be the next number to deduct minus one) with the decimals added to it $(x_n)$.

If our method converges, it will converge to $L = \sqrt b - a$. Now we check that it does converge to $L$ by showing $|x_{n+1} - L| < |x_n-L|$ (that is, each iteration we go closer and closer to the value). We have:

$$|x_{n+1} - L| = \left|\frac {b-a^2}{2a+ x_n}-(\sqrt b-a)\right| = \frac {\sqrt b - a}{2a+x_n}|\sqrt b + a - 2a - x_n| = \frac{\sqrt b - a}{2a+x_n}|L-x_n|$$

since $\sqrt b-a < 1$ and $2a+x_n \ge 2$, we have $|x_{n+1}-L| < \frac12|x_n-L|$ and we are done.

This also shows that this method converges linearly with rate of convergence $\dfrac {\sqrt b - a}{\sqrt b + a}$.