Given a number n, find n-th Fibonacci Number. Note that F0 = 0, F1 = 1, F2 = 2, …..
Examples :
Input : n = 5 Output : 5 Input : n = 10 Output : 89
We have discussed below recursive solution in method 4 of Program for Fibonacci numbers.
F[2][2] = |1, 1|
|1, 0|
M[2][2] = |1, 1|
|1, 0|
F[n][n] = fib(n) | fib(n-1)
------------------
fib(n-1)| fib(n-2)
In this post an iterative method is discussed that avoids extra recursion call stack space. We have also used bitwise operators to further optimize. In the previous method, we divide the number with 2 so that at the end we get 1 and then we start the multiplication process
In this method we get the second MSB then start to multiply with FxF matrix then if bit is set then multiply again FxM matrix and so on. then we get the final result.
Approach :
1. First get the MSB of a number.
2. while (MSB > 0)
multiply(F, F);
if (n & MSB)
multiply(F, M);
and then shift MSB till MSB != 0
C++
// CPP code to find nth fibonacci #include <bits/stdc++.h> using namespace std; // get second MSB int getMSB(int n) { // consectutively set all the bits n |= n >> 1; n |= n >> 2; n |= n >> 4; n |= n >> 8; n |= n >> 16; // returns the second MSB return ((n + 1) >> 2); } // Multiply function void multiply(int F[2][2], int M[2][2]) { int x = F[0][0] * M[0][0] + F[0][1] * M[1][0]; int y = F[0][0] * M[0][1] + F[0][1] * M[1][1]; int z = F[1][0] * M[0][0] + F[1][1] * M[1][0]; int 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 to calculate F[][] // raise to the power n void power(int F[2][2], int n) { // Base case if (n == 0 || n == 1) return; // take 2D array to store number's int M[2][2] = { 1, 1, 1, 0 }; // run loop till MSB > 0 for (int m = getMSB(n); m; m = m >> 1) { multiply(F, F); if (n & m) { multiply(F, M); } } } // To return fibonacci numebr int fib(int n) { int F[2][2] = { { 1, 1 }, { 1, 0 } }; if (n == 0) return 0; power(F, n - 1); return F[0][0]; } // Driver Code int main() { // Given n int n = 6; cout << fib(n) << " "; return 0; } |
Java
// Java code to // find nth fibonacci class GFG { // get second MSB static int getMSB(int n) { // consectutively set // all the bits n |= n >> 1; n |= n >> 2; n |= n >> 4; n |= n >> 8; n |= n >> 16; // returns the // second MSB return ((n + 1) >> 2); } // Multiply function static void multiply(int F[][], int M[][]) { int x = F[0][0] * M[0][0] + F[0][1] * M[1][0]; int y = F[0][0] * M[0][1] + F[0][1] * M[1][1]; int z = F[1][0] * M[0][0] + F[1][1] * M[1][0]; int 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 to calculate F[][] // raise to the power n static void power(int F[][], int n) { // Base case if (n == 0 || n == 1) return; // take 2D array to // store number's int[][] M ={{1, 1}, {1, 0}}; // run loop till MSB > 0 for (int m = getMSB(n); m > 0; m = m >> 1) { multiply(F, F); if ((n & m) > 0) { multiply(F, M); } } } // To return // fibonacci numebr static int fib(int n) { int[][] F = {{1, 1}, {1, 0}}; if (n == 0) return 0; power(F, n - 1); return F[0][0]; } // Driver Code public static void main(String[] args) { // Given n int n = 6; System.out.println(fib(n)); } } // This code is contributed // by mits |
C#
// C# code to find nth fibonacci using System; class GFG { // get second MSB static int getMSB(int n) { // consectutively set // all the bits n |= n >> 1; n |= n >> 2; n |= n >> 4; n |= n >> 8; n |= n >> 16; // returns the // second MSB return ((n + 1) >> 2); } // Multiply function static void multiply(int [,]F, int [,]M) { int x = F[0,0] * M[0,0] + F[0,1] * M[1,0]; int y = F[0,0] * M[0,1] + F[0,1] * M[1,1]; int z = F[1,0] * M[0,0] + F[1,1] * M[1,0]; int 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 to calculate F[][] // raise to the power n static void power(int [,]F, int n) { // Base case if (n == 0 || n == 1) return; // take 2D array to // store number's int[,] M ={{1, 1}, {1, 0}}; // run loop till MSB > 0 for (int m = getMSB(n); m > 0; m = m >> 1) { multiply(F, F); if ((n & m) > 0) { multiply(F, M); } } } // To return // fibonacci numebr static int fib(int n) { int[,] F = {{1, 1}, {1, 0}}; if (n == 0) return 0; power(F, n - 1); return F[0,0]; } // Driver Code static public void Main () { // Given n int n = 6; Console.WriteLine(fib(n)); } } // This code is contributed ajit |
PHP
> 1;
$n |= $n >> 2;
$n |= $n >> 4;
$n |= $n >> 8;
$n |= $n >> 16;
// returns the second MSB
return (($n + 1) >> 2);
}
// Multiply function
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 to calculate F[][]
// raise to the power n
function power(&$F, $n)
{
// Base case
if ($n == 0 || $n == 1)
return;
// take 2D array to store number’s
$M = array(array(1, 1), array(1, 0));
// run loop till MSB > 0
for ($m = getMSB($n); $m; $m = $m >> 1)
{
multiply($F, $F);
if ($n & $m)
{
multiply($F, $M);
}
}
}
// To return fibonacci numebr
function fib($n)
{
$F = array(array( 1, 1 ),
array( 1, 0 ));
if ($n == 0)
return 0;
power($F, $n – 1);
return $F[0][0];
}
// Driver Code
// Given n
$n = 6;
echo fib($n) . ” “;
// This code is contributed by ita_c
?>
8
Time Complexity :- O(logn) and space complexity :- O(1).
This article is attributed to GeeksforGeeks.org
leave a comment
0 Comments