Fast Doubling method to find the Nth Fibonacci number | Java 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
class GFG { static void FastDoubling ( int n , int [ ] res ) { int a , b , c , d ; int MOD = 1000000007 ; 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 ; } } public static void main ( String [ ] args ) { int N = 6 ; int res [ ] = new int [ 2 ] ; FastDoubling ( N , res ) ; System . out . print ( res [ 0 ] ) ; } }