Fast Doubling method to find the Nth Fibonacci number | C ++ program to find the Nth Fibonacci number using Fast Doubling Method ; Function calculate the N - th fibanacci number using fast doubling method ; Base Condition ; Here a = F ( n ) ; Here b = F ( n + 1 ) ; As F ( 2 n ) = F ( n ) [ 2F ( n + 1 ) F ( n ) ] Here c = F ( 2 n ) ; As F ( 2 n + 1 ) = F ( n ) ^ 2 + F ( n + 1 ) ^ 2 Here d = F ( 2 n + 1 ) ; Check if N is odd or even ; Driver code
#include <bits/stdc++.h> NEW_LINE using namespace std ; int a , b , c , d ; #define MOD  1000000007 NEW_LINE void FastDoubling ( int n , int res [ ] ) { if ( n == 0 ) { res [ 0 ] = 0 ; res [ 1 ] = 1 ; return ; } FastDoubling ( ( n / 2 ) , res ) ; a = res [ 0 ] ; b = res [ 1 ] ; c = 2 * b - a ; if ( c < 0 ) c += MOD ; c = ( a * c ) % MOD ; d = ( a * a + b * b ) % MOD ; if ( n % 2 == 0 ) { res [ 0 ] = c ; res [ 1 ] = d ; } else { res [ 0 ] = d ; res [ 1 ] = c + d ; } } int main ( ) { int N = 6 ; int res [ 2 ] = { 0 } ; FastDoubling ( N , res ) ; cout << res [ 0 ] << " STRNEWLINE " ; return 0 ; }