fib_method.cpp

// 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;
}