Square Root Process Similar to Long Division

[Albert Chan]

Newton's method converge fast, but required expensive mul/div.
HP has a digit-by-digit method for square-root, that is very efficient.

First, we halved R

R/2 = δ*(X+δ/2)

if δ=1, δ*(X+δ/2) = (X+0.5)
if δ=2, δ*(X+δ/2) = 2*(X+1) = (X+0.5) + (X+1.5)
if δ=3, δ*(X+δ/2) = 3*(X+1.5) = (X+0.5) + (X+1.5) + (X+2.5)
...

This way, we avoided division to get δ. When R/2 - δ*(X+δ/2) < 0, we gone too far.

√12345, digit-by-digit:

1.2345 - 1^2 = .2345
R/2 = .11725

11.725 - 10.5 = 1.225
1.225 - 11.5 = -10.275

122.5 - 110.5 = 12
12 - 111.5 = -99.5

1200 - 1110.5 = 89.5
89.5 - 1111.5 = -1022

8950 - 11110.5 = -2160.5

895000 - 111100.5 = 783899.5
783899.5 - 111101.5 = 672798
672798 - 111102.5 = 561695.5
561695.5 - 111103.5 = 450592
450592 - 111104.5 = 339487.5
339487.5 - 111105.5 = 228382
228382 - 111106.5 = 117275.5
117275.5 - 111107.5 = 6168
6168 - 111108.5 = -104940.5

616800 - 1111080.5 = -494280.5

61680000 - 11110800.5 = 50569199.5
50569199.5 - 11110801.5 = 39458398
39458398 - 11110802.5 = 28347595.5
28347595.5 - 11110803.5 = 17236792
17236792 - 11110804.5 = 6125987.5
6125987.5 - 11110805.5 = -4984818

√12345 ≈ 111.10805 (under-estimated due to positive remainder)

Except for initial setup, algorithm only use subtraction

Quote:Note that for the final quotient = 12345-111.10805^2 = .0012251975 is the remainder

We confirm by undo scaling and halving R
first digit 1.2345/12345 = 1e-4, other 7 digits 100^7 = 1e14

12345 - 111.10805^2 = 6125987.5 * 1e-10 * 2 = 0.0012251975