How to make it fast? Is my formula correct?

Posted by

Alexey 23 Aug 2006 19:59

I use Fib(n-1)+Fib(n+1).

I can find Fib(n) in O(log n).

But the long arithmetics makes my programm too slow.

Help, please.

Re: How to make it fast? Is my formula correct?

Read below some solutions. Your formula is correct, I used it too and recursevly computed the F[n]. I used long arithmetics in base 1.000.000 and it runs quick enough.

Re: How to make it fast? Is my formula correct?

Better use long arithmetics base 2^P, and then fetch decimal answer by sequential divisions by 1'000'000 or something like that.