Fast Doubling method to find the Nth Fibonacci number | Javascript 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
let a , b , c , d ; let MOD = 1000000007 ; function FastDoubling ( n , res ) { if ( n == 0 ) { res [ 0 ] = 0 ; res [ 1 ] = 1 ; return ; } FastDoubling ( parseInt ( n / 2 , 10 ) , 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 ; } } let N = 6 ; let res = new Array ( 2 ) ; res . fill ( 0 ) ; FastDoubling ( N , res ) ; document . write ( res [ 0 ] ) ;