Calculate nth fibonacci number in O(log(n))

I wrote this function that calculates nth fibonacci number in O(log(n)) time complexity and O(log(n)) space complexity. This is helpful when n is very large. You can't calculate nth fib iteratively when n is say 2^31. You need O(log(n)) or better algorithm for that. However the below function can't calculate 2^31th fib because it won't fit into long long. But my point now is to just present the implementation of O(log(n)) algo for small integers. It can be easily adapted to any integer(however large) if you have a BigInt library. I will try to write the BigInt version later when I get time.

The logic behind this algo is explained here. Note that this algo does not use any approximation. Its 100% accurate. The O(1) alogs available for this use approximation and MAY give wrong answers for some value of n.
Note that F(0)=0 and F(1)=1.

/*
* This function computes the nth fibonacci number in log(n) time and log(n) space complexity.
* This is helpful when we need to calculate fibonacci number where n is very large.
* Note that when n is large, fib(n) won't fit in integer.
* So essentially this function will have to be adapted for bigint.
*
* We assume F(0)=0 and F(1)=1.
*
* Note that this function does not use any approximation. Its 100% accurate.
*/
#include
#include
#include
#include
#include
using namespace std;
int Fibonacci(int n)
{
if(n<=1)return n;
int *nums=NULL,*values=NULL,ret,ctr,a,b,i;
nums = new int[int(ceil(4*log(n)))+4];
ctr=0;
nums[ctr++]=n;
for(i=0;i if(nums[i]>1)
{
if(nums[i]&1) // if odd
{
if(find(nums+i+1,nums+ctr,(nums[i]+1)/2)==nums+ctr)
nums[ctr++]=(nums[i]+1)/2;
if(find(nums+i+1,nums+ctr,(nums[i]+1)/2-1)==nums+ctr)
nums[ctr++]=(nums[i]+1)/2-1;
}
else // if even
{
if(find(nums+i+1,nums+ctr,nums[i]/2)==nums+ctr)
nums[ctr++]=nums[i]/2;
if(find(nums+i+1,nums+ctr,nums[i]/2-1)==nums+ctr)
nums[ctr++]=nums[i]/2-1;
}
}
values = new int[ctr];
for(i=ctr-1;i>=0;i--)
{
if(nums[i]<=1)values[i]=nums[i];
else if(nums[i]&1) // if odd
{
a=values[find(nums+i+1,nums+ctr,(nums[i]+1)/2)-nums];
b=values[find(nums+i+1,nums+ctr,(nums[i]+1)/2-1)-nums];
values[i]=a*a+b*b;
}
else // if even
{
a=values[find(nums+i+1,nums+ctr,nums[i]/2)-nums];
b=values[find(nums+i+1,nums+ctr,nums[i]/2-1)-nums];
values[i]=(2*b+a)*a;
}
}
ret = values[0];
delete nums;
delete values;
return ret;
}
int main()
{
int n;
while(scanf(" %d",&n)!=EOF)
printf("%d\n",Fibonacci(n));
return 0;
}