Skip to content

Instantly share code, notes, and snippets.

@grantmwilliams
Last active August 29, 2015 14:26
Show Gist options
  • Save grantmwilliams/c89942e35f1b1d41df0d to your computer and use it in GitHub Desktop.
Save grantmwilliams/c89942e35f1b1d41df0d to your computer and use it in GitHub Desktop.
// fib_method.cpp -- Grant Williams \\
#include <stdio.h>
#include <fstream>
#include <math.h>
using namespace std;
//Uses matrix operations \\
void multiply(int F[2][2], int M[2][2]);
void power(int F[2][2], int n);
// function that returns nth Fibonacci number \\
int fib(int n)
{
int F[2][2] = {{1,1},{1,0}};
if (n == 0)
return 0;
power(F, n-1);
return F[0][0];
}
void power(int F[2][2], int n)
{
if( n == 0 || n == 1)
return;
int M[2][2] = {{1,1},{1,0}};
power(F, n/2);
multiply(F, F);
if (n%2 != 0)
multiply(F, M);
}
void multiply(int F[2][2], int M[2][2])
{
int x = F[0][0]*M[0][0] + F[0][1]*M[1][0];
int y = F[0][0]*M[0][1] + F[0][1]*M[1][1];
int z = F[1][0]*M[0][0] + F[1][1]*M[1][0];
int w = F[1][0]*M[0][1] + F[1][1]*M[1][1];
F[0][0] = x;
F[0][1] = y;
F[1][0] = z;
F[1][1] = w;
}
int main(int argc, char** argv) {
// File Parsing for Code Eval \\
ifstream fileInput;
fileInput.open(argv[1]);
int value;
while (fileInput >> value) {
printf("%d \n", fib(value));
getchar();
}
return 0;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment