Your algorithm will not compute the correct result for large N's, due to the floating point errors of sqrn(5).
In order to speed up your algorithm you can use fast doubling Fibonacci:
F(2k) = F(k)[2F(k+1) - F(k)]
F(2k+1) = F(k+1)^2 + F(k)^2
Applying modulo arithmetics, your final fastest algorithm would be:
F(2k) = F(k)[2F(k+1) - F(k)] % 10000
F(2k+1) = (F(k+1)^2 + F(k)^2) % 10000
Using this approach, your function never exceeds 10000, thus an int
type suffices.
EDIT: Okay I had some free time on a Friday night (not a good thing I guess) and implemented the algorithm. I implemented two versions, first one with O(1) memory and O(lg n) time complexity and second one using a cache, with memory and worst-case runtime of O(lg n), but with a best case runtime of O(1).
#include <iostream>
#include <unordered_map>
using namespace std;
const int P = 10000;
/* Fast Fibonacci with O(1) memory and O(lg n) time complexity. No cache. */
int fib_uncached (int n)
{
/* find MSB position */
int msb_position = 31;
while (!((1 << (msb_position-1) & n)) && msb_position >= 0)
msb_position--;
int a=0, b=1;
for (int i=msb_position; i>=0;i--)
{
int d = (a%P) * ((b%P)*2 - (a%P) + P),
e = (a%P) * (a%P) + (b%P)*(b%P);
a=d%P;
b=e%P;
if (((n >> i) & 1) != 0)
{
int c = (a + b) % P;
a = b;
b = c;
}
}
return a;
}
/* Fast Fibonacci using cache */
int fib (int n)
{
static std::unordered_map<int,int> cache;
if (cache.find(n) == cache.end())
{
int f;
if (n==0)
f = 0;
else if (n < 3)
f = 1;
else if (n % 2 == 0)
{
int k = n/2;
f = (fib(k) * (2*fib(k+1) - fib(k))) % P;
}
else
{
int k = (n-1)/2;
f = (fib(k+1)*fib(k+1)+ fib(k) * fib(k)) % P;
}
if (f<0)
f += P;
cache[n] = f;
}
return cache.at(n);
}
int main ()
{
int i ;
cin >> i;
cout << i << " : " << fib(i) << endl;
return 0;
}
Reference for cache-less implementations: https://www.nayuki.io/page/fast-fibonacci-algorithms