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

```