possible improvement to fibonacci number calculations

schult25 at illinois.edu schult25 at illinois.edu
Sun Jan 10 11:04:46 CET 2010


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?
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).
Any feedback would be appreciated.

Sincerely,
Dan


More information about the gmp-devel mailing list