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
< ? php 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 ) { $ x = $ F [ 0 ] [ 0 ] * $ M [ 0 ] [ 0 ] + $ F [ 0 ] [ 1 ] * $ M [ 1 ] [ 0 ] ; $ y = $ F [ 0 ] [ 0 ] * $ M [ 0 ] [ 1 ] + $ F [ 0 ] [ 1 ] * $ M [ 1 ] [ 1 ] ; $ z = $ F [ 1 ] [ 0 ] * $ M [ 0 ] [ 0 ] + $ F [ 1 ] [ 1 ] * $ M [ 1 ] [ 0 ] ; $ 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 ; $ M = array ( array ( 1 , 1 ) , array ( 1 , 0 ) ) ; for ( $ m = getMSB ( $ n ) ; $ m ; $ m = $ m >> 1 ) { multiply ( $ F , $ F ) ; if ( $ n & $ m ) { multiply ( $ F , $ M ) ; } } } function fib ( $ n ) { $ F = array ( array ( 1 , 1 ) , array ( 1 , 0 ) ) ; if ( $ n == 0 ) return 0 ; power ( $ F , $ n - 1 ) ; return $ F [ 0 ] [ 0 ] ; } $ n = 6 ; echo fib ( $ n ) . " " ; ? >