mike_liz.day@tiscali.co.uk on Fri, 08 Jan 2016 19:25:07 +0100 |
[Date Prev] [Date Next] [Thread Prev] [Thread Next] [Date Index] [Thread Index]
Re: fibonacci(n) for large n's |
Whether or not you're working modulo something, consider the 2x2 matrix M = [0 1] [1 1] , ie with all Mij = 1 except for M11 = 0 . Let MM (i) be M to the power 2^i . If n = sum of 2^ai, then the product of MM (ai) yields the required fibonacci number in the (2,1) position. So: (17:56) gp > M=matrix(2,2,x,y,1<max(x,y)) \\ set up matrix M %16 = [0 1] [1 1] (17:57) gp > MM(i)={M^2^i} \\ set up function MM %17 = (i) ->M^2^i (17:57) gp > q=apply(MM,[0,1,3]) \\ 11 = 1 + 2 + 8 = sum 2^0 1 3 %18 = [[0, 1; 1, 1], [1, 1; 1, 2], [13, 21; 21, 34]] (17:57) gp > prod(x=1,3,q[x]) \\ product of the 3 matrices %19 = [55 89] [89 144] (18:05) gp > M^11 \\ compare the straightforward (but slower) way %22 = [55 89] [89 144] 89 is the 11th or 12th Fibonacci number, depending on where you set the origin. 10^10 is approximately 2^33, so you don't need to apply MM too many times. But you probably need to restrict M with a modulus function, eg M = Mod(M,101) .... Any use? Mike On 08/01/2016 08:28, Ralf Stephan wrote: > You're sure you want the complete number as result, or only modulo something, like in some Project Euler puzzles? > > On Fri, Jan 8, 2016 at 9:03 AM Zak Seidov <zakseidov@yahoo.com> wrote: > > > Dear pari gurus, > what is the fastest way to calculate fibonacci numbers > other than just fibonacci(n) for large n's (>~10^10, say). > Thx, > Zak