Skip to content

Instantly share code, notes, and snippets.

@jeffs
Last active August 29, 2015 14:04
Show Gist options
  • Save jeffs/98f5e9f77a77340b98b0 to your computer and use it in GitHub Desktop.
Save jeffs/98f5e9f77a77340b98b0 to your computer and use it in GitHub Desktop.
O(log(N)) Fibonacci computation
/* Computation of the Nth Fibonacci number in O(log(N)) time.
*
* clang++ -o fibs -pedantic -Wall fibs.cpp
*
* The program prints a sequence of lines each containing three values: an
* integer index, the Fibonacci number at that index, and the number of matrix
* multiplications required to compute the number.
*
* This code uses an arbitrary-precision integer type from Boost, just because
* it's fun to play with big numbers, but you can remove the #include, and
* typedef long cpp_int (or some other big integer type) if you don't Boost.
*/
#include <boost/multiprecision/cpp_int.hpp>
using boost::multiprecision::cpp_int;
typedef cpp_int matrix[2][2];
const matrix identity = {
{ 1, 0 },
{ 0, 1 }
};
void copy(matrix r, const matrix m)
{
r[0][0] = m[0][0];
r[0][1] = m[0][1];
r[1][0] = m[1][0];
r[1][1] = m[1][1];
}
int mult_count = 0;
void mult(matrix r, const matrix m)
{
matrix t = {
{ r[0][0] * m[0][0] + r[0][1] * m[1][0],
r[0][0] * m[0][1] + r[0][1] * m[1][1] },
{ r[1][0] * m[0][0] + r[1][1] * m[1][0],
r[1][0] * m[0][1] + r[1][1] * m[1][1] }
};
copy(r, t);
++mult_count;
}
void pow(matrix r, int n)
{
if (n == 0) {
copy(r, identity);
} else if (n == 1) {
/* Do nothing. */
} else if (n % 2 == 0) {
pow(r, n / 2);
mult(r, r);
} else {
matrix t;
copy(t, r);
pow(r, n - 1);
mult(r, t);
}
}
const matrix seed = {
{ 0, 0 },
{ 0, 1 }
};
const matrix factor = {
{ 0, 1 },
{ 1, 1 }
};
cpp_int fib(int n)
{
matrix a, r;
copy(a, seed);
copy(r, factor);
pow(r, n);
mult(a, r);
return a[1][0];
}
#include <iostream>
int main()
{
for (int i = 0; i < 100; ++i) {
mult_count = 0;
cpp_int v = fib(i);
std::cout << i << '\t' << v << '\t' << mult_count << '\n';
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment