Created
June 14, 2011 21:39
-
-
Save ameerkat/1025967 to your computer and use it in GitHub Desktop.
Calculating Fibonacci numbers with matrices
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
/* Fibonacci Calculation using Matrices | |
* Ameer Ayoub <ameer.ayoub@gmail.com> | |
* Jun 13, 2011 | |
*/ | |
#include <iostream> | |
#include <math.h> | |
using namespace std; | |
const int fib_matrix_size = 2; | |
void fib_multiply_matrix(int fm1[][fib_matrix_size], | |
int fm2[][fib_matrix_size], | |
int fmr[][fib_matrix_size]){ | |
/* Performs fib_matrix_size * fib_matrix_size matrix | |
* multiplication on the input matrices, putting the | |
* result into fmr (fib_matrix_result) | |
*/ | |
fmr[0][0] = fm1[0][0] * fm2[0][0] + fm1[0][1] * fm2[1][0]; | |
fmr[0][1] = fm1[0][0] * fm2[0][1] + fm1[0][1] * fm2[1][1]; | |
fmr[1][0] = fm1[1][0] * fm2[0][0] + fm1[1][1] * fm2[1][0]; | |
fmr[1][1] = fm1[1][0] * fm2[0][1] + fm1[1][1] * fm2[1][1]; | |
} | |
void fib_copy_matrix(int m1[][fib_matrix_size], int m2[][fib_matrix_size]){ | |
/* copies from m2 into m1, like strcpy param order */ | |
for(int i = 0; i < fib_matrix_size; i++) | |
for(int j = 0; j < fib_matrix_size; j++) | |
m1[i][j] = m2[i][j]; | |
} | |
double log2(double x){ | |
return log10(x) / log10(2.0); | |
} | |
int calc_fib_matrix(int fmx[][fib_matrix_size], int n){ | |
int exp = (int)log2(n); | |
int diff = n - exp; | |
int fmir1[fib_matrix_size][fib_matrix_size]; | |
int fmir2[fib_matrix_size][fib_matrix_size]; | |
fib_copy_matrix(fmir2, fmx); | |
for(;exp != 1; exp /= 2){ | |
fib_multiply_matrix(fmir2, fmir2, fmir1); | |
fib_copy_matrix(fmir2, fmir1); | |
} | |
for(int i = 0; i < diff; ++i){ | |
// We can probably reduce this | |
fib_multiply_matrix(fmir2, fmx, fmir1); | |
fib_copy_matrix(fmir2, fmir1); | |
} | |
return fmir2[0][1]; | |
} | |
int rfib(int n){ | |
return (n <= 1) ? n : rfib(n-1)+rfib(n-2); | |
} | |
int main(){ | |
int fm[fib_matrix_size][fib_matrix_size] = {{1, 1}, {1, 0}}; | |
int f6 = calc_fib_matrix(fm, 6); | |
int rf6 = rfib(6); | |
cout << "6th Fibonacci Number: " << f6 << " (expected: " << rf6 << ")" << endl; | |
return 0; | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment