Berechnen der n-ten Fibonacci-Zahl modulo m unter Verwendung des Goldenen Schnitts in C

Question

Ich versuche die n-te Fibonacci-Zahl modulo 10^9 + 7 zu berechnen, wobei n vom Benutzer eingegeben wird.

Ich habe das goldene Verhältnis verwendet, um Fibonacci-Zahlen zu berechnen.

Der folgende Code liefert korrekte Ergebnisse bis n = 43. Aber für n> = 44 geht phi über 10^9 + 7 und ich bekomme unerwartete Ergebnisse. Auch ergibt n> = 44 ein korrektes Ergebnis, wenn der Modul entfernt wird.

#include <stdio.h> 
#include <math.h> 
long double mod=1000000007; 

long double power(long double base, long long int expo) 
{ 
    if(base==1 || expo==0) 
     return 1; 
    if(expo&1) 
    { 
     long double temp = power(base, expo>>1); 
     return fmodl(base * fmodl(temp*temp, mod), mod); 
    } 
    else 
    { 
     long double temp=power(base, expo>>1); 
     return fmodl(temp*temp,mod); 
    } 
} 


int main(void) { 
    // your code goes here 
    long double phi = (1+powl(5, 0.5))/2; 
    long double phi_cap = (1 - powl(5, 0.5))/2; 
    long double root5 = powl(5, 0.5); 
    long long int n; 
    scanf("%lld",&n); 
    long double ans = fmodl( (power(phi, n) - power(phi_cap, n)) * power(root5,mod-2), mod); 
    printf("%.0Lf\n", ans); 
    return 0; 
} 

Warum passiert das? Ist es falsch, lange Doppel zu verwenden, um irrationale Zahlen zu speichern?

Dank

Answer 1

Die closed form expression for the n'th Fibonacci number ist

F _n   =   φ ⁿ/√5   -   ψ ⁿ/√5

wo

φ = 1/2 + √5/2 ≅ 1,6180339887
ψ = 1/2 - √5/2 = φ - 1 ≅ 0,6180339887

Da das subtrahierte Teil in F n ist immer weniger als die Hälfte, wir F_n via rounding gegen Null berechnen können (oder in Richtung negativ unendlich oder floor(), da F n für n ≥ 0 ist nicht negative):

F _n = ⌊ φ ⁿ/√5 ⌋ = floor (φ ⁿ/√5)

Wenn wir in F interessiert sind _n Modulo M, M ≥ 2, müssen wir beobachten Die modulo operation beeinflusst die obige Formel. Man beachte, dass der Ausdruck "expr MOD M" typischerweise unter Verwendung von fmod(expr, M) in C berechnet wird

Wir die property of modular multiplication anwenden können: für positive reelle Zahlen a, b und m, ( a mod m) (b mod m) = (a bmod m). Die Bodenoperation ist nicht betroffen. Hier a = ⁿ und b = 1/√5.Dies bedeutet, dass wir den Ausdruck

F _n MOD M/√5 ⌋ MOD M

in

F _n MOD M vereinfachen = ⌊ φ n ^{= ⌊ (φ n MOD (M5))/√5 ⌋}

Hier können wir modular exponentiation anwenden, wobei darauf hingewiesen wird, dass der Modul an diesem Punkt nicht durch die ganze Zahl M, sondern durch M · √5 ist.

Mit anderen Worten, wenn wir eine Funktion, die tut eine ganzzahlige Potenz von einem Gleitkommawert mit modularer Potenzierung mit Gleitkommazahlen Modul haben, sagen

double pow_mod(double base, unsigned int exponent, double modulus); 

wir die n-te Fibonacci-Zahl berechnen können, F _n Modulo m

#define PHI 1.61803398874989484820458683436563811772 
#define SQRT5 2.236067977499789696409173668731276235441; 

double fn_mod_m; 
unsigned int n, m; 

fn_mod_m = floor(pow_mod(PHI, n, SQRT5 * (double)m)/SQRT5); 

die right-to-left method ist ein ausgezeichneter Kandidat für die modulare Exponentiation mit hier.