Skip to content

Instantly share code, notes, and snippets.

@fcannizzaro
Last active March 6, 2016 21:06
Show Gist options
  • Save fcannizzaro/e733a09226e81e0f2f32 to your computer and use it in GitHub Desktop.
Save fcannizzaro/e733a09226e81e0f2f32 to your computer and use it in GitHub Desktop.
c source with 6 different algorithms for Fibonacci's function ( + time )
#include<stdio.h>
#include<stdlib.h>
#include<time.h>
#include<math.h>
// MATRIX UTILS
void mMultiply(int matrix[2][2]){
int tmp = matrix[0][0] + matrix[0][1];
matrix[0][1] = matrix[0][0];
matrix[0][0] = tmp;
tmp = matrix[1][0] + matrix[1][1];
matrix[1][1] = matrix[1][0];
matrix[1][0] = tmp;
}
int mPow(int matrix[2][2] , int n){
if(n > 1){
mPow(matrix, n/2);
int m[2][2];
m[0][0] = matrix[0][0] * matrix[0][0] + matrix[0][1] * matrix[1][0];
m[0][1] = matrix[0][0] * matrix[0][1] + matrix[0][1] * matrix[1][1];
m[1][0] = matrix[1][0] * matrix[0][0] + matrix[1][1] * matrix[1][0];
m[1][1] = matrix[1][0] * matrix[0][1] + matrix[1][1] * matrix[1][1];
matrix[0][0] = m[0][0];
matrix[0][1] = m[0][1];
matrix[1][0] = m[1][0];
matrix[1][1] = m[1][1];
}
if( n % 2 )
mMultiply(matrix);
}
// FIBONACCI
int fibonacci1(int n){
return (pow((1+sqrt(5))/2,n) - pow((1-sqrt(5))/2,n))/sqrt(5);
}
int fibonacci2(int n){
return n <= 2 ? 1 : fibonacci2(n-1) + fibonacci2(n-2);
}
int fibonacci3(int n){
int array[n+1],
i;
array[1] = array[2] = 1;
for (i = 3; i <= n; ++i)
array[i] = array[i-1] + array[i-2];
return array[i-1];
}
int fibonacci4(int n){
int a = 1,
b = 1,
i;
for (i = 3; i <= n; i++){
int c = a + b;
a = b;
b = c;
}
return b;
}
int fibonacci5(int n){
int matrix[2][2] = { 1 , 0 , 0 , 1 },
i,
tmp;
for (i = 1; i < n; i++)
mMultiply(matrix);
return matrix[0][0];
}
int fibonacci6(int n){
int matrix[2][2] = { 1 , 0 , 0 , 1 };
mPow(matrix, n-1);
return matrix[0][0];
}
int timeof(int type, int fn(int) , int n){
int t = time(NULL), res = fn(n);
printf("\n $ fibonacci%d(%d) = %d [%d sec]\n", type , n, res , time(NULL) - t );
}
int main(int argc, char * argv[]){
if(argc < 2){
puts("\n > Pass 'n' value");
return 0;
}
int n = atoi(argv[1]);
timeof(1, &fibonacci1, n);
timeof(2, &fibonacci2, n);
timeof(3, &fibonacci3, n);
timeof(4, &fibonacci4, n);
timeof(5, &fibonacci5, n);
timeof(6, &fibonacci6, n);
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment