Método de duplicación rápida para encontrar el enésimo número de Fibonacci

Dado un número entero N , la tarea es encontrar los N-ésimos números de Fibonacci .
Ejemplos:

Entrada: N = 3
Salida: 2
Explicación:
F(1) = 1, F(2) = 1
F(3) = F(1) + F(2) = 2
Entrada: N = 6
Salida: 8

Acercarse:

El método de exponenciación de arrays ya se discutió anteriormente. El método de duplicación puede verse como una mejora del método de exponenciación de arrays para encontrar el N-ésimo número de Fibonacci, aunque no utiliza la multiplicación de arrays en sí.
La secuencia recursiva de Fibonacci está dada por

F(n+1) = F(n) + F(n-1)

El método de exponenciación matricial utiliza la siguiente fórmula
$\begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix}^n = \begin{bmatrix} F_{n+1} & F_n \\ F_n & F_{n-1} \end{bmatrix}$
El método implica una costosa multiplicación de arrays y, además, F _n se calcula dos veces de forma redundante.
Por otro lado, el método de duplicación rápida se basa en dos fórmulas básicas:

F(2n) = F(n)[2F(n+1) – F(n)]
F(2n + 1) = F(n)^{2 + F(n+1)2}

Aquí hay una breve explicación de los resultados anteriores:

Comience con:
F(n+1) = F(n) + F(n-1) &
F(n) = F(n)
Se puede reescribir en forma matricial como:

$\begin{bmatrix} F(n+1) \\ F(n) \end{bmatrix} = \begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix} \begin{bmatrix} F(n) \\ F(n-1) \end{bmatrix} \] \[\quad\enspace= \begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix}^2 \begin{bmatrix} F(n-1) \\ F(n-2) \end{bmatrix} \] \quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\enspace\enspace\thinspace......\\ \[= \begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix}^n \begin{bmatrix} F(1) \\ F(0) \end{bmatrix}$

Para duplicar, simplemente ingresamos «2n» en la fórmula:

$\begin{bmatrix} F(2n+1) \\ F(2n) \end{bmatrix} = \begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix}^{2n} \begin{bmatrix} F(1) \\ F(0) \end{bmatrix} \] \[\quad\enspace= \begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix}^n \begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix}^n \begin{bmatrix} F(1) \\ F(0) \end{bmatrix} \] \[\quad\enspace= \begin{bmatrix} F(n+1) & F(n) \\ F(n) & F(n-1) \end{bmatrix} \begin{bmatrix} F(n+1) & F(n) \\ F(n) & F(n-1) \end{bmatrix} \begin{bmatrix} F(1) \\ F(0) \end{bmatrix} \] \[\quad\enspace= \begin{bmatrix} F(n+1)^2 + F(n)^2 \\ F(n)F(n+1) + F(n)F(n-1) \end{bmatrix}$

Sustituyendo F(n-1) = F(n+1)- F(n) y después de la simplificación obtenemos,

$\begin{bmatrix} F(2n+1) \\ F(2n) \end{bmatrix} = \begin{bmatrix} F(n+1)^2 + F(n)^2 \\ 2F(n+1)F(n) - F(n)^2 \end{bmatrix}$

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

C++

// C++ program to find the Nth Fibonacci
// number using Fast Doubling Method
#include <bits/stdc++.h>
using namespace std;
 
int a, b, c, d;
#define MOD 1000000007
 
// Function calculate the N-th fibonacci
// number using fast doubling method
void FastDoubling(int n, int res[])
{
    // Base Condition
    if (n == 0) {
        res[0] = 0;
        res[1] = 1;
        return;
    }
    FastDoubling((n / 2), res);
 
    // Here a = F(n)
    a = res[0];
 
    // Here b = F(n+1)
    b = res[1];
 
    c = 2 * b - a;
 
    if (c < 0)
        c += MOD;
 
    // As F(2n) = F(n)[2F(n+1) – F(n)]
    // Here c  = F(2n)
    c = (a * c) % MOD;
 
    // As F(2n + 1) = F(n)^2 + F(n+1)^2
    // Here d = F(2n + 1)
    d = (a * a + b * b) % MOD;
 
    // Check if N is odd
    // or even
    if (n % 2 == 0) {
        res[0] = c;
        res[1] = d;
    }
    else {
        res[0] = d;
        res[1] = c + d;
    }
}
 
// Driver code
int main()
{
    int N = 6;
    int res[2] = { 0 };
 
    FastDoubling(N, res);
 
    cout << res[0] << "\n";
    return 0;
}

Java

// Java program to find the Nth Fibonacci
// number using Fast Doubling Method
class GFG{
 
// Function calculate the N-th fibonacci
// number using fast doubling method
static void FastDoubling(int n, int []res)
{
    int a, b, c, d;
    int MOD = 1000000007;
     
    // Base Condition
    if (n == 0)
    {
        res[0] = 0;
        res[1] = 1;
        return;
    }
    FastDoubling((n / 2), res);
 
    // Here a = F(n)
    a = res[0];
 
    // Here b = F(n+1)
    b = res[1];
 
    c = 2 * b - a;
 
    if (c < 0)
        c += MOD;
 
    // As F(2n) = F(n)[2F(n+1) – F(n)]
    // Here c = F(2n)
    c = (a * c) % MOD;
 
    // As F(2n + 1) = F(n)^2 + F(n+1)^2
    // Here d = F(2n + 1)
    d = (a * a + b * b) % MOD;
 
    // Check if N is odd
    // or even
    if (n % 2 == 0)
    {
        res[0] = c;
        res[1] = d;
    }
    else
    {
        res[0] = d;
        res[1] = c + d;
    }
}
 
// Driver code
public static void main(String []args)
{
    int N = 6;
    int res[] = new int[2];
 
    FastDoubling(N, res);
 
    System.out.print(res[0]);
}
}
 
// This code is contributed by rock_cool

Python3

# Python3 program to find the Nth Fibonacci
# number using Fast Doubling Method
MOD = 1000000007
 
# Function calculate the N-th fibonacci
# number using fast doubling method
def FastDoubling(n, res):
     
    # Base Condition
    if (n == 0):
        res[0] = 0
        res[1] = 1
        return
         
    FastDoubling((n // 2), res)
 
    # Here a = F(n)
    a = res[0]
 
    # Here b = F(n+1)
    b = res[1]
 
    c = 2 * b - a
 
    if (c < 0):
        c += MOD
 
    # As F(2n) = F(n)[2F(n+1) – F(n)]
    # Here c = F(2n)
    c = (a * c) % MOD
 
    # As F(2n + 1) = F(n)^2 + F(n+1)^2
    # Here d = F(2n + 1)
    d = (a * a + b * b) % MOD
 
    # Check if N is odd
    # or even
    if (n % 2 == 0):
        res[0] = c
        res[1] = d
    else :
        res[0] = d
        res[1] = c + d
     
# Driver code
N = 6
res = [0] * 2
 
FastDoubling(N, res)
 
print(res[0])
     
# This code is contributed by divyamohan123

C#

// C# program to find the Nth Fibonacci
// number using Fast Doubling Method
using System;
class GFG{
 
// Function calculate the N-th fibonacci
// number using fast doubling method
static void FastDoubling(int n, int []res)
{
    int a, b, c, d;
    int MOD = 1000000007;
     
    // Base Condition
    if (n == 0)
    {
        res[0] = 0;
        res[1] = 1;
        return;
    }
    FastDoubling((n / 2), res);
 
    // Here a = F(n)
    a = res[0];
 
    // Here b = F(n+1)
    b = res[1];
 
    c = 2 * b - a;
 
    if (c < 0)
        c += MOD;
 
    // As F(2n) = F(n)[2F(n+1) – F(n)]
    // Here c = F(2n)
    c = (a * c) % MOD;
 
    // As F(2n + 1) = F(n)^2 + F(n+1)^2
    // Here d = F(2n + 1)
    d = (a * a + b * b) % MOD;
 
    // Check if N is odd
    // or even
    if (n % 2 == 0)
    {
        res[0] = c;
        res[1] = d;
    }
    else
    {
        res[0] = d;
        res[1] = c + d;
    }
}
 
// Driver code
public static void Main()
{
    int N = 6;
    int []res = new int[2];
 
    FastDoubling(N, res);
 
    Console.Write(res[0]);
}
}
 
// This code is contributed by Code_Mech

Javascript

<script>
 
    // Javascript program to find the Nth Fibonacci
      // number using Fast Doubling Method
     
    let a, b, c, d;
    let MOD = 1000000007;
 
    // Function calculate the N-th fibonacci
    // number using fast doubling method
    function FastDoubling(n, res)
    {
        // Base Condition
        if (n == 0) {
            res[0] = 0;
            res[1] = 1;
            return;
        }
        FastDoubling(parseInt(n / 2, 10), res);
 
        // Here a = F(n)
        a = res[0];
 
        // Here b = F(n+1)
        b = res[1];
 
        c = 2 * b - a;
 
        if (c < 0)
            c += MOD;
 
        // As F(2n) = F(n)[2F(n+1) – F(n)]
        // Here c  = F(2n)
        c = (a * c) % MOD;
 
        // As F(2n + 1) = F(n)^2 + F(n+1)^2
        // Here d = F(2n + 1)
        d = (a * a + b * b) % MOD;
 
        // Check if N is odd
        // or even
        if (n % 2 == 0) {
            res[0] = c;
            res[1] = d;
        }
        else {
            res[0] = d;
            res[1] = c + d;
        }
    }
 
    let N = 6;
    let res = new Array(2);
    res.fill(0);
   
    FastDoubling(N, res);
   
    document.write(res[0]);
     
</script>

Producción

Complejidad del tiempo: El cuadrado repetido reduce el tiempo de lineal a logarítmico. Por lo tanto, con aritmética de tiempo constante, la complejidad de tiempo es O(log n) .
Espacio Auxiliar: O(n).

Versión iterativa

Podemos implementar una versión iterativa del método anterior, inicializando la array con dos elementos f = [F(0), F(1)] = [0, 1] y construyendo iterativamente F(n), en cada paso transformaremos f en [F(2i), F(2i+1)] o [F(2i+1), F(2i+2)] , donde i corresponde al valor actual de i almacenado en f = [F(i), F (i+1)].

Acercarse:

Cree una array con dos elementos f = [0, 1] , que representa [F(0), F(1)] .
Para encontrar F(n), itere sobre la representación binaria de n de izquierda a derecha, sea k ^-ésimo bit de izquierda a b _k .
Aplique iterativamente los siguientes pasos para todos los bits en n .
Usando b _k decidiremos si transformar f = [F(i), F(i+1)] en [F(2i), F(2i+1)] o [F(2i+1), F(2i +2)] .

if b_{k == 0:}
 f = [F(2i), F(2i+1)] = [F(i){2F(i+1)-F(i)}, F(i+1)^2+F(i)2]
if b_{k == 1:}
 f = [F(2i+1), F(2i+2)] = [F(i+1)^{2+F(i)2, F(i+1){2F(i)+F(i+1)}]}

where,
F(i) and F(i+1) are current values stored in f.

devuelve f[0] .

Example:
for n = 13 = (1101)₂
b =          1               1               0               1
[F(0), F(1)] -> [F(1), F(2)] -> [F(3), F(4)] -> [F(6), F(7)] -> [F(13), F(14)]
[0, 1]       -> [1, 1]       -> [2, 3]       -> [8, 13]      -> [233, 377]

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

C++

// C++ program to find the Nth Fibonacci
// number using Fast Doubling Method iteratively
 
#include <bitset>
#include <iostream>
#include <string>
 
using namespace std;
 
// helper function to get binary string
string decimal_to_bin(int n)
{
    // use bitset to get binary string
    string bin = bitset<sizeof(int) * 8>(n).to_string();
    auto loc = bin.find('1');
    // remove leading zeros
    if (loc != string::npos)
        return bin.substr(loc);
    return "0";
}
 
// computes fib(n) iteratively using fast doubling method
long long fastfib(int n)
{
    string bin_of_n
        = decimal_to_bin(n); // binary string of n
 
    long long f[] = { 0, 1 }; // [F(i), F(i+1)] => i=0
 
    for (auto b : bin_of_n) {
        long long f2i1
            = f[1] * f[1] + f[0] * f[0]; // F(2i+1)
        long long f2i = f[0] * (2 * f[1] - f[0]); // F(2i)
 
        if (b == '0') {
            f[0] = f2i; // F(2i)
            f[1] = f2i1; // F(2i+1)
        }
        else {
            f[0] = f2i1; // F(2i+1)
            f[1] = f2i1 + f2i; // F(2i+2)
        }
    }
 
    return f[0];
}
 
int main()
{
    int n = 13;
    long long fib = fastfib(n);
    cout << "F(" << n << ") = " << fib << "\n";
}

Python3

# Python3 program to find the Nth Fibonacci
# number using Fast Doubling Method iteratively
 
 
def fastfib(n):
    """computes fib(n) iteratively using fast doubling method"""
    bin_of_n = bin(n)[2:]  # binary string of n
    f = [0, 1]  # [F(i), F(i+1)] => i=0
 
    for b in bin_of_n:
        f2i1 = f[1]**2 + f[0]**2  # F(2i+1)
        f2i = f[0]*(2*f[1]-f[0])  # F(2i)
 
        if b == '0':
            f[0], f[1] = f2i, f2i1  # [F(2i), F(2i+1)]
        else:
            f[0], f[1] = f2i1, f2i1+f2i  # [F(2i+1), F(2i+2)]
 
    return f[0]
 
 
n = 13
fib = fastfib(n)
print(f'F({n}) =', fib)

Javascript

// JavaScript program to find the Nth Fibonacci
// number using Fast Doubling Method iteratively
 
// Helper function to convert decimal to binary.
function convertToBinary(x) {
    let bin = 0;
    let rem, i = 1, step = 1;
    while (x != 0) {
        rem = x % 2;
        x = parseInt(x / 2);
        bin = bin + rem * i;
        i = i * 10;
    }
    // let myArr = Array.from(String(bin).split(""));
    return bin.toString();
}
 
// helper function to get binary string
function decimal_to_bin(n)
{
    // use bitset to get binary string
    let bin = convertToBinary(n);
    let loc = bin.indexOf('1');
    // remove leading zeros
    if (loc != -1)
        return bin.substring(loc);
    return "0";
}
 
// computes fib(n) iteratively using fast doubling method
function fastfib(n)
{
    let bin_of_n = decimal_to_bin(n); // binary string of n
 
    let f = [0, 1]; // [F(i), F(i+1)] => i=0
 
    for(let i = 0; i < bin_of_n.length; i++){
        let b = bin_of_n[i];
        let f2i1 = f[1] * f[1] + f[0] * f[0]; // F(2i+1)
        let f2i = f[0] * (2 * f[1] - f[0]); // F(2i)
 
        if (b == '0') {
            f[0] = f2i; // F(2i)
            f[1] = f2i1; // F(2i+1)
        }
        else {
            f[0] = f2i1; // F(2i+1)
            f[1] = f2i1 + f2i; // F(2i+2)
        }
    }
 
    return f[0];
}
 
let n = 13;
let fib = fastfib(n);
console.log("F(",n,") =", fib);
 
// The code is contributed by Gautam goel (gautamgoel962)

Producción

F(13) = 233

Complejidad de tiempo : estamos iterando sobre la string binaria del número n que tiene una longitud de log(n) y haciendo operaciones aritméticas de tiempo constante, por lo que la complejidad de tiempo es O(log n) .

Espacio auxiliar : estamos almacenando dos elementos en f y la string binaria de n tiene una longitud log(n), por lo que la complejidad del espacio es O(log n) .

Publicación traducida automáticamente

Artículo escrito por unagi y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

C++

Java

Python3

C#

Javascript

C++

Python3

Javascript

Deja una respuesta Cancelar la respuesta