Sum of Fibonacci Numbers | C ++ Program to find sum of Fibonacci numbers in O ( Log n ) time . ; Create an array for memoization ; Returns n 'th Fibonacci number using table f[] ; Base cases ; If fib ( n ) is already computed ; Applying above formula [ Note value n & 1 is 1 if n is odd , else 0 ] . ; Computes value of first Fibonacci numbers ; Driver program to test above function
#include <bits/stdc++.h> NEW_LINE using namespace std ; const int MAX = 1000 ; int f [ MAX ] = { 0 } ; int fib ( int n ) { if ( n == 0 ) return 0 ; if ( n == 1 n == 2 ) return ( f [ n ] = 1 ) ; if ( f [ n ] ) return f [ n ] ; int k = ( n & 1 ) ? ( n + 1 ) / 2 : n / 2 ; 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 ] ; } int calculateSum ( int n ) { return fib ( n + 2 ) - 1 ; } int main ( ) { int n = 4 ; cout << " Sum ▁ of ▁ Fibonacci ▁ numbers ▁ is ▁ : ▁ " << calculateSum ( n ) << endl ; return 0 ; }