If it's the n-th Fibonacci number that is to be computed, a faster computation can be derived from the expression (0 1 ,: 1 1)&(+/ . *) ^:(i.12) 0 1
Let A=:0 1,:1 1x be a 2 2 matrix and x=:+/ .* be matrix multiplication. Fib n using the above method is: A x A x A x ... x A x 0 1 which is equivalent to (A x A x A x ... x A) x 0 1 The expression in parens is A to the power n which can be computed efficiently by repeated squaring. http://www.jsoftware.com/jwiki/Essays/Repeated_Squaring A function that embodies this idea is f7 in: http://www.jsoftware.com/jwiki/Essays/Fibonacci_Sequence#Matrixpower ----- Original Message ----- From: "M.Shimura" <[email protected]> Date: Sunday, March 1, 2009 17:01 Subject: Re: [Jprogramming] fast n-th fiboncci To: [email protected] > > this is very simple and maybe fast > > (0 1 ,: 1 1)&(+/ . *) ^:(i.12) 0 1 > 0 1 > 1 1 > 1 2 > 2 3 > 3 5 > 5 8 > 8 13 > 13 21 > 21 34 > 34 55 > 55 89 > 89 144 > > [email protected] > M.Shimura > > > Inspired by Haskells: http://tinyurl.com/3c3yor > > > > > > ffib=:(+&*:,]*]-~+:@[)/@]`((+&*:,~[*[++:@])/@])@.({...@[)/@(1x > 0,~,.@|....@#:)> > > ffib"0 i.8 > > 1 0 > > 1 1 > > 2 1 > > 3 2 > > 5 3 > > 8 5 > > 13 8 > > 21 13 > > > > ts '{: ffib 100001' > > 0.748854 265536 > > > > 11{. ": {: ffib 100001 > > 42026927029 > > > > > > (slower) variants: > > > > ffib2=: (+&*:,+:@*- > *:@])/@]`((+&*:,~*:@[++:@*)/@])@.({...@[)/@(1x 0,~,.@|....@#:) > > > > ffib3=: (,+/ .*~,,:],-)/@]`(((,~,:~[,+)+/ .*,~)/@])@.({...@[)/@(1x > > 0,~,.@|....@#:) ---------------------------------------------------------------------- For information about J forums see http://www.jsoftware.com/forums.htm
