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
function getMSB ( n ) { n |= n >> 1 ; n |= n >> 2 ; n |= n >> 4 ; n |= n >> 8 ; n |= n >> 16 ; return ( ( n + 1 ) >> 2 ) ; } function multiply ( F , M ) { let x = F [ 0 ] [ 0 ] * M [ 0 ] [ 0 ] + F [ 0 ] [ 1 ] * M [ 1 ] [ 0 ] ; let y = F [ 0 ] [ 0 ] * M [ 0 ] [ 1 ] + F [ 0 ] [ 1 ] * M [ 1 ] [ 1 ] ; let z = F [ 1 ] [ 0 ] * M [ 0 ] [ 0 ] + F [ 1 ] [ 1 ] * M [ 1 ] [ 0 ] ; let w = F [ 1 ] [ 0 ] * M [ 0 ] [ 1 ] + F [ 1 ] [ 1 ] * M [ 1 ] [ 1 ] ; F [ 0 ] [ 0 ] = x ; F [ 0 ] [ 1 ] = y ; F [ 1 ] [ 0 ] = z ; F [ 1 ] [ 1 ] = w ; } function power ( F , n ) { if ( n == 0 n == 1 ) return ; let M = [ [ 1 , 1 ] , [ 1 , 0 ] ] ; for ( let m = getMSB ( n ) ; m > 0 ; m = m >> 1 ) { multiply ( F , F ) ; if ( ( n & m ) > 0 ) { multiply ( F , M ) ; } } } function fib ( n ) { let F = [ [ 1 , 1 ] , [ 1 , 0 ] ] ; if ( n == 0 ) return 0 ; power ( F , n - 1 ) ; return F [ 0 ] [ 0 ] ; } let n = 6 ; document . write ( fib ( n ) ) ;