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;
}

Trim, ltrim, rtrim / strip, lstrip, rstrip fucntions for javascript

In programming, trim or strip is a string manipulation function or algorithm which removes leading and trailing whitespace from a string. ltrim removes only leading trailing whitespaces and rtrim removes only trailing whitespaces and trim removes both leading and trailing whitespaces.
Trim, ltrim and rtrim are also known as strip, lstrip and rstrip, respectively.

Javascript does not have its own trim or strip function. But you can define your own. Write the codes given below in your source code and you can use them as you do in other languages. Take care, that these codes should be written in your code before they are called.

trim:

String.prototype.trim = function() {
return this.replace(/^\s*|\s*$/g, "")
}

ltrim:

String.prototype.trim = function() {
return this.replace(/^\s*/g, "")
}

rtrim:

String.prototype.trim = function() {
return this.replace(/\s*$/g, "")
}

After writing the above codes you can use the functions normally. A few examples are:-

trimmed_str=str.trim();
trimmed_str=' someString '.trim();
str=str.ltrim();
str=str1.rtrim() + str2.rtrim();

Technorati: javascript, programming, code-snippets