fibo.cpp

// C++ Program to find n'th fibonacci Number in 
// with O(Log n) arithmatic operations 
#include <stdlib.h>
#include<iostream>

using namespace std; 

const int MAX = 1000; 

// Create an array for memoization 
int f[MAX] = {0}; 

// Returns n'th fuibonacci number using table f[] 
int fib(int n) 
{ 
	// Base cases 
	if (n == 0) 
		return 0; 
	if (n == 1 || n == 2) 
		return (f[n] = 1); 

	// If fib(n) is already computed 
	if (f[n]) 
		return f[n]; 

	int k = (n & 1)? (n+1)/2 : n/2; 

	// Applyting above formula [Note value n&1 is 1 
	// if n is odd, else 0. 
	f[n] = (n & 1)? (fib(k)*fib(k) + fib(k-1)*fib(k-1)) 
		: (2*fib(k-1) + fib(k))*fib(k); 

	return f[n]; 
} 

/* Driver program to test above function */
int main() 
{ 
	int n = 3,d=0; 
	for(int i=0;i<n;i++){
		d=d+fib(n);;
	}
	cout<<d;
	return 0; 
}