Square Root Process Similar to Long Division

[Thomas Klemm]

(09-18-2021 01:07 PM)Albert Chan Wrote:  Newton's method converge fast, but required expensive mul/div.

We can do as Newton did and use this equation instead:

\(
\begin{align}
\frac{1}{x^2} = d
\end{align}
\)

Using Newton's method we get the following recurrence:

\(
\begin{align}
x \leftarrow x + \frac{x(1 - d \cdot x^2)}{2}
\end{align}
\)

So we can get rid of the expensive division and only have to divide by 2.
To get \(\sqrt{d}\) we have to multiply the final result \(x\) by \(d\).

Program

This is the corresponding Python program:

Code:

def newton(d, x, n):
     for _ in range(n):
         u = d * x
         print(u)
         x += x * (1 - u * x) / 2

Examples

d = Decimal('.9996')
x = Decimal('1')
newton(d, x, 7)

0.9996
0.99979992
0.99979997999599359936
0.99979997999599899971991597354766255640239090891735007232
0.999799979995998999719915973591417139027263962386382736646308053824790220415186​0911590260475681681352
0.999799979995998999719915973591417139027263962386382736649180323587214856901603​0640762583498945948583
0.999799979995998999719915973591417139027263962386382736649180323587214856901603​0640762583498945948583

d = Decimal('12345')
x = Decimal('0.009')
newton(d, x, 7)

111.105
111.1080553875
111.1080555135405110305346994140625
111.1080555135405112450044387430752408689311675830734154751136313016974218865863​978862762451171875
111.1080555135405112450044387430752414899113774596977299764856731617825851115519​126275283305922167024
111.1080555135405112450044387430752414899113774596977299764856731617825903175167​629180920706522637384
111.1080555135405112450044387430752414899113774596977299764856731617825903175167​629180920706522637384

Depending on the use case only a few iterations might be needed.
Still the multiplications might get tedious after a while.