N-ésimo número de Fibonacci usando la ecuación de Pell

Dado un número entero N , la tarea es encontrar el N ^número de Fibonacci .
 

Entrada: N = 13 
Salida: 144
Entrada: N = 19 
Salida: 2584 
 

Enfoque: El N ^número de Fibonacci se puede encontrar usando las raíces de la ecuación de Pell . La ecuación de Pell es generalmente de la forma (x ² ) – n(y ² ) = |1| . 
Aquí, considere y ² = x, n = 1 . Además, tomado positivo (+1) en el lado derecho. 
Ahora la ecuación se convierte en x ² – x = 1 que es lo mismo que x ² – x – 1 = 0 . 
Aquí, {x = (p ⁱ – q ⁱ ) / (p – q)} se denomina N ^thtérmino de la serie de Fibonacci donde i = n – 1 y (p, q) son las raíces de la ecuación de Pell. 
 

Encontrar raíces de ecuaciones cuadráticas generales (a*x ² + b*x + c = 0). 
x1 = [-b + matemática.raíz cuadrada(b ² – 4*a*c)] / 2*a 
x2 = [-b – matemática.raíz cuadrada(b ² – 4*a*c)] / 2*a 
es decir  ,
p = (1 + matemática.raíz cuadrada(5)) / 2 
q = (1 – matemática.raíz cuadrada(5)) / 2 
 

A continuación se muestra la implementación del enfoque anterior: 
 

// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to return the
// nth fibonacci number
int 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 code
int main()
{
    int n = 5;
    cout << fib(n);
}
 
// This code is contributed by PrinciRaj1992

// Java implementation of the approach
class GFG
{
     
// Assign roots of the pell's
// equation to p and q
static double p = ((1 + Math.sqrt(5)) / 2);
static double q = ((1 - Math.sqrt(5)) / 2);
 
// Function to return the
// nth fibonacci number
static int fib(int n)
{
    int i = n - 1;
    int x = (int) ((Math.pow(p, i) -
                    Math.pow(q, i)) / (p - q));
    return x;
}
 
// Driver code
public static void main(String[] args)
{
    int n = 5;
    System.out.println(fib(n));
}
}
 
// This code is contributed by 29AjayKumar

# Python3 implementation of the approach
import math
 
# Assign roots of the pell's
# equation to p and q
p = (1 + math.sqrt(5)) / 2
q = (1 - math.sqrt(5)) / 2
 
# Function to return the
# nth fibonacci number
def fib(n):
    i = n - 1
    x = (p**i - q**i) / (p - q)
    return int(x)
 
# Driver code
n = 5
print(fib(n))

// C# implementation of the approach
using System;
 
class GFG
{
         
// Assign roots of the pell's
// equation to p and q
static double p = ((1 + Math.Sqrt(5)) / 2);
static double q = ((1 - Math.Sqrt(5)) / 2);
 
// Function to return the
// nth fibonacci number
static int fib(int n)
{
    int i = n - 1;
    int x = (int) ((Math.Pow(p, i) -
                    Math.Pow(q, i)) / (p - q));
    return x;
}
 
// Driver code
static public void Main ()
{
    int n = 5;
    Console.Write(fib(n));
}
}
 
// This code is contributed by @ajit..

<script>
 
// Javascript implementation of the approach
 
// Function to return the
// nth fibonacci number
function 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