Golden Ratio Um Fibonacci-Zahl

Question

ich die Xth Fibonacci-Zahl d.h F(X)%1000000007
Für Beispiel finden, wenn ich d X(350) = 672262724 fin haben. Hier ist ein Code

Jetzt bin ich daran interessiert, mit Golden Ratio A=1.61 B=-0.61

X(350) = (A^350-B^350+1)/Math.sqrt(5) 

aber wie kümmern Modulo, wie es mir falsche Antwort ist zu geben, wenn ich einfach % Betrieb verwenden

Hier ist mein Code:

public static double super_pow(double A , long B){ 

     double o=1; 

     while(B>0){ 

      if((B&1)!=0) o*=A; 

      A*=A; 
      B/=2; 
      o%=mod; 
      A%=mod; 
     } 



     return (o+1)%mod; 
} 

I funktioniert gut, wenn die Antwort less thanMod. Aber für große Werte gibt es falsche Antworten.

Answer 1

Es funktioniert nicht so. Man kann nicht so tun, als würde man in einem endlichen Feld arbeiten und dann durch eine irrationale Zahl dividieren, oder vielmehr kann man das, aber es ergibt keinen Sinn. Sie erhalten als Ergebnis irrelevant irrelevant, das keine Beziehung zu der gewünschten Antwort hat. Du müsstest das ganze Ding in R machen, wenn du so gehst. Das erfordert, extrem große Zahlen zu berechnen und dann einen Rest zu nehmen. Fließkommazahlen werden irgendwann nicht mehr genau genug sein und Ihnen Unsinn bereiten. Das Bit mit dem Gewicht 1 ist immer wichtig, wenn Sie einen solchen Rest machen wollen, aber es ist nicht notwendigerweise in einer Gleitkommazahl vorhanden, abhängig vom Exponenten. Aber vielleicht wussten Sie das, und deshalb haben Sie sich entschieden, es nicht zu tun.

Sie können dies in diesem Fall auch nicht mit der endlichen Feldmathematik tun. Iff 5 ist ein quadratischer Rest in dem Feld, in dem Sie arbeiten, diese Konstruktion funktioniert immer noch. A und B sind nicht phi und phibar, sondern (sqrt (5) +1)/2 bzw. (1-sqrt (5))/2, was bei der endlichen Feldmathematik zu "komischen Zahlen" führt, die aussehen völlig unabhängig von phi und phibar (sind aber tatsächlich das endliche Feld von ihnen). Und natürlich, wenn Sie dies tun, wird es keine Math.sqrt irgendwo in Ihrem Code geben. Sie brauchen die Nummer x, so dass x * x = 5Modulo etwas, nicht eine dyadische rationale Annäherung der Lösung zwischen den Reals.

Die Quadratwurzel von 5 muss existieren, damit eines davon funktioniert, aber Modulo 1000000007, 5 hat keine Quadratwurzel.

Folgende Werke Modulo 1009: 856 * (627 ⁿ-383 ⁿ)

Andere Algorithmen noch funktionieren, wie eine bestimmte 2x2-Matrix auf die n-te Potenz erhöhen, und seine leicht optimierte Version (redundante Berechnung vermeiden).