Square Root Process Similar to Long Division

[Albert Chan]

(09-17-2021 11:00 PM)jeejohn Wrote:  Basically, we're keeping track of 2*X on the left, then we add a digit δ to get 2X+δ. Finally we multiple by δ to get 2Xδ+δ^2. We subtract this from the previous quotient to get a new quotient.

Above is based on identity: (X+δ)^2 = X^2 + δ*(2X+δ)

N = 12345 = (X+δ)^2
X = 100
R = N-X^2 = 2345

R = δ*(2X+δ), but we cannot get δ without square root.

Newton's method assumed (2X+δ) ≈ 2X, then solve for δ
With this assumption, solved δ always over-estmate.
To compensate, we floored estimated result.

R/2/X = 11.725
δ = 11
R -= δ*(2X+δ) = 24

X = X+δ = 111
R/2/X ≈ 0.108108108
δ = 0.1081
R -= δ*(2X+δ) = -0.00988561

X = X+δ = 111.1081
R/2/X ≈ -4.448645058E-5
δ = -4.448646E-5             // floor of negative number, same sig. digits as X

√12345 ≈ 111.1081 + (-4.448646E-5) = 111.10805551354