// This program calculates the nth fibonacci number
// using alrogirhtm 1A: naive binary recursion
//
// compiled: g++ -std=c++0x -Wall -Wextra -pedantic -O2 -march=native -o f1a f1a.cc
// executed: ./f1a n
//
#include <iostream>
#include <stdexcept>
#include <vector>

// Naive binary recursion: F(n) = F(n-1) + F(n-2)
long fib(int n) {
    return n<2 ? n : fib(n-1) + fib(n-2);
}
// Function f(n) handles the negative arguments: F(-n) = F(n)*(-1)^(n+1) 
long f(int n) {
    if(n<0)
       return n%2 ? fib(-n) : -fib(-n);
    else
       return fib(n);
}
// Function f_print prints out n'th Fibonacci number
void fib_print(int n) {
    std::cout << n << "th Fibonacci number is " << f(n) << '\n';
}
// entry point:
// convert the first argument to a number and calls fib_print
// if argument did not exist or wasn't a number, show usage information
int main(int argc, char** argv) {
    std::vector<std::string> args(argv, argv+argc);
    try {
        fib_print(stoi(args.at(1)));
    } catch (std::exception& ) {
        std::cout << "Usage: " << args[0] << " <n>\n";
    }
}

// This program calculates the nth fibonacci number
// using algorithm 1B: cached binary recursion
//
// compile: g++ -std=c++0x -O2 -o f1b f1b.cc -lgmpxx -lgmp
// executed: ./f1b n

#include <iostream>
#include <stdexcept>
#include <unordered_map>
#include <gmpxx.h>
#include <vector>
typedef std::unordered_map<int, mpz_class> memo;

// Naive binary recursion: F(n) = F(n-1) + F(n-2) with memoization
// First checks if the answer is known, reports it if it is known
// then recurses twice, saves the new answer, and returns it.
mpz_class frec(int n, memo& m) {
   memo::iterator i = m.find(n);
   if(i!=m.end()) return i->second;
   return n<2 ? n : m[n] = frec(n-1, m) + frec(n-2, m);
}

// Function fib initializes the memoization data structure and calls frec
mpz_class fib(int n) {
    memo m;
    return frec(n, m);
}

// Function f(n) handles the negative arguments: F(-n) = F(n)*(-1)^(n+1)
mpz_class f(int n) {
    if(n<0)
        return n%2 ? fib(-n) : 0-fib(-n);
    else
        return fib(n);
}

// Function fib_print prints out n'th Fibonacci number
void fib_print(int n) {
    std::cout << n << "th Fibonacci number is "
              << f(n).get_str(10) << '\n';
}
// entry point:
// convert the first argument to a number and calls fib_print
// if argument did not exist or wasn't a number, show usage information
int main(int argc, char** argv) {
    std::vector<std::string> args(argv, argv+argc);
    try {
        fib_print(stoi(args.at(1)));
    } catch (std::exception& ) {
        std::cout << "Usage: " << args[0] << " <n>\n";
    }
}

// This program calculates the nth fibonacci number
// using algorithm 2A: cached linear iteration with random-access container
//
// compile: g++ -std=c++0x -O2 -o f2a f2a.cc -lgmpxx -lgmp
// executed: ./f2a n
//
#include <iostream>
#include <algorithm>
#include <sstream>
#include <gmpxx.h>
#include <vector>

// Function fib creates an array of zeroes large enough to hold all Fibonacci
// numbers up to the one requested (but no less than 2), sets F(1) = 1, and
// then executes f(i) = f(i-2)+f(i-1) for all elements of the array from f(2)
// to f(n).
mpz_class fib(int n) {
    std::vector<mpz_class> flist(1+std::max(n,1), 0);
    flist[1]=1;
    transform(  flist.begin(), flist.end()-2,
              ++flist.begin(), flist.begin()+2,
              std::plus<mpz_class>());
    return flist[n];
}

// A purely recursive way to solve this would have been something like
// mpz_class flrec(std::deque<mpz_class>& fl, int n)
// {
//     fl.push_back(fl.back() + *++fl.rbegin());
//     return n<1 ? fl.back() : flrec(fl, n-1);
// }
// mpz_class fib(int n) {
//     std::deque<mpz_class> fl(1,0); fl.push_back(1);
//     return n<2 ? n : flrec(fl, n-2);
// }

// Function f(n) handles the negative arguments: F(-n) = F(n)*(-1)^(n+1)
mpz_class f(int n) {
    if(n<0)
        return n%2 ? fib(-n) : 0-fib(-n);
    else
        return fib(n);
}

