Space efficient iterative method to Fibonacci number | get second MSB ; consectutively set all the bits ; returns the second MSB ; Multiply function ; Function to calculate F [ ] [ ] raise to the power n ; Base case ; take 2D array to store number 's ; run loop till MSB > 0 ; To return fibonacci number ; Given n
def getMSB ( n ) : NEW_LINE INDENT n |= n >> 1 NEW_LINE n |= n >> 2 NEW_LINE n |= n >> 4 NEW_LINE n |= n >> 8 NEW_LINE n |= n >> 16 NEW_LINE return ( ( n + 1 ) >> 2 ) NEW_LINE DEDENT def multiply ( F , M ) : NEW_LINE INDENT x = F [ 0 ] [ 0 ] * M [ 0 ] [ 0 ] + F [ 0 ] [ 1 ] * M [ 1 ] [ 0 ] NEW_LINE y = F [ 0 ] [ 0 ] * M [ 0 ] [ 1 ] + F [ 0 ] [ 1 ] * M [ 1 ] [ 1 ] NEW_LINE z = F [ 1 ] [ 0 ] * M [ 0 ] [ 0 ] + F [ 1 ] [ 1 ] * M [ 1 ] [ 0 ] NEW_LINE w = F [ 1 ] [ 0 ] * M [ 0 ] [ 1 ] + F [ 1 ] [ 1 ] * M [ 1 ] [ 1 ] NEW_LINE F [ 0 ] [ 0 ] = x NEW_LINE F [ 0 ] [ 1 ] = y NEW_LINE F [ 1 ] [ 0 ] = z NEW_LINE F [ 1 ] [ 1 ] = w NEW_LINE DEDENT def power ( F , n ) : NEW_LINE INDENT if ( n == 0 or n == 1 ) : NEW_LINE INDENT return NEW_LINE DEDENT M = [ [ 1 , 1 ] , [ 1 , 0 ] ] NEW_LINE m = getMSB ( n ) NEW_LINE while m : NEW_LINE INDENT multiply ( F , F ) NEW_LINE if ( n & m ) : NEW_LINE INDENT multiply ( F , M ) NEW_LINE DEDENT m = m >> 1 NEW_LINE DEDENT DEDENT def fib ( n ) : NEW_LINE INDENT F = [ [ 1 , 1 ] , [ 1 , 0 ] ] NEW_LINE if ( n == 0 ) : NEW_LINE INDENT return 0 NEW_LINE DEDENT power ( F , n - 1 ) NEW_LINE return F [ 0 ] [ 0 ] NEW_LINE DEDENT n = 6 NEW_LINE print ( fib ( n ) ) NEW_LINE