Skip to content

Instantly share code, notes, and snippets.

@yoshiokatsuneo
Created March 8, 2012 09:21
Show Gist options
  • Save yoshiokatsuneo/1999881 to your computer and use it in GitHub Desktop.
Save yoshiokatsuneo/1999881 to your computer and use it in GitHub Desktop.
fibonacci in javascript (O(log(N)))
function multiply_matrix(a, b)
{
var c = new Array;
for(y=0;y<a.length;y++){
c[y] = new Array;
for(x=0;x<b[0].length;x++){
sum = 0;
for(i=0;i<a[0].length;i++){
sum += a[y][i] * b[i][x];
}
c[y][x] = sum;
}
}
return c;
}
function pow_matrix(a, n)
{
if(n == 1){return a;}
half = pow_matrix(a, ((n-(n%2))/2));
ret = multiply_matrix(half, half);
if(n%2){
ret = multiply_matrix(ret, a);
}
return ret;
}
function fibonacci(n){
// [f(n+2), f(n+1)] = [[1,1], [1,0]] [f(n+1), f(n)];
// [f(n+2), f(n+1)] = [[1,1], [1,0]]^n [1, 0];
a = [[1, 1], [1,0]];
a_n = pow_matrix(a, n);
start = [[1], [0]];
end = multiply_matrix(a_n, start);
return end[1][0];
}
print (fibonacci(arguments[0]));
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment