nte Fibonacci-Zahl in der sublinearen Zeit

Den nTEN Fibonacci-Zahl ist gegeben durch

f(n) = Floor(phi^n /sqrt(5) + 1/2) 

wo

phi = (1 + sqrt(5)) /2

Unter der Annahme, dass der primitive mathematische Operationen (+-* und /) O(1) können Sie dieses Ergebnis, um zu berechnen nTEN Fibonacci-Zahl in O(log n) Zeit (O(log n) wegen der Potenzierung in der Formel).

In C#:

static double inverseSqrt5 = 1 /Math.Sqrt(5);
static double phi = (1 + Math.Sqrt(5)) /2;
/* should use 
   const double inverseSqrt5 = 0.44721359549995793928183473374626
   const double phi = 1.6180339887498948482045868343656
*/

static int Fibonacci(int n) {
    return (int)Math.Floor(Math.Pow(phi, n) * inverseSqrt5 + 0.5);
}

InformationsquelleAutor der Antwort jason

Wenn Sie möchten, dass die genaue Anzahl (was ist ein "bignum", sondern als ein int/float), dann fürchte ich, dass

Es ist unmöglich!

Wie gesagt die Formel für die Fibonacci-zahlen lautet:

fib n = floor (phiⁿ/√5 + ¹/₂)

fib n ~= phiⁿ/√5

Wie viele Ziffern ist fib n?

numDigits (fib n) = log (fib n) = log (phiⁿ/√5) = log phiⁿ - log √5 = n * log phi - log √5

numDigits (fib n) = n * const + const

es O(n)

Da die angeforderten Ergebnis ist der O(n), es kann nicht berechnet werden, in weniger als O(n) Zeit.

Wenn Sie nur wollen, die niedrigere Ziffern für die Antwort, dann ist es möglich zu berechnen, in sub-linearen Zeit mit der matrix-Potenzierung-Methode.

InformationsquelleAutor der Antwort yairchu

Können Sie es exponentiating eine matrix von Integer-zahlen, wie gut. Wenn Sie die matrix

    /1  1 \
M = |      |
    \ 1  0 /

dann (M^n)[1, 2] wird gleich der nTEN Fibonacci-Zahl, wenn [] ist eine matrix hoch-und ^ ist matrix-Potenzierung. Für eine Feste Größe-matrix, Potenzierung, um eine positive ganzzahlige Potenz kann durchgeführt werden in O(log n) Zeit in der gleichen Weise wie mit reellen zahlen.

EDIT: natürlich abhängig von der Art der Antwort, die Sie wollen, können Sie in der Lage sein, um Weg mit einem konstant-Zeit-Algorithmus. Wie die anderen Formeln zeigen, die nTEN Fibonacci-Zahl wächst exponentiell mit n. Auch mit 64-bit vorzeichenlosen Ganzzahlen, Sie müssen nur eine 94-Eintrag lookup-Tabelle, um zu decken das ganze Spektrum.

ZWEITER EDIT: Tun das matrix-exponential, mit einer eigendecomposition erste entspricht genau JDunkerly die Lösung unten. Die Eigenwerte dieser matrix sind die (1 + sqrt(5))/2 und (1 - sqrt(5))/2.

InformationsquelleAutor der Antwort Pillsy

Für die wirklich großen dieser rekursiven Funktion arbeiten. Dabei verwendet er die folgenden Gleichungen:

F(2n-1) = F(n-1)^2 + F(n)^2
F(2n) = (2*F(n-1) + F(n)) * F(n)

Müssen Sie eine Bibliothek, ermöglicht Ihnen die Arbeit mit großen ganzen zahlen. Ich benutze die BigInteger Bibliothek von https://mattmccutchen.net/bigint/.

Beginnen mit einem array von fibonacci-zahlen. Verwenden fibs[0]=0, fibs[1]=1 fibs[2]=1 fibs[3]=2, fibs[4]=3, usw. In diesem Beispiel verwende ich ein array von der ersten 501 (gezählt von 0). Finden Sie die ersten 500 nicht-null Fibonacci-zahlen hier: http://home.hiwaay.net/~jalison/Fib500.html. Es dauert ein wenig Bearbeiten, um es in das richtige format, aber das ist nicht allzu schwer.

Dann finden Sie jede Fibonacci-Zahl die Verwendung dieser Funktion (in C):

BigUnsigned GetFib(int numfib)
{
int n;
BigUnsigned x, y, fib;  

if (numfib < 501) //Just get the Fibonacci number from the fibs array
    {
       fib=(stringToBigUnsigned(fibs[numfib]));
    }
else if (numfib%2) //numfib is odd
    {
       n=(numfib+1)/2;
       x=GetFib(n-1);
       y=GetFib(n);
       fib=((x*x)+(y*y));
    }
else //numfib is even
    {
       n=numfib/2;
       x=GetFib(n-1);
       y=GetFib(n);
       fib=(((big2*x)+y)*y);
   }
return(fib);
}

Ich habe getestet dieses für die 25.000 TEN Fibonacci-Zahl und dergleichen.

InformationsquelleAutor der Antwort user3137939

mithilfe R

l1 <- (1+sqrt(5))/2
l2 <- (1-sqrt(5))/2

P <- matrix(c(0,1,1,0),nrow=2) #permutation matrix
S <- matrix(c(l1,1,l2,1),nrow=2)
L <- matrix(c(l1,0,0,l2),nrow=2)
C <- c(-1/(l2-l1),1/(l2-l1))

k<-20 ; (S %*% L^k %*% C)[2]
[1] 6765

InformationsquelleAutor der Antwort George Dontas

Fixed point Arithmetik ist ungenau. Jason ist C# - code gibt falsche Antwort für n = 71 (308061521170130 statt 308061521170129) und darüber hinaus.

Für die richtige Antwort, verwenden Sie ein Computer-algebra-system. Sympy ist wie eine Bibliothek für Python. Es gibt eine interaktive Konsole in http://live.sympy.org/ . Kopieren und einfügen mit dieser Funktion

phi = (1 + sqrt(5)) /2
def f(n):
    return floor(phi**n /sqrt(5) + 1/2)

Dann berechnen

>>> f(10)
55

>>> f(71)
308061521170129

Vielleicht möchten Sie versuchen, die Inspektion phi.

InformationsquelleAutor der Antwort Colonel Panic

Hier ist ein one-liner berechnet, dass F(n), mit ganzen zahlen der Größe O(n) O(log n) arithmetische Operationen:

for i in range(1, 50):
    print(i, pow(2<<i, i, (4<<2*i)-(2<<i)-1)//(2<<i))

Verwendung von ganzen zahlen der Größe O(n) zumutbar ist, weil das ist vergleichbar um die Größe der Antwort.

Um dies zu verstehen, lassen Sie phi-der goldene Schnitt (die größte Lösung für x^2=x+1) und F(n) die n ' te Fibonacci-Zahl, wobei F(0)=0, F(1)=F(2)=1

Nun, phi^n = F(n-1) + F(n)phi.

Beweis durch Induktion: phi^1 = 0 + 1*phi = F(0) + F(1)phi. Und wenn phi^n =
F(n-1) + F(n) - phi, dann ist phi^(n+1) = F(n-1)phi + F(n)phi^2 = F(n-1)phi +
F(n)(phi+1) = F(n) + (F(n)+F(n-1))phi = F(n) + F(n+1)phi. Die einzige heikle Schritt in dieser Berechnung ist das eine, ersetzt phi^2 (1+phi), die folgt, weil phi ist der goldene Schnitt.

Auch zahlen der form (a+b*phi), wobei a, b sind Ganzzahlen geschlossen unter Multiplikation.

Beweis: (p0+p1*phi)(q0+q1*phi) = p0q0 + (p0q1+q1p0)phi + p1q1*phi^2 =
p0q0 + (p0q1+q1p0)phi + p1q1*(phi+1) = (p0q0+p1q1) +
(p0q1+q1p0+p1q1)*phi.

Mithilfe dieser Darstellung kann man berechnen phi^n in O(log n) integer-Operationen mit Potenzierung durch Quadratur. Das Ergebnis wird sein, F(n-1)+F(n) - phi, aus denen man ablesen kann der n ' te Fibonacci-Zahl.

def mul(p, q):
    return p[0]*q[0]+p[1]*q[1], p[0]*q[1]+p[1]*q[0]+p[1]*q[1]

def pow(p, n):
    r=1,0
    while n:
        if n&1: r=mul(r, p)
        p=mul(p, p)
        n=n>>1
    return r

for i in range(1, 50):
    print(i, pow((0, 1), i)[1])

Beachten Sie, dass die Mehrheit dieser code ist ein standard-Potenzierung-von-Quadratur-Funktion.

Man die one-liner, beginnt diese zu beantworten, kann man festhalten, dass die Repräsentation von phi durch eine ausreichend große ganzzahlige X kann man durchführen (a+b*phi)(c+d*phi) als integer-operation (a+bX)(c+dX) modulo (X^2-X-1). Dann die pow Funktion ersetzt werden kann durch die standard-Python - pow - Funktion (die beinhaltet praktischerweise ein drittes argument z berechnet das Ergebnis modulo z. Die X gewählt ist 2<<i.

InformationsquelleAutor der Antwort Paul Hankin