[VA] SRC#003- New Year 2019 Special

[Albert Chan]

(02-08-2019 06:46 PM)Albert Chan Wrote:  Tried doing √3 with this matrix power method, noticed a pattern:
let M = {{1,3}, {1, 1}}

M^2 = {{3*1+1, 3*(1+1)}, {1+1, 3*1+1}} = {{4,6}, {2,4}}
M^3 = {{3*2+4, 3*(2+4)}, {2+4, 3*2+4}} = {{10,18}, {6,10}} ...

To prove that the ratio converge to √3, noticed above actually does Farey Fraction:

M^1: √3 between 1/1 and 3/1, so (1+3)/(1+1) = 4/2 is better estimate.
M^2: √3 between 4/2 and 3/(4/2) = 6/4, so (4+6)/(2+4) = 10/6 is better estimate
M^3: ...

Newton's method, does the same thing, but converge faster: x = ½(x + 3/x)

1: ½(1/1 + 3*1/1) = 2/1 = 2
2: ½(2/1 + 3*1/2) = 7/4 = 1.75
3: ½(7/4 + 3*4/7) = 97/56 ~ 1.732143
4: ½(97/56 + 3*56/97) = 18817/10864 ~ 1.73205081

The fractions are so good that all above (and at least 6 more !) are √3 continued fraction convergents.