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.

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.

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