Given an integer N, the task is to find the Nth Fibonacci number.
Examples:
Input: N = 13
Output: 144Input: N = 19
Output: 2584
Approach: The Nth Fibonacci number can be found using the roots of the pell’s equation. Pells equation is generally of the form (x2) – n(y2) = |1|.
Here, consider y2 = x, n = 1. Also, taken positive (+1) in the right-hand side.
Now the equation becomes x2 – x = 1 which is same as x2 – x – 1 = 0.
Here, {x = (pi – qi) / (p – q)} is termed as Nth term of the fibonacci series where i = n – 1 and (p, q) are the roots of the pell’s equation.
To find roots of general quadratic equation (a*x2 + b*x + c = 0).
x1 = [-b + math.sqrt(b2 – 4*a*c)] / 2*a
x2 = [-b – math.sqrt(b2 – 4*a*c)] / 2*a
i.e.
p = (1 + math.sqrt(5)) / 2
q = (1 – math.sqrt(5)) / 2
Below is the implementation of the above approach:
C++
// C++ implementation of the approach#include <bits/stdc++.h>using namespace std;// Function to return the // nth fibonacci numberint fib(int n){ // Assign roots of the pell's // equation to p and q double p = ((1 + sqrt(5)) / 2); double q = ((1 - sqrt(5)) / 2); int i = n - 1; int x = (int) ((pow(p, i) - pow(q, i)) / (p - q)); return x;}// Driver codeint main(){ int n = 5; cout << fib(n);}// This code is contributed by PrinciRaj1992 |
Java
// Java implementation of the approachclass GFG { // Assign roots of the pell's // equation to p and qstatic double p = ((1 + Math.sqrt(5)) / 2);static double q = ((1 - Math.sqrt(5)) / 2);// Function to return the // nth fibonacci numberstatic int fib(int n){ int i = n - 1; int x = (int) ((Math.pow(p, i) - Math.pow(q, i)) / (p - q)); return x;}// Driver codepublic static void main(String[] args) { int n = 5; System.out.println(fib(n));}} // This code is contributed by 29AjayKumar |
Python3
# Python3 implementation of the approachimport math# Assign roots of the pell's # equation to p and qp = (1 + math.sqrt(5)) / 2q = (1 - math.sqrt(5)) / 2# Function to return the # nth fibonacci numberdef fib(n): i = n - 1 x = (p**i - q**i) / (p - q) return int(x)# Driver coden = 5print(fib(n)) |
C#
// C# implementation of the approachusing System;class GFG{ // Assign roots of the pell's // equation to p and qstatic double p = ((1 + Math.Sqrt(5)) / 2);static double q = ((1 - Math.Sqrt(5)) / 2);// Function to return the // nth fibonacci numberstatic int fib(int n){ int i = n - 1; int x = (int) ((Math.Pow(p, i) - Math.Pow(q, i)) / (p - q)); return x;}// Driver codestatic public void Main (){ int n = 5; Console.Write(fib(n));}} // This code is contributed by @ajit.. |
Javascript
<script>// Javascript implementation of the approach// Function to return the // nth fibonacci numberfunction fib(n){ // Assign roots of the pell's // equation to p and q let p = ((1 + Math.sqrt(5)) / 2); let q = ((1 - Math.sqrt(5)) / 2); let i = n - 1; let x = parseInt((Math.pow(p, i) - Math.pow(q, i)) / (p - q)); return x;}// Driver code let n = 5; document.write(fib(n));</script> |
3
Time complexity: O(logn)
Auxiliary Space: O(1)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