// Function fib_print prints out n'th Fibonacci number
void fib_print(int n) {
    std::cout << n << "th Fibonacci number is "
              << f(n).get_str(10) << '\n';
}
// entry point
// check the number of command line arguments
// convert the first argument to a number and calls fib_print
// if argument did not exist or wasn't a number, show usage information
int main(int argc, char** argv) {
    std::vector<std::string> args(argv, argv+argc);
    try {
        fib_print(stoi(args.at(1)));
    } catch (std::exception& ) {
        std::cout << "Usage: " << args[0] << " <n>\n";
    }
}

// This program calculates the nth fibonacci number
// using algorithm 2B: linear recursion with accumulator
//
// compile: g++ -std=c++0x -O2 -o f2b f2b.cc -lgmpxx -lgmp
// executed: ./f2b n
//
#include <iostream>
#include <sstream>
#include <gmpxx.h>
#include <vector>

// Function fib(x) calculates F(n) by linear recursion
// keeping two accumulators, F(n-1) and F(n-2)
mpz_class fib(int x, mpz_class x1 = 0, mpz_class x2 = 1) {
    return x<1 ? x1 : fib(x-1, x2+x1, x1);
}

// Function f(n) handles the negative arguments: F(-n) = F(n)*(-1)^(n+1)
mpz_class f(int n) {
    if(n<0)
        return n%2 ? fib(-n) : 0-fib(-n);
    else
        return fib(n);
}

// Function fib_print prints out n'th Fibonacci number
void fib_print(int n) {
    std::cout << n << "th Fibonacci number is "
              << f(n).get_str(10) << '\n';
}
// entry point
// check the number of command line arguments
// convert the first argument to a number and calls fib_print
// if argument did not exist or wasn't a number, show usage information
int main(int argc, char** argv) {
    std::vector<std::string> args(argv, argv+argc);
    try {
        fib_print(stoi(args.at(1)));
    } catch (std::exception& ) {
        std::cout << "Usage: " << args[0] << " <n>\n";
    }
}

// This program calculates the nth fibonacci number
// using algorithm 2C: imperative loop with mutable variables
//
// compile: g++ -std=c++0x -O2 -o f2c f2c.cc -lgmpxx -lgmp
// executed: ./f2c n
//
#include <iostream>
#include <algorithm>
#include <sstream>
#include <gmpxx.h>
#include <vector>

// Function fib(x) calculates F(abs(x)) by repeating x1=x1+x2; swap(x1,x2)
// and returns negative result if x was even and negative
mpz_class fib(int x) {
    mpz_class x1=0;
    mpz_class x2=1;
    for(int i=1; i<=(x<0?-x:x); ++i)
        std::swap(x1+=x2,x2);
    return (x<0 && x%2==0) ? 0-x1 : x1;
}
// Function fib_print prints out n'th Fibonacci number
void fib_print(int n) {
    std::cout << n << "th Fibonacci number is "
              << fib(n).get_str(10) << '\n';
}
// entry point
// check the number of command line arguments
// convert the first argument to a number and calls fib_print
// if argument did not exist or wasn't a number, show usage information
int main(int argc, char** argv) {
    std::vector<std::string> args(argv, argv+argc);
    try {
        fib_print(stoi(args.at(1)));
    } catch (std::exception& ) {
        std::cout << "Usage: " << args[0] << " <n>\n";
    }
}

// This program calculates the nth fibonacci number
// using algorithm 3A: matrix multiplication
//
// compile: g++ -std=c++0x -O2 -o f3a f3a.cc -lgmpxx -lgmp
// executed: ./f3a n

#include <iostream>
#include <sstream>
#include <gmpxx.h>
#include <vector>
#include <boost/numeric/ublas/matrix.hpp> 
typedef boost::numeric::ublas::matrix<mpz_class> matrix;
typedef boost::numeric::ublas::identity_matrix<mpz_class> identity_matrix;

// This overload of operator ^ raises a martix to integer power
// using repeated squaring.
matrix operator^(const matrix& a, int n) {
    if(n<=0) return identity_matrix(a.size1(), a.size2());
    matrix b(prod(a,a));
    return n&1 ? prod(a,b^n>>1) : b^n>>1;
}

// Function fib prepares the (1,1)(1,0) matrix, raises it
// to the x-1'st power, and returns the top left corner of the matrix
mpz_class fib(int x) {
    matrix A(2,2);
    A(0,0)=A(0,1)=A(1,0)=1; A(1,1)=0;
    return x==0 ? 0 : (A^(x-1))(0,0);
}

