Another way to derive the same faster iteration is described in http://www.jsoftware.com/jwiki/Essays/Linear_Recurrences Basically, when you have M&x^:n v (where x=: +/ .*), it's M x M x ... x M v, which is equivalent to (M x M x ... x M) v, and you can use repeated squaring http://www.jsoftware.com/jwiki/Essays/Repeated_Squaring to compute the part in the parents, the n-th power of M. We can then use Cliff's suggestion to see how close we are getting. Thus:
x=: +/ .* M=: 1 3,:1 1x 0j80 ": ,. %/"1 (x~^:(i.10) M) x 1 0 1.00000000000000000000000000000000000000000000000000000000000000000000000000000000 2.00000000000000000000000000000000000000000000000000000000000000000000000000000000 1.75000000000000000000000000000000000000000000000000000000000000000000000000000000 1.73214285714285714285714285714285714285714285714285714285714285714285714285714286 1.73205081001472754050073637702503681885125184094256259204712812960235640648011782 1.73205080756887729525435394607217191423510670911984376613038236739989213213414405 1.73205080756887729352744634150587236780369509078195667060132376597461798623959566 1.73205080756887729352744634150587236694280525381038062805580697945193301712274622 1.73205080756887729352744634150587236694280525381038062805580697945193301690880004 1.73205080756887729352744634150587236694280525381038062805580697945193301690880004 I note that Newton's iteration gives the same convergents: 0j80": ,. -:@(+3&%)^:(i.10) 1x 1.00000000000000000000000000000000000000000000000000000000000000000000000000000000 2.00000000000000000000000000000000000000000000000000000000000000000000000000000000 1.75000000000000000000000000000000000000000000000000000000000000000000000000000000 1.73214285714285714285714285714285714285714285714285714285714285714285714285714286 1.73205081001472754050073637702503681885125184094256259204712812960235640648011782 1.73205080756887729525435394607217191423510670911984376613038236739989213213414405 1.73205080756887729352744634150587236780369509078195667060132376597461798623959566 1.73205080756887729352744634150587236694280525381038062805580697945193301712274622 1.73205080756887729352744634150587236694280525381038062805580697945193301690880004 1.73205080756887729352744634150587236694280525381038062805580697945193301690880004 a=: %/"1 (x~^:(i.10) M) x 1 0 b=: -:@(+3&%)^:(i.10) 1x a-:b 1 ----- Original Message ----- From: John Randall <rand...@andromeda.rutgers.edu> Date: Friday, March 5, 2010 9:29 Subject: Re: [Jprogramming] Precision of rational approximation of irrational number To: Programming forum <programming@jsoftware.com> > Devon McCormick wrote: > > Members of the Forum - > > > > If I'm approximating, e.g. the square root of 3, with a matrix > method> which > > returns an extended precision numerator and denominator, when > I work out > > the > > decimal equivalent of this, at what point do I run out of > significant> digits? > > > > Devon: > > You can do much better with these Pell-type estimates, since you can > generate estimates 2,4,8,16,... directly: If your last > estimate was p/q, > your next estimate is ((*:p)+3**:q)%2*p*q. > > > f=:((1 3)&(+/ .*)@:*:),+:@(*/) > > f^:(i.5) 1 1x > > 1 1 > > 4 2 > 28 16 > 1552 896 > 4817152 2781184 > > (%:3)-%/f^:3 ] 1 1x > _9.20496e_5 > (%:3)-%/f^:4 ] 1 1x > _2.44585e_9 > (%:3)-%/f^:5 ] 1 1x > 0 ---------------------------------------------------------------------- For information about J forums see http://www.jsoftware.com/forums.htm
