Square Root: Digit by Digit Algorithm

[Albert Chan]

(11-25-2022 02:40 PM)ttw Wrote:  There's a hidden point that's not obvious (at least it wasn't to me). Any continued fraction P2/Q2 lies between the fractions P1/Q1 (the previous approximation) and (P1+P0)/(Q1+Q0), the mediant of the previous two approximations. It's sort of like doing interval arithmetic but with mediants rather than half-interval representatives.

If we let x0 = P0/Q0, x1 = P1/Q1, continued fraction coefficient, k ≥ 1:

x2 = P2/Q2 = (k*P1+P0)/(k*Q1+Q0) = x1 - (x1-x0)* (Q0/(Q0+k*Q1))

Since Q1 > Q0, 0 < last term < 1/2, x2 between ((x0+x1)/2, x1)
In other words, convergent is always better estimate than mean of previously 2 convergents.