#include <iostream>
// Function f returns n'th Fibonacci number
// It uses ALGORITHM 1A: BINARY RECURSION
unsigned int f(int x) {
    return x<2 ? 1 : f(x-1) + f(x-2);
}
// Function f_print prints out n'th Fibonacci number
void f_print(int n) {
    std::cout << n << "th Fibonacci number is " << f(n) << std::endl;
}
// main is the entry point in C++
int main() {
    f_print(46);
}

#include <iostream>
#include <vector>
using std::vector;
using std::cout;
using std::endl;
// Function f returns n'th Fibonacci number
// It uses ALGORITHM 2A: DATA STRUCTURE - SIMPLE LIST
unsigned int f(unsigned int x) {
    vector<unsigned int> fib(2);
    fib[0]=fib[1]=1;
    fib.reserve(x);
    while(x>=fib.size())
        fib.push_back(*(fib.end()-2) + *(fib.end()-1));
    return fib[x];
}
// Function f_print prints out n'th Fibonacci number
void f_print(int n) {
    cout << n << "th Fibonacci number is " << f(n) << endl;
}
// main is the entry point in C++
int main() {
    f_print(46);
}

#include <iostream>
// Function f returns n'th Fibonacci number
// It uses ALGORITHM 2B: SIMPLE RECURSION
unsigned int f(int x, unsigned int n1 = 1, unsigned int n2 = 1) {
    return x<2 ? n1 : f(x-1, n2+n1, n1);
}
// Function f_print prints out n'th Fibonacci number
void f_print(int n) {
    std::cout << n << "th Fibonacci number is " << f(n) << std::endl;
}
// main is the entry point in C++
int main() {
    f_print(46);
}

#include <iostream>
#include <algorithm>
using std::swap;
using std::cout;
using std::endl;
// Function f returns n'th Fibonacci number
// It uses ALGORITHM 2C: NON-RECURSIVE LOOP
unsigned int f(unsigned int x) {
    unsigned int x1=1;
    for(unsigned int i=1,x2=1;i<=x;i++) {
        x1+=x2;
        swap(x1,x2);
    }
    return x1;
}
// Function f_print prints out n'th Fibonacci number
void f_print(int n) {
    cout << n << "th Fibonacci number is " << f(n) << endl;
}
// main is the entry point in C++
int main() {
    f_print(46);
}

#include <iostream>
#include <vector>
using std::vector;
using std::cout;
using std::endl;
// Class Matrix is a small class implementing square matrices
// it defines multiplication (operator*) and integer 
// power (operator^).
template<class T>
class Matrix {
private:
    vector<vector<T> > data;
public:
    Matrix(int size) : data(vector<vector<T> >(size,vector<T>(size,0))) {}
    size_t size(void) const { return data.size(); }
    vector<T> & operator[] (int i) { return data[i]; }
    const vector<T> & operator[] (int i) const { return data[i]; }
    const Matrix operator*(const Matrix& b) const {
        Matrix c(data.size());
        for(unsigned int i=0; i<data.size(); i++)
            for(unsigned int j=0; j<data.size(); j++)
                for(unsigned int k=0; k<data.size(); k++)
                    c[i][j]+=data[i][k]*b[k][j];
        return c;
    }
	const Matrix operator^(const int n) const {
		if(n>1) {
			Matrix a=*this^(n/2);
			return (n%2) ? a*a**this : a*a;
		} else return *this;
    }
};
// Function f returns n'th Fibonacci number
// It uses ALGORITHM 3A: MATRIX EQUATION
unsigned int f(int x) {
    Matrix<unsigned int> a(2);
    a[0][0]=a[0][1]=a[1][0]=1; a[1][1]=0;
    return (a^x)[0][0];
}
// Function f_print prints out n'th Fibonacci number
void f_print(int n) {
    cout << n << "th Fibonacci number is " << f(n) << endl;
}
// main is the entry point in C++
int main() {
    f_print(46);
}

#include <iostream>
using std::cout;
using std::endl;
// structure fib_pair is a pair of Fibonacci numbers
struct fib_pair {
    unsigned int n1, n2;
    fib_pair(unsigned int a = 1, unsigned int b = 1): n1(a), n2(b) {}
};
fib_pair* l(int x) {
    if(x<=1) return new fib_pair;
    if(x==2) return new fib_pair(2,1);
	fib_pair *k, *r;
    if(x%2) {   
        k = l((x-1)/2);
		r = new fib_pair( k->n1*(k->n1+k->n2) + k->n1*k->n2 ,
                          k->n1*k->n1 + k->n2*k->n2 );
    } else {
        k = l((x/2)-1);
        r = new fib_pair( (k->n1+k->n2)*(k->n1+k->n2) + k->n1*k->n1 ,
                          (k->n1+k->n2)*k->n1 + k->n1*k->n2 );
    }
	delete k; return r;
}
// Function f returns n'th Fibonacci number
// It uses ALGORITHM 3B: FAST RECURSION
unsigned int f(int x) {
    fib_pair* k=l(x);
	unsigned int r=k->n1;
	delete k; return r;
}
// Function f_print prints out n'th Fibonacci number
void f_print(int n) {
    cout << n << "th Fibonacci number is " << f(n) << endl;
}
// main is the entry point in C++
int main() {
    f_print(46);
}

#include <iostream>
#include <cmath>
using std::cout;
using std::endl;
using std::pow;
using std::sqrt;
// Function f returns n'th Fibonacci number
// It uses ALGORITHM 3C: BINET'S FORMULA
unsigned int f(int x) {
    double phi=(1+sqrt(5.0))/2;
    double n=(pow(phi,x+1)-pow(1-phi,x+1))/sqrt(5.0);
	return static_cast<unsigned int>(n);
}
// Function f_print prints out n'th Fibonacci number
void f_print(int n) {
    cout << n << "th Fibonacci number is " << f(n) << endl;
}
// main is the entry point in C++
int main() {
    f_print(46);
}