Fast Doubling method to find the Nth Fibonacci number | Python3 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
MOD = 1000000007 NEW_LINE def FastDoubling ( n , res ) : NEW_LINE INDENT if ( n == 0 ) : NEW_LINE INDENT res [ 0 ] = 0 NEW_LINE res [ 1 ] = 1 NEW_LINE return NEW_LINE DEDENT FastDoubling ( ( n // 2 ) , res ) NEW_LINE a = res [ 0 ] NEW_LINE b = res [ 1 ] NEW_LINE c = 2 * b - a NEW_LINE if ( c < 0 ) : NEW_LINE INDENT c += MOD NEW_LINE DEDENT c = ( a * c ) % MOD NEW_LINE d = ( a * a + b * b ) % MOD NEW_LINE if ( n % 2 == 0 ) : NEW_LINE INDENT res [ 0 ] = c NEW_LINE res [ 1 ] = d NEW_LINE DEDENT else : NEW_LINE INDENT res [ 0 ] = d NEW_LINE res [ 1 ] = c + d NEW_LINE DEDENT DEDENT N = 6 NEW_LINE res = [ 0 ] * 2 NEW_LINE FastDoubling ( N , res ) NEW_LINE print ( res [ 0 ] ) NEW_LINE