Re: fibonacci(n) for large n's

["mike_liz.day@tiscali.co.uk" <mike_liz.day@tiscali.co.uk>]

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