possible improvement to fibonacci number calculations

[Paul Zimmermann]

       Dan,

> From: <schult25 at illinois.edu>
> Date: Sun, 10 Jan 2010 04:04:46 -0600 (CST)
> 
> to whom it may concern:
> 
> I recently tried to cook up a good fibonacci algorithm, as I was in a competition with mathematica (sorry!). I know that mathematica uses GMP for multi-precision calculations, so I though if I were going to beat it, I would need a better algorithm. Surprisingly, with the straight foward implementation in mathematica of the equations:
> f = fibonacci numbers, l = lucas numbers,
> f(2n) = f(n) * l(n) 
> l(2n) = l(n) ^ 2 - 2*(-1)^n 
> f(2n+1) = l(n) * (f(n) + l(n)) / 2 - (-1)^n 
> l(2n+1) = l(n) * (5 * f(n) + l(n)) / 2 - (-1)^n 
> I was able to beat it 5-10%.
> But then, I noticed that the GMP fibonacci algorithm is linked in the dll file that mathematica uses - which leads me to beleive that it is using the GMP algorithm directly.
> It is possible that the above algorithm could be better than GMP's algorithm which only uses squares but has more additions?

I doubt, since usually a square costs 2/3 of a multiply in the FFT range,
and additions are negligible.

> Note: the equations:
> f(3n) = f(n) (l(n)^2 - (-1)^n)
> l(3n) = l(n) (l(n)^2 - 3*(-1)^n)
> ...
> could be used to give the best algorithm, since 2/log(2) > 3/log(3) < 4/log(4).

if you count 2/3 for a square, then GMP's algorithm has constant 4/3/log(2),
which is about 1.92, whereas the above has constant 8/3/log(3), about 2.43,
thus I guess GMP's algorithm is hard to beat.

> Any feedback would be appreciated.
> 
> Sincerely,
> Dan

Paul Zimmermann