wake-up-neo.com

Nte Fibonacci-Zahl für sehr großes 'n' ermitteln

Ich habe mich gefragt, wie man den n-ten Term der Fibonacci-Sequenz für einen sehr großen Wert von n sagen kann, sagen wir 1000000. Wenn man die Rekursionsgleichung fib(n)=fib(n-1)+fib(n-2) der Grundschule verwendet, dauert es 2-3 Minuten, um den 50. Term zu finden! 

Nach dem Googeln lernte ich die Binetsche Formel kennen, die jedoch nicht für Werte von n> 79 geeignet ist, wie es hier heißt.

Gibt es einen Algorithmus, um dies genauso zu tun, wie wir Primzahlen finden?

48
kunal18

Sie können die Matrix-Exponentiation-Methode (lineare Wiederholungsmethode) verwenden. Eine ausführliche Erklärung und Vorgehensweise finden Sie in this blog. Laufzeit ist O (log n).

Ich glaube nicht, dass es einen besseren Weg gibt, dies zu tun.

47
Wayne Rooney

Sie können viel Zeit sparen, indem Sie memoization verwenden. Vergleichen Sie beispielsweise die folgenden zwei Versionen (in JavaScript):

Version 1: normale Rekursion

var fib = function(n) {
  return n < 2 ? n : fib(n - 1) + fib(n - 2);
};

Version 2: Memoisierung

A. Verwenden Sie Unterstrich library

var fib2 = _.memoize(function(n) {
  return n < 2 ? n : fib2(n - 1) + fib2(n - 2);
});

B. bibliotheksfrei

var fib3 = (function(){
    var memo = {};
    return function(n) {
        if (memo[n]) {return memo[n];}
        return memo[n] = (n <= 2) ? 1 : fib3(n-2) + fib3(n-1);
    };
})();

Die erste Version benötigt für n = 50 (unter Chrome) mehr als 3 Minuten, während die zweite nur weniger als 5 ms dauert! Sie können dies in jsFiddle überprüfen.

Es ist nicht so überraschend, wenn wir wissen, dass die zeitliche Komplexität von Version 1 exponentiell ist (O (2N/2)), während Version 2 linear ist (O (N)). 

Version 3: Matrixmultiplikation

Darüber hinaus können wir die Zeitkomplexität sogar auf O (log (N)) reduzieren, indem wir die Multiplikation von N Matrizen berechnen.

matrix

wo Fn bezeichnet den n-ten Begriff der Fibonacci-Sequenz.

29
Hui Zheng

Ich stimme mit Wayne Roonys Antwort überein, dass die optimale Lösung in Schritten von O (log n) abgeschlossen wird, die Gesamtlaufzeitkomplexität jedoch von der Komplexität des verwendeten Multiplikationsalgorithmus abhängt. Bei Verwendung von Karatsuba Multiplication würde die Gesamtlaufzeitkomplexität beispielsweise O (n.) Seinlog23) ≈ O (n1,585).1

Die Matrix-Exponentiation ist jedoch nicht notwendigerweise der beste Weg, um dies zu erreichen. Wie ein Entwickler bei Project Nayuki bemerkt hat, trägt die Matrix-Exponentiation redundante Berechnungen mit sich, die entfernt werden können. Aus der Beschreibung des Autors:

Gegeben Fk und Fk + 1 können wir diese berechnen:


Beachten Sie, dass dies nur 3 Multiplikationen von BigInt zu BigInt pro Aufteilung erfordert, und nicht 8 als Matrixexponentiation.

Wir können es immer noch etwas besser machen. Eine der elegantesten Fibonacci-Identitäten hängt mit den Lucas-Zahlen zusammen:

wo Ln ist das nth Lucas-Nummer . Diese Identität kann weiter verallgemeinert werden als:

Es gibt einige mehr oder weniger äquivalente Wege , um rekursiv vorzugehen, aber die logischsten scheinen F zu seinn und Ln . Weitere Identitäten, die in der folgenden Implementierung verwendet werden, können entweder gefunden oder aus den für Lucas Sequences angegebenen Identitäten abgeleitet werden:

Um auf diese Weise vorzugehen, sind nur zwei Multiplikationen von BigInt zu BigInt pro Split erforderlich, und nur eine für das Endergebnis. Dies ist etwa 20% schneller als der von Project Nayuki bereitgestellte Code ( Testskript ). Hinweis: Die Originalquelle wurde leicht modifiziert (verbessert), um einen fairen Vergleich zu ermöglichen.

def fibonacci(n):
  def fib_inner(n):
    '''Returns F[n] and L[n]'''
    if n == 0:
      return 0, 2
    u, v = fib_inner(n >> 1)
    q = (n & 2) - 1
    u, v = u * v, v * v + 2*q
    if (n & 1):
      u1 = (u + v) >> 1
      return u1, 2*u + u1
    return u, v

  u, v = fib_inner(n >> 1)
  if (n & 1):
    q = (n & 2) - 1
    u1 = (u + v) >> 1
    return v * u1 + q
  return u * v

Aktualisieren

A greybeard weist darauf hin , das obige Ergebnis wurde bereits von Takahashi (2000) verbessert.2durch das Feststellen, dass das Quadrieren von BigInt im Allgemeinen (und speziell für den Schönhage-Strassen-Algorithmus) weniger rechenintensiv ist als die Multiplikation von BigInt. Der Autor schlägt eine Iteration vor, die sich auf F teiltn und Ln mit folgenden Identitäten:

Um auf diese Weise zu iterieren, sind zwei BigInt-Quadrate pro Split erforderlich, und nicht ein BigInt-Quadrat und eine BigInt-Multiplikation wie oben. Wie erwartet ist die Laufzeit für sehr große n messbar schneller als die obige Implementierung, für kleine Werte jedoch etwas langsamer (n <25000).

Dies kann jedoch auch etwas verbessert werden. Der Autor behauptet, dass "Es ist bekannt, dass der Product of Lucas Numbers-Algorithmus die wenigsten Bitoperationen verwendet, um die Fibonacci-Zahl F zu berechnenn. " Der Autor wählt dann den Algorithmus" Product of Lucas Numbers "aus, der zu der Zeit der schnellste bekannte war, wobei er sich auf F aufspalteten und Ln . Beachten Sie jedoch, dass Ln wird immer nur bei der Berechnung von F verwendetn + 1 . Dies erscheint etwas verschwenderisch, wenn man die folgenden Identitäten betrachtet:

wenn das erste direkt von Takahashi übernommen wird, ist das zweite Ergebnis der Matrix-Exponentiationsmethode (auch von Nayuki bekannt), und das dritte ist das Ergebnis der Addition der beiden vorhergehenden. Dies ermöglicht eine offensichtliche Trennung von Fn und Fn + 1 . Das Ergebnis erfordert einen BigInt-Zusatz weniger und, was noch wichtiger ist, eine Division durch 2 für gerade n; für ungerade n wird der Nutzen verdoppelt. In der Praxis ist dies signifikant schneller als die von Takahashi vorgeschlagene Methode für kleine n (10-15% schneller) und geringfügig schneller für sehr große n ( Testskript ).

def fibonacci(n):
  def fib_inner(n):
    '''Returns F[n] and F[n+1]'''
    if n == 0:
      return 0, 1
    u, v = fib_inner(n >> 1)
    q = (n & 2) - 1
    u *= u
    v *= v
    if (n & 1):
      return u + v, 3*v - 2*(u - q)
    return 2*(v + q) - 3*u, u + v

  u, v = fib_inner(n >> 1)
  # L[m]
  l = 2*v - u
  if (n & 1):
    q = (n & 2) - 1
    return v * l + q
  return u * l

Update 2

Seit dem ersten Posting habe ich auch das vorherige Ergebnis leicht verbessert. Abgesehen von den beiden BigInt-Quadraten wird bei F aufgeteiltn und Fn + 1 hat auch einen Overhead von drei BigInt-Additionen und zwei kleinen konstanten Multiplikationen pro Split. Dieser Aufwand kann durch Aufteilung auf L fast vollständig beseitigt werdenn und Ln + 1 stattdessen:

Das Aufteilen auf diese Weise erfordert wie zuvor zwei BigInt-Quadrate, jedoch nur einen einzigen BigInt-Zusatz. Diese Werte müssen jedoch auf die entsprechende Fibonacci-Nummer zurückgeführt werden. Glücklicherweise kann dies mit einer einzigen Division durch 5 erreicht werden:

Da bekannt ist, dass der Quotient ganzzahlig ist, kann eine genaue Divisionsmethode wie der mpz_divexact_ui von GMP verwendet werden. Das Aufrollen der äußersten Aufteilung ermöglicht es uns, den endgültigen Wert mit einer einzigen Multiplikation zu berechnen:

Wie in Python implementiert, ist dies für kleine n (5-10% schneller) und für sehr große n ( Testskript ) geringfügig schneller als die vorherige Implementierung.

def fibonacci(n):
  def fib_inner(n):
    '''Returns L[n] and L[n+1]'''
    if n == 0:
      return mpz(2), mpz(1)
    m = n >> 1
    u, v = fib_inner(m)
    q = (2, -2)[m & 1]
    u = u * u - q
    v = v * v + q
    if (n & 1):
      return v - u, v
    return u, v - u

  m = n >> 1
  u, v = fib_inner(m)
  # F[m]
  f = (2*v - u) / 5
  if (n & 1):
    q = (n & 2) - 1
    return v * f - q
  return u * f

1 Es ist ersichtlich, dass die Anzahl der Stellen (oder Bits) von F istn ~ O(n) als:

Die Laufzeitkomplexität bei der Karatsuba-Multiplikation kann dann wie folgt berechnet werden:


2 Takahashi, D. (2000), " Ein schneller Algorithmus zum Berechnen großer Fibonacci-Zahlen " (PDF), Informationsverarbeitungsbuchstaben 75, S. 243–246.

14
primo

Verwenden Sie Wiederholungsidentitäten http://en.wikipedia.org/wiki/Fibonacci_number#Other_identities , um die n- th-Nummer in log(n)-Schritten zu finden. Dafür müssen Sie beliebige Integer mit beliebiger Genauigkeit verwenden. Oder Sie können die genaue Antwort modulo eines Faktors berechnen, indem Sie bei jedem Schritt die modulare Arithmetik verwenden.

recurrence formula 1

recurrence formula 2

recurrence formula 3

Unter Beachtung der 3n+3 == 3(n+1) können wir eine single-rekursive- Funktion entwickeln, die zwei sequentielle Fibonacci-Zahlen bei jedem Schritt berechnet, indem die n durch 3 dividiert wird und die entsprechende Formel entsprechend der Restwert. IOW berechnet aus einem Paar @(3n+r,3n+r+1), r=0,1,2 in einem Schritt ein Paar @(n,n+1), so dass keine doppelte Rekursion und keine Memoisierung erforderlich ist. 

Ein Haskell-Code lautet here .

Update:

F(2n-1) =   F(n-1)^2    + F(n)^2   ===   a' = a^2 + b^2 
F(2n)   = 2 F(n-1) F(n) + F(n)^2   ===   b' = 2ab + b^2 

scheint zu schnellerem Code zu führen. Die Verwendung von "Lucas-Sequenzidentitäten" ist möglicherweise am schnellsten ( das liegt an dem Benutzer: primo , der diese Implementierung zitiert).

12
Will Ness

Die meisten Leute haben Ihnen bereits einen Link gegeben, der die Feststellung der N-ten Fibonacci-Zahl erklärt. Der Power-Algorithmus funktioniert auf gleiche Weise mit geringfügigen Änderungen.

Auf jeden Fall ist dies meine O (log N) -Lösung.

package algFibonacci;

import Java.math.BigInteger;

public class algFibonacci {
    // author Orel Eraki
    // Fibonacci algorithm
    // O(log2 n)
    public static BigInteger Fibonacci(int n) {

        int num = Math.abs(n);
        if (num == 0) {
            return BigInteger.ZERO;
        }
        else if (num <= 2) {
            return BigInteger.ONE;
        }

        BigInteger[][] number = { { BigInteger.ONE, BigInteger.ONE }, { BigInteger.ONE, BigInteger.ZERO } };
        BigInteger[][] result = { { BigInteger.ONE, BigInteger.ONE }, { BigInteger.ONE, BigInteger.ZERO } };

        while (num > 0) {
            if (num%2 == 1) result = MultiplyMatrix(result, number);
            number = MultiplyMatrix(number, number);
            num/= 2;
        }

        return result[1][1].multiply(BigInteger.valueOf(((n < 0) ? -1:1)));
    }

    public static BigInteger[][] MultiplyMatrix(BigInteger[][] mat1, BigInteger[][] mat2) {
        return new BigInteger[][] {
            {
                mat1[0][0].multiply(mat2[0][0]).add(mat1[0][1].multiply(mat2[1][0])), 
                mat1[0][0].multiply(mat2[0][1]).add(mat1[0][1].multiply(mat2[1][1]))
            },
            {
                mat1[1][0].multiply(mat2[0][0]).add(mat1[1][1].multiply(mat2[1][0])), 
                mat1[1][0].multiply(mat2[0][1]).add(mat1[1][1].multiply(mat2[1][1]))
            }
        };
    }

    public static void main(String[] args) {
        System.out.println(Fibonacci(8181));
    }
}
4
Orel Eraki

Für die Berechnung der Fibonacci-Zahlen ist der rekursive Algorithmus eine der schlechtesten Methoden. Durch einfaches Hinzufügen der beiden vorherigen Zahlen in einem for-Zyklus (als iterative Methode bezeichnet) werden keine 2-3 Minuten benötigt, um das 50. Element zu berechnen.

2
Bartis Áron

Hier ist eine Python-Version, um die n-te Fibonacci-Zahl in O (log (n)) zu berechnen.

def fib(n):
    if n == 0: 
        return 0

    if n == 1: 
        return 1

    def matmul(M1, M2):
        a11 = M1[0][0]*M2[0][0] + M1[0][1]*M2[1][0]
        a12 = M1[0][0]*M2[0][1] + M1[0][1]*M2[1][1]
        a21 = M1[1][0]*M2[0][0] + M1[1][1]*M2[1][0]
        a22 = M1[1][0]*M2[0][1] + M1[1][1]*M2[1][1]
        return [[a11, a12], [a21, a22]]

    def matPower(mat, p):
        if p == 1: 
            return mat

        m2 = matPower(mat, p//2)
        if p % 2 == 0:
            return matmul(m2, m2)
        else: 
            return matmul(matmul(m2, m2),mat)

    Q = [[1,1],[1,0]]

    q_final = matPower(Q, n-1)
    return q_final[0][0]

Um beliebig große Elemente der Fibonacci-Sequenz zu berechnen, müssen Sie die geschlossene Lösung - die Binet-Formel - verwenden und die Mathematik mit beliebiger Genauigkeit verwenden, um eine ausreichende Genauigkeit für die Berechnung der Antwort bereitzustellen.

Wenn Sie jedoch nur die Wiederholungsbeziehung verwenden, sollte nicht 2-3 Minuten dauern, um den 50. Begriff zu berechnen - Sie sollten in der Lage sein, die Ausdrücke auf jeder modernen Maschine innerhalb weniger Sekunden in Milliardenhöhe zu berechnen. Es klingt, als würden Sie die vollrekursive Formel verwenden, die zu einer kombinatorischen Explosion rekursiver Berechnungen führt. Die einfache iterative Formel ist viel schneller.

Die rekursive Lösung ist:

int fib(int n) {
  if (n < 2)
    return 1;
  return fib(n-1) + fib(n-2)
}

... und lehnen Sie sich zurück und beobachten Sie, wie der Stapel überläuft.

Die iterative Lösung ist:

int fib(int n) {
  if (n < 2)
    return 1;
  int n_1 = 1, n_2 = 1;
  for (int i = 2; i <= n; i += 1) {
    int n_new = n_1 + n_2;
    n_1 = n_2;
    n_2 = n_new;
  }
  return n_2;
}

Beachten Sie, dass wir im Wesentlichen den nächsten Begriff n_new aus den vorherigen Begriffen n_1 und n_2 berechnen und dann alle Begriffe für die nächste Iteration "mischen". Bei einer linearen Laufzeit auf dem Wert von n ist es für n in Milliardenhöhe (gut nach Integer-Überlauf für Ihre Zwischenvariablen) auf einer modernen Gigahertz-Maschine eine Sache von wenigen Sekunden.

1
sheu

Ich habe eine C-Implementierung geschrieben, die jede Skala der Eingangsnummer mit GNU gmp unterstützt.

Die Zeit, um fib für eine einzelne Zahl darzustellen, ist O(n), und der Platz für den Cache-Speicher ist O(1), (eigentlich waren alle fib für 0 ~ n).


Code

fib_cached_gmp.c:

// fibonacci - cached algorithm - any scale of input with GMP,
#include <gmp.h>
#include <stdio.h>
#include <stdlib.h>

// a single step,
void fib_gmp_next(mpz_t *cache) {
    mpz_add(cache[2], cache[0], cache[1]);
    mpz_set(cache[0], cache[1]);
    mpz_set(cache[1], cache[2]);
}

// figure fib for a single number, in O(n),
mpz_t *fib_gmp(int n, mpz_t *result) {
    // init cache,
    mpz_t cache[3]; // number: [fib(n-2), fib(n-1), fib(n)],

    mpz_init(cache[0]);
    mpz_init(cache[1]);
    mpz_init(cache[2]);

    mpz_set_si(cache[0], 0);
    mpz_set_si(cache[1], 1);

    while (n >= 2) {
        fib_gmp_next(cache);
        n--;
    }

    mpz_set(*result, cache[n]);

    return result;
}

// test - print fib from 0 to n, tip: cache won't be reused between any 2 input numbers,
void test_seq(int n) {
    mpz_t result;
    mpz_init(result);

    for (int i = 0; i <= n; i++) {
        gmp_printf("fib(%2d): %Zd\n", i, fib_gmp(i, &result));
    }
}

// test - print fib for a single num,
void test_single(int x) {
    mpz_t result;
    mpz_init(result);

    gmp_printf("fib(%d): %Zd\n", x, fib_gmp(x, &result));
}

int main() {
    // test sequence,
    test_seq(100);

    // test single,
    test_single(12345);

    return 0;
}

Installiere zuerst gmp:

// for Ubuntu,
Sudo apt-get install libgmp3-dev

Kompilieren:

gcc fib_cached_gmp.c -lgmp

Ausführen:

./a.out

Beispielausgabe:

fib( 0): 0
fib( 1): 1
fib( 2): 1
fib( 3): 2
fib( 4): 3
fib( 5): 5
fib( 6): 8
fib( 7): 13
fib( 8): 21
fib( 9): 34
fib(10): 55
fib(11): 89
fib(12): 144
fib(13): 233
fib(14): 377
fib(15): 610
fib(16): 987
fib(17): 1597
fib(18): 2584
fib(19): 4181
fib(20): 6765
fib(21): 10946
fib(22): 17711
fib(23): 28657
fib(24): 46368
fib(25): 75025
fib(26): 121393
fib(27): 196418
fib(28): 317811
fib(29): 514229
fib(30): 832040
fib(31): 1346269
fib(32): 2178309
fib(33): 3524578
fib(34): 5702887
fib(35): 9227465
fib(36): 14930352
fib(37): 24157817
fib(38): 39088169
fib(39): 63245986
fib(40): 102334155
fib(41): 165580141
fib(42): 267914296
fib(43): 433494437
fib(44): 701408733
fib(45): 1134903170
fib(46): 1836311903
fib(47): 2971215073
fib(48): 4807526976
fib(49): 7778742049
fib(50): 12586269025
fib(51): 20365011074
fib(52): 32951280099
fib(53): 53316291173
fib(54): 86267571272
fib(55): 139583862445
fib(56): 225851433717
fib(57): 365435296162
fib(58): 591286729879
fib(59): 956722026041
fib(60): 1548008755920
fib(61): 2504730781961
fib(62): 4052739537881
fib(63): 6557470319842
fib(64): 10610209857723
fib(65): 17167680177565
fib(66): 27777890035288
fib(67): 44945570212853
fib(68): 72723460248141
fib(69): 117669030460994
fib(70): 190392490709135
fib(71): 308061521170129
fib(72): 498454011879264
fib(73): 806515533049393
fib(74): 1304969544928657
fib(75): 2111485077978050
fib(76): 3416454622906707
fib(77): 5527939700884757
fib(78): 8944394323791464
fib(79): 14472334024676221
fib(80): 23416728348467685
fib(81): 37889062373143906
fib(82): 61305790721611591
fib(83): 99194853094755497
fib(84): 160500643816367088
fib(85): 259695496911122585
fib(86): 420196140727489673
fib(87): 679891637638612258
fib(88): 1100087778366101931
fib(89): 1779979416004714189
fib(90): 2880067194370816120
fib(91): 4660046610375530309
fib(92): 7540113804746346429
fib(93): 12200160415121876738
fib(94): 19740274219868223167
fib(95): 31940434634990099905
fib(96): 51680708854858323072
fib(97): 83621143489848422977
fib(98): 135301852344706746049
fib(99): 218922995834555169026
fib(100): 354224848179261915075
fib(12345): 400805695072240470970514993214065752192289440772063392234116121035966330621821050108284603033716632771086638046166577665205834362327397885009536790892524821512145173749742393351263429067658996935575930135482780507243981402150702461932551227590433713277255705297537428017957026536279252053237729028633507123483103210846617774763936154673522664591736081039709294423865668046925492747583953758325850613548914282578320544573036249175099094644435323970587790740267131607004023987409385716162460955707793257532112771932704816713519196128834470721836094265012918046427449156654067195071358955104097973710150920536847877434256779886729555691213282504703193401739340461924048504866698176130757935914248753973087073009601101912877383634628929467608983980664185363370286731771712542583041365328648124549323878806758395652340861186334027392307091079257180835672989798524084534677252369585918458720952520972332496025465803523315515681084895362126005441170936820059518262349022456888758938672920855739736423917065122816343192172271301981007636070751378441363091187289522144227851382197807194256392294919912037019476582418451273767976783751999133072126657949249799858935787018952232743400610036315564885371356712960608966755186612620425868892621106627825137425386831657368826398245606147944273998498356443362170133234924531673939303668042878258282104212769625245680321344034442698232414181912301904509531018692483863038992377680591406376081935756597411807864832452421993121459549055042253305545594009110753730302061881025182053074077930494574304284381890534053065639084253641881363463311184024281835265103884539012874542416238100890688593076189105555658375552988619203325356676814545718066196038345684671830102920209857682912971565838896011294918349088792184108318689299230788355618638040186790724351073650210514429114905535411044888774713860041341593318365792673354888566799196442017231870631867558530906286613228902689695061557951752309687806567573290910909535395758148994377158637050112347651517847188123790794231572729345617619677555583207012253101701328971768827861922408064379891201972881554890367344239218306050355964382953279316318309272212482218232309006973312977359562553184608144571713073802285675503209229581312057259729362382786183100343961484090866057560474044189870633912200595478051573769889968342203512550302655117491740823696686983281784153050366346823513213598551985596176977626982962058849363351794302206703907577970065793839511591930741441079234179943480206539767561244271325923343752071038968002157889912694947204003637791271084190929058369801531787887444598295425899927970

Tipps:

  • Die test_seq() ist nicht sehr schlau, der Cache wurde nicht zwischen zwei Eingangsnummern wiederverwendet.
    Während ein einzelner Aufruf von fib_gmp() tatsächlich ausreicht, reicht es aus, wenn Sie gmp_printf() eine fib_gmp_next() hinzufügen und in jedem Schritt fib_gmp_next() das i angeben.
    Jedenfalls ist es nur für die Demo.
1
Eric Wang

Zunächst kann man sich aus dem größten bekannten Fibonacci-Begriff eine Vorstellung des höchsten Begriffs bilden. siehe auch schrittweise durch rekursive Fibonacci-Funktionspräsentation . Ein interessierter Ansatz zu diesem Thema ist in diesem Artikel . Versuchen Sie auch, in dem schlechtesten Algorithmus der Welt darüber zu lesen. .

1
user1929959

hier ist ein kurzer Python-Code, der bis zu 7 Stellen gut funktioniert. Benötigt nur ein 3-Element-Array

def fibo(n):
    i=3
    l=[0,1,1]
    if n>2:
        while i<=n:
            l[i%3]= l[(i-1) % 3] + l[(i-2) % 3]
            i+=1
    return l[n%3]
0
#include <bits/stdc++.h>
#define MOD 1000000007
using namespace std;

const long long int MAX = 10000000;

// Create an array for memoization
long long int f[MAX] = {0};

// Returns n'th fuibonacci number using table f[]
long long int fib(int n)
{
    // Base cases
    if (n == 0)
        return 0;
    if (n == 1 || n == 2)
        return (f[n] = 1);

    if (f[n])
        return f[n];

    long long int k = (n & 1)? (n+1)/2 : n/2;

    f[n] = (n & 1)? (fib(k)*fib(k) + fib(k-1)*fib(k-1)) %MOD
        : ((2*fib(k-1) + fib(k))*fib(k))%MOD;

    return f[n];
}

int main()
{
    long long int n = 1000000;
    printf("%lld ", fib(n));
    return 0;
}

Zeitkomplexität: O (Log n), da wir das Problem in jedem rekursiven Aufruf auf die Hälfte teilen.

0
Sourabh Goel

Die einfachste Pythonic-Implementierung kann wie folgt angegeben werden

def Fib(n):
    if (n < 0) : 
        return -1
    Elif (n == 0 ): 
        return 0
    else:
        a = 1
        b = 1
        for i in range(2,n+1):
            a,b = b, a+b
        return a
0
Alex Mercer

Elegantere Lösung in Python

def fib(n):
  if n == 0: 
    return 0
  a, b = 0, 1
  for i in range(2, n+1):
    a, b = b, a+b
  return b
0
farincz

Ich habe ein UVA Problem gelöst: 495 - Fibonacci Freeze

Es generiert alle Fibonacci-Zahlen bis 5000. und druckt Ausgaben für gegebene Eingaben (Bereich 1. - 5.000).

Es wird mit einer Laufzeit von 00.00 Sekunden akzeptiert.

Die Fibonacci-Nummer für 5000 lautet:

3878968454388325633701916308325905312082127714646245106160597214895550139044037097010822916462210669479293452858882973813483102008954982940361430156911478938364216563944106910214505634133706558656238254656700712525929903854933813928836378347518908762970712033337052923107693008518093849801803847813996748881765554653788291644268912980384613778969021502293082475666346224923071883324803280375039130352903304505842701147635242270210934637699104006714174883298422891491273104054328753298044273676822977244987749874555691907703880637046832794811358973739993110106219308149018570815397854379195305617510761053075688783766033667355445258844886241619210553457493675897849027988234351023599844663934853256411952221859563060475364645470760330902420806382584929156452876291575759142343809142302917491088984155209854432486594079793571316841692868039545309545388698114665082066862897420639323438488465240988742395873801976993820317174208932265468879364002630797780058759129671389634214252579116872755600360311370547754724604639987588046985178408674382863125

#include<stdio.h>
#include<string.h>

#define LIMIT 5001
#define MAX 1050
char num[LIMIT][MAX];
char result[MAX];
char temp[MAX];

char* sum(char str1[], char str2[])
{
    int len1 = strlen(str1);
    int len2 = strlen(str2);
    int minLen, maxLen;
    int i, j, k;

    if (len1 > len2)
        minLen = len2, maxLen = len1;
    else
        minLen = len1, maxLen = len2;
    int carry = 0;
    for (k = 0, i = len1 - 1, j = len2 - 1; k<minLen; k++, i--, j--)
    {
        int val = (str1[i] - '0') + (str2[j] - '0') + carry;
        result[k] = (val % 10) + '0';
        carry = val / 10;
    }
    while (k < len1)
    {
        int val = str1[i] - '0' + carry;
        result[k] = (val % 10) + '0';
        carry = val / 10;

        k++; i--;
    }
    while (k < len2)
    {
        int val = str2[j] - '0' + carry;
        result[k] = (val % 10) + '0';
        carry = val / 10;

        k++; j--;
    }
    if (carry > 0)
    {
        result[maxLen] = carry + '0';
        maxLen++;
        result[maxLen] = '\0';
    }
    else
    {
        result[maxLen] = '\0';
    }
    i = 0;
    while (result[--maxLen])
    {
        temp[i++] = result[maxLen];
    }
    temp[i] = '\0';
    return temp;
}

void generateFibonacci()
{
    int i;
    num[0][0] = '0'; num[0][1] = '\0';
    num[1][0] = '1'; num[1][1] = '\0';
    for (i = 2; i <= LIMIT; i++)
    {
        strcpy(num[i], sum(num[i - 1], num[i - 2]));
    }
}

int main()
{
    //freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
    int N;
    generateFibonacci();
    while (scanf("%d", &N) == 1)
    {
        printf("The Fibonacci number for %d is %s\n", N, num[N]);
    }
    return 0;
}
0

Berechnung der Fibonacci-Zahlen (mit Haskell):

Version 1 : Direkte Übersetzung der Definition in Code (sehr langsame Version):

fib :: Integer -> Integer
fib 0 = 1
fib 1 = 1
fib n =
  fib (n - 1) + fib (n - 2)

Version 2 : Mit der Arbeit, die wir zum Berechnen von F_ ​​{n - 1} und F_ ​​{n - 2} (der schnellen Version) durchgeführt haben:

fibs = 0 : 1 : zipWith (+) fibs (tail fibs)

Sie können die n-te Fibonacci erhalten, indem Sie einfach fibs !! n ausführen, wobei n der Index ist.

Version 3 : Verwenden der Matrixmultiplikationsmethode. (die noch schnellere Version):

-- declaring a matrix
data Matrix = Matrix
  ( (Integer, Integer)
  , (Integer, Integer)
  )
  deriving (Show, Eq)

-- creating it an instance of Num
-- so that if we implement (*) we get (^) for free
instance Num Matrix where
  (*) = mMult

  -- don't need these
  (+) = undefined
  negate = undefined
  fromInteger = undefined
  abs = undefined
  signum = undefined


-- 2-d matrix multiplication
mMult :: Matrix -> Matrix -> Matrix
mMult (Matrix ((a11, a12), (a21, a22))) (Matrix ((b11, b12), (b21, b22))) =
  Matrix
    ( (a11 * b11 + a12 * b21, a11 * b12 + a12 * b22)
    , (a21 * b11 + a22 * b21, a21 * b12 + a22 * b22)
    )

-- base matrix for generating fibonacci
fibBase :: Matrix
fibBase =
  Matrix ((1,1), (1,0))

-- get the large fibonacci numbers
fastFib :: Int -> Integer
fastFib n =
  let
    getNth (Matrix ((_, a12), _)) = a12
  in
    getNth (fibBase ^ n)
0
Sherub Thakur

Ich habe einen Quellcode in c, um sogar die 3500. Fibonacci-Nummer zu berechnen: - Für weitere Details besuchen Sie bitte 

http://codingloverlavi.blogspot.in/2013/04/fibonacci-series.html

quellcode in C: -

#include<stdio.h>
#include<conio.h>
#define max 2000

int arr1[max],arr2[max],arr3[max];

void fun(void);

int main()
{
    int num,i,j,tag=0;
    clrscr();
    for(i=0;i<max;i++)
        arr1[i]=arr2[i]=arr3[i]=0;

    arr2[max-1]=1;

    printf("ENTER THE TERM : ");
    scanf("%d",&num);

    for(i=0;i<num;i++)
    {
        fun();

        if(i==num-3)
            break;

        for(j=0;j<max;j++)
            arr1[j]=arr2[j];

        for(j=0;j<max;j++)
            arr2[j]=arr3[j];

    }

    for(i=0;i<max;i++)
    {
        if(tag||arr3[i])
        {
            tag=1;
            printf("%d",arr3[i]);
        }
    }


    getch();
    return 1;
}

void fun(void)
{
    int i,temp;
    for(i=0;i<max;i++)
        arr3[i]=arr1[i]+arr2[i];

    for(i=max-1;i>0;i--)
    {
        if(arr3[i]>9)
        {
            temp=arr3[i];
            arr3[i]%=10;
            arr3[i-1]+=(temp/10);
        }
    }
}
0
Lavish Kothari

Mit etwas Kenntnis der diskreten Mathematik können Sie jede Fibonacci-Zahl in konstanter Zeit O (1) finden. Es gibt etwas, das als lineare homogene Wiederholungsbeziehung bezeichnet wird. 

Die Fibonacci-Sequenz ist ein berühmtes Beispiel.

Um die nte Fibonacci-Zahl zu finden, müssen wir diese finden 

f

Wir wissen das

f1

woher 

f2

Dann ist die charakteristische Gleichung 

f3

Nachdem Sie die Wurzeln der charakteristischen Gleichung gefunden und in die erste Gleichung eingesetzt haben

f4

Schließlich müssen wir den Wert von Alpha 1 und Alpha 2 ermitteln

ff

Jetzt können Sie diese Gleichung verwenden, um eine beliebige Fibonacci-Zahl in O (1) zu finden.

0
Omar Alghamdi