Re: fibonacci(n) for large n's

[Karim Belabas <Karim.Belabas@math.u-bordeaux.fr>]

* Zak Seidov [2016-01-09 18:11]:
>  Great, 
> Bill's code is much more faster than standard fibonacci(n).

It's not. They should have the same order of complexity, fibonacci()
being a little faster.

(18:16) gp > myfibo(100000000);
time = 1,814 ms.
(18:17) gp > fibonacci(100000000);
time = 1,294 ms.

On the other hand, myfibomod(n, m) is indeed going to be faster if
the modulus m is much smaller than (golden ratio)^n.

Cheers,

    K.B.

[...]
>>Bill Allombert <Bill.Allombert@math.u-bordeaux.fr>:
>>
>>One simpler and faster way is 
>>myfibo(n)=polcoeff(lift(Mod(x,x^2-x-1)^n),1)
>>
>>which you can restrict mod m:
>>myfibomod(n,m)=polcoeff(lift(Mod(x*Mod(1,m),x^2-x-1)^n),1)
--
Karim Belabas, IMB (UMR 5251)  Tel: (+33) (0)5 40 00 26 17
Universite de Bordeaux         Fax: (+33) (0)5 40 00 69 50
351, cours de la Liberation    http://www.math.u-bordeaux.fr/~kbelabas/
F-33405 Talence (France)       http://pari.math.u-bordeaux.fr/  [PARI/GP]
`