Given a number n, print n-th Fibonacci Number, using Binet’s Formula.
Examples:
Input: n = 5
Output: 1
Input: n = 9
Output: 34
What is Binet’s Formula?
Binet’s Formula states that:
If
is the
Fibonacci number, then
is the 
Why is Binet’s Formula not used regularly?
Binet’s Formula gives correct results only up to n<71.
Because as we move forward from n>=71, the rounding error becomes significantly large. Although, using the floor function instead of the round function will give the correct result for n=71. But after n=72, it also fails.
Example: For N=72 , Correct result is 498454011879264 but above formula gives 498454011879265.
Approach to Find Nth Fibonacci Number using Binet’s Formula
In this method, we directly implement the formula for the nth term in the Fibonacci series. Fn = {[(√5 + 1)/2] ^ n} / √5
Below is the implementation of the above approach:
C++
// C++ Program to find n'th fibonacci Number #include <cmath> #include <iostream> int fib(int n) { double phi = (1 + sqrt(5)) / 2; return round(pow(phi, n) / sqrt(5)); } // Driver Code int main() { int n = 9; std::cout << fib(n) << std::endl; return 0; } // This code is contributed by Lokesh Mohanty. |
Java
// Java Program to find n'th fibonacci Number import java.util.*; public class GFG { static int fib(int n) { double phi = (1 + Math.sqrt(5)) / 2; return (int)Math.round(Math.pow(phi, n) / Math.sqrt(5)); } // Driver Code public static void main(String[] args) { int n = 9; System.out.println(fib(n)); } }; // This code is contributed by PrinciRaj1992 |
Python3
# Python3 program to find n'th # fibonacci Number import math def fibo(n): phi = (1 + math.sqrt(5)) / 2 return round(pow(phi, n) / math.sqrt(5)) # Driver code if __name__ == '__main__': n = 9 print(fibo(n)) # This code is contributed by prasun_parate |
C#
// C# Program to find n'th fibonacci Number using System; public class GFG { static int fib(int n) { double phi = (1 + Math.Sqrt(5)) / 2; return (int)Math.Round(Math.Pow(phi, n) / Math.Sqrt(5)); } // Driver code public static void Main() { int n = 9; Console.WriteLine(fib(n)); } } // This code is contributed by 29AjayKumar |
Javascript
// Javascript Program to find n'th fibonacci Number function fib(n) { let phi = (1 + Math.sqrt(5)) / 2; return Math.round(Math.pow(phi, n) / Math.sqrt(5)); } let n = 9; console.log(fib(n)); // This code is contributed by mukesh07. |
PHP
<?php // PHP Program to find n'th // fibonacci Number function fib($n) { $phi = (1 + sqrt(5)) / 2; return round(pow($phi, $n) / sqrt(5)); } // Driver Code $n = 9; echo fib($n) ; // This code is contributed by Ryuga ?> |
34
Time Complexity: O(log n), this is because calculating phi^n takes log n time
Auxiliary Space: O(1)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