// Function f(n) handles the negative arguments: F(-n) = F(n)*(-1)^(n+1)
mpz_class f(int n) {
    if(n<0)
        return n%2 ? fib(-n) : 0-fib(-n);
    else
        return fib(n);
}

// Function fib_print prints out n'th Fibonacci number
void fib_print(int n) {
    std::cout << n << "th Fibonacci number is "
              << f(n).get_str(10) << '\n';
}
// entry point
// check the number of command line arguments
// convert the first argument to a number and calls fib_print
// if argument did not exist or wasn't a number, show usage information
int main(int argc, char** argv) {
    std::vector<std::string> args(argv, argv+argc);
    try {
        fib_print(stoi(args.at(1)));
    } catch (std::exception& ) {
        std::cout << "Usage: " << args[0] << " <n>\n";
    }
}

// This program calculates the nth fibonacci number
// using algorithm 3B: fast recursion
//
// compile: g++ -std=c++0x -O2 -o f3b f3b.cc -lgmpxx -lgmp
// executed: ./f3b n

#include <iostream>
#include <sstream>
#include <vector>
#include <gmpxx.h>

// calculate a pair of fibonacci numbers according to
// the recurrent relationship: 
// F(2n-1) = F(n-1)^2 + F(n)^2
// F(2n) = (2F(n-1) + F(n))F(n)
//
// in this function, f1 = F(n-1), f2 = F(n), f3 = F(n+1)
std::pair<mpz_class, mpz_class> fib_rec(int n) {
    if(n<=0) return {0,0};
    if(n==1) return {0,1};
    auto k = fib_rec(n/2);
    mpz_class f1 = k.first;
    mpz_class f2 = k.second;
    mpz_class f3 = f1+f2;
    if (n%2) return { (f1+f3)*f2, f3*f3+f2*f2 };
    else     return { f1*f1+f2*f2, (f1+f3)*f2 };
}

// Function fib calls fib_rec and returns the second of the two
// values returned. 
mpz_class fib(int x) {
    return fib_rec(x).second;
}

// Function f(n) handles the negative arguments: F(-n) = F(n)*(-1)^(n+1)
mpz_class f(int n) {
    if(n<0)
        return n%2 ? fib(-n) : 0-fib(-n);
    else
        return fib(n);
}

// Function fib_print prints out n'th Fibonacci number
void fib_print(int n) {
    std::cout << n << "th Fibonacci number is "
              << f(n).get_str(10) << '\n';
}
// entry point
// check the number of command line arguments
// convert the first argument to a number and calls fib_print
// if argument did not exist or wasn't a number, show usage information
int main(int argc, char** argv) {
    std::vector<std::string> args(argv, argv+argc);
    try {
        fib_print(stoi(args.at(1)));
    } catch (std::exception& ) {
        std::cout << "Usage: " << args[0] << " <n>\n";
    }
}

// This program calculates the nth fibonacci number
// using algorithm 3C: Binet's formula with rounding
//
// compile: g++ -std=c++0x -O2 -o f3c f3c.cc -lgmpxx -lgmp
// executed: ./f3c n

#include <iostream>
#include <sstream>
#include <vector>
#include <gmpxx.h>

// This overload of operator ^ raises a number to integer power
// using repeated squaring.
mpf_class operator^(const mpf_class& a, int n) {
   if(n<=0) return 1;
   mpf_class b = a*a;
   b = b^n>>1;
   return n&1 ? a*b : b;
}

// This function calculates the nth fibonacci number
// as floor( phi^n/sqrt(5) + 1/2), where phi = (1+sqrt(5.0))/2;
mpz_class fib(int x) {
    mpf_class five(5, 0.7*x); // 5.0 with precision of x*log_2(phi) = 0.694*x
    mpf_class sqrt5 = sqrt(five);
    mpf_class phi = (1+sqrt5)/2;
    return floor((phi^x)/sqrt5 + 0.5);
}

// Function f(n) handles the negative arguments: F(-n) = F(n)*(-1)^(n+1)
mpz_class f(int n) {
    if(n<0)
        return n%2 ? fib(-n) : 0-fib(-n);
    else
        return fib(n);
}

// Function fib_print prints out n'th Fibonacci number
void fib_print(int n) {
    std::cout << n << "th Fibonacci number is "
              << f(n).get_str(10) << '\n';
}
// entry point
// check the number of command line arguments
// convert the first argument to a number and calls fib_print
// if argument did not exist or wasn't a number, show usage information
int main(int argc, char** argv) {
    std::vector<std::string> args(argv, argv+argc);
    try {
        fib_print(stoi(args.at(1)));
    } catch (std::exception& ) {
        std::cout << "Usage: " << args[0] << " <n>\n";
    }
}