n-ième nombre de fibonacci dans sublinéaire temps

Est-il un algorithme pour calculer le n-ième nombre de fibonacci dans la sous-linéaire dans le temps?

  • On pourrait dire que c'est lié à des algorithmes, depuis l'OP fait une vague allusion à la complexité algorithmique... je serais toujours curieux de ce algorithme de bien.
  • Les deux réponses ci-dessous ont la bonne formule. Si cette question est en relation avec la programmation: c'est une partie de l'informatique. L'appareil utilisé pour dériver la formule est connue comme "générer" et a un rôle important dans l'algorithme d'analyse.
  • Lors de la génération de fonctions sont utiles, ils ne sont pas nécessaires pour tirer le fermé forme d'expression de la séquence de Fibonacci.
  • Vous avez un problème que vous voulez résoudre, pour quelque raison que ce soit, et que vous voulez le faire de manière efficace. Parfois, la compréhension voulue sera une nouvelle mise en œuvre, parfois un algorithme, et parfois les mathématiques. Il n'est pas nécessaire pour dénoncer la situation comme "pas de programmation relative" à chaque fois que ce dernier arrive.
  • La taille du résultat est linéaire en n. Il n'est donc pas un tel algorithme. Bien sûr, cela ne veut pas invalider tout de nice réponses ci-dessous qui calculer les nombres de Fibonacci à l'aide de O(log n) opérations arithmétiques.
  • Oui. Parce qu'ils sont le calcul des approximations.
  • Il ressemble à stackoverflow.com/questions/30595844/...
  • Cela dépend de ce qui est "du temps": si le "temps" est mesuré dans des opérations arithmétiques, alors vous pouvez calculer le résultat en log(n) fois. Si le "temps" est mesurée en bits, alors vous ne pouvez pas. Notez que dans une grande partie de la théorie de la complexité, le choix de "temps" est flexible (par exemple: algorithmes de tri d'utilisation "du temps" pour désigner les comparaisons par paires, et également d'une table de hachage de l'analyse de l'utilisation "du temps" pour les comparaisons de moyennes). Ni l'un ni l'décrire avec précision le temps qu'il effectuait sur un "vrai" ordinateur (parce que le calcul d'un hash n'est pas O(1) pour arbitraire de gros objets), mais personne ne se plaint de mer).

InformationsquelleAutor Biswajyoti Das | 2009-10-06
  1. 64

    La nème nombre de Fibonacci est donnée par

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

    où 

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

    En supposant que la primitive d'opérations mathématiques (+, -, * et /) sont O(1) vous pouvez utiliser ce résultat pour calculer la nème nombre de Fibonacci dans O(log n) temps (O(log n) en raison de l'élévation à la puissance de la formule).

    En 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);
}
    • En aparté, je serais probablement le défenseur de la prise de ces variables const plutôt que static, juste pour être sûr.
    • Scharley: Oui, ils devraient probablement, mais alors que j'aurais à clé dans la valeur décimale pour 1 / Math.Sqrt(5) et (1 + Math.Sqrt(5)) / 2 que C# ne pas laisser const valeurs calculées à l'aide de Math.Sqrt. Pour nos besoins ici, la formule est plus clair pour comprendre que le mystérieux valeurs décimales serait.
    • c'est ce que les commentaires sont pour. Mais comme il est statique, la différence est si petite qu'elle n'est pas la peine de jouer avec.
    • Coehoorn: je suis d'accord avec vous. J'ai essayé de garder les choses simples ici.
    • Je n'ai pas downvoted vous, mais d'autres peuvent le faire, parce que votre réponse suggère que le n-ième nombre de fibonacci peut être calculée en temps O(log n) le temps, ce qui est faux. Votre code est le calcul d'une approximation. Votre code devrait être d'au moins O(n) en précision arbitraire, car la longueur de la réponse est O(n).
    • La formule n'est pas une approximation. Le n-ième nombre de Fibonacci est égale à l'étage de phi^n / sqrt(5) + 1/2 où phi = (1 + sqrt(5)) / 2. C'est un fait. Deuxièmement, je comprends le point que d'autres ont au sujet de la longueur de la réponse étant O(n) mais j'ai ajouté une remarque à ma réponse en supposant que la primitive opérations mathématiques de prendre de la constante de temps (je sais qu'ils ne sont pas, sauf si vous avez lié les intrants). Mon point est que nous pouvons trouver le n-ième nombre de Fibonacci dans O(log n) les opérations arithmétiques.
    • En supposant que l'exponentiation est O(1) rend l'ensemble de l'algorithme O(1). Ce qui serait bien, cependant, l'exponentiation est pas O(1) et ne sont ni les autres primitives des opérations mathématiques. Donc, en bref, la formule est belle, mais il ne parvient pas à calculer le résultat dans la sous-linéaire dans le temps.
    • Voici quelque chose d'intéressant: double foo = 1.6; printf ("%.40f\n", foo); Imprime: 1.6000000000000000888178419700125232338905 Maintenant ce n'est à prévoir en raison de la norme IEEE 754 en virgule flottante. Tentez votre constantes ci-dessus: double foo = 1.6180339887498948482045868343656; printf ("%.40f\n", foo); Imprime: 1.6180339887498949025257388711906969547272 Donc, la question est de savoir quand est-ce que l'erreur d'arrondi début à la question?
    • La formule n'est pas une approximation, mais le code est une approximation (sauf sur un imaginaire C# de la mise en œuvre dans les Mathématiques.Pow(...) a une précision infinie, dans ce cas, le code est en O(n)).
    • En fait, remarque l'utilisation de Math.Floor. Le résultat de l'exécution de ce code, même sur un pathétique machine qui ne dispose pas d'une précision infinie, est la nème nombre de Fibonacci.
    • Nope. Exécuter votre code sur n=1000 (pour laquelle le nombre de Fibonacci 43466...849228875 a seulement 209 chiffres) et dites-moi si vous obtenez tous les chiffres à droite. Pour Les Mathématiques.Sol pour obtenir la partie entière de droite, ceux de nombreux chiffres doivent être calculés de manière précise par les Mathématiques.Pow. En fait, dans mon implémentation C++, même les 16 chiffres F_{74} = 130496954492865 est calculée correctement, même si l'entier 130496954492865 peut être représenté exactement (avec long long), et je serais surpris si C# est beaucoup plus de chiffres que.
    • le code est correct pour la première 46 nombres de Fibonacci, puis il déborde. Le classique a,b = b, a+b algorithme fait la même chose. Toutefois, si vous modifiez int à long dans le C#, puis il fait une erreur à n=71.
    • il donne de mauvais résultats pour des valeurs plus élevées

    InformationsquelleAutor jason
  2. 98

    La suite de Pillsy référence à des exponentielles de matrices, telles que pour la matrice

    M = [1 1] 
[1 0]

    puis 

    fib(n) = Mn1,2

    Sensibilisation des matrices de pouvoirs utilisation répétée de la multiplication n'est pas très efficace.

    Deux approches pour des exponentielles de matrices sont diviser et conquérir ce qui donne Mn dans S(ln n) étapes, ou de la valeur propre de décomposition qui est de la constante de temps, mais peut introduire des erreurs à cause du peu de précision en virgule flottante.

    Si vous voulez l'exacte valeur supérieure à la précision de votre point flottant de mise en œuvre, vous devez utiliser l'O ( ln n ) approche basée sur cette relation: 

    Mn = (Mn/2)2 si n même 
= M·Mn-1 si n est bizarre

    La valeur propre de décomposition sur M trouve deux matrices U et Λ tels que Λ est diagonale et 

     M = U Λ U-1 
Mn = ( U Λ U-1) n 
= U Λ U-1 U Λ U-1 U Λ U-1 ... n fois 
= U Λ Λ Λ ... U-1 
= U Λ n U-1

    Élever un la diagonale de la matrice de Λ de la nth puissance est une simple question d'élever chaque élément de Λ de la nth, de sorte que cela donne un O(1) méthode de collecte de M de la nth pouvoir. Cependant, les valeurs de Λ ne sont pas susceptibles d'être des entiers, de sorte que certains d'erreur va se produire.

    La définition de Λ pour notre matrice 2x2 comme

    Λ = [ λ1 0 ] 
= [ 0 λ2 ]

    De trouver chaque λ, nous résolvons 

     |M - λI| = 0

    qui donne

     |M - λI| = -λ ( 1 - λ ) - 1 

λ2 - λ - 1 = 0

    à l'aide de la formule quadratique 

    λ = ( -b ± √ ( b2 - 4ac ) ) /2a 
= ( 1 ± √5 ) /2 
{ λ1, λ2 } = { Φ, 1-Φ } où Φ = ( 1 + √5 ) /2

    Si vous avez lu la réponse de Jason, vous pouvez voir où cela va aller.

    De problèmes pour les vecteurs propres X1 et X2:

    si X1 = [ X1,1, X1,2 ] 

M.X1 1 = λ1X1 

X1,1 + X1,2 = λ1 X1,1 
X1,1 = λ1 X1,2 

=> 
X1 = [ Φ, 1 ] 
X2 = [ 1-Φ, 1 ]

    Ces vecteurs donner U:

    U = [ X1,1, X2,2 ] 
[ X1,1, X2,2 ] 

= [ Φ, 1-Φ ] 
[ 1, 1 ]

    De l'inversion de U à l'aide de

    A = [ a b ] 
[ c d ] 
=> 
A-1 = ( 1 /|A| ) [ d-b ] 
[ -c ]

    donc U-1 est donnée par

    U-1 = ( 1 /( Φ - ( 1 - Φ ) ) [ 1 Φ-1 ] 
[ -1 Φ ] 
U-1 = ( √5 )-1 [ 1 Φ-1 ] 
[ -1 Φ ]

    Sanity check:

    UΛU-1 = ( √5 )-1 [ Φ 1 Φ ] . [ Φ 0 ] . [ 1 Φ-1 ] 
[ 1 1 ] [ 0 1-Φ ] [ -1 Φ ] 

laissez Ψ = 1-Φ, l'autre valeur propre 

comme Φ est une racine de λ2-λ-1=0 
soi-ΨΦ = Φ2-Φ = 1 
et Ψ+Φ = 1 

UΛU-1 = ( √5 )-1 [ Φ Ψ ] . [ Φ 0 ] . [ 1 -Ψ ] 
[ 1 1 ] [ 0 Ψ ] [ -1 Φ ] 

= ( √5 )-1 [ Φ Ψ ] . [ Φ -ΨΦ ] 
[ 1 1 ] [ -Ψ ΨΦ ] 

= ( √5 )-1 [ Φ Ψ ] . [ Φ 1 ] 
[ 1 1 ] [ -Ψ -1 ] 

= ( √5 )-1 [ Φ2-Ψ2 Φ-Ψ ] 
[ Φ-Ψ 0 ] 

= [ Φ+Ψ 1 ] 
[ 1 0 ] 

= [ 1 1 ] 
[ 1 0 ] 

= M

    De sorte que la vérification générale détient.

    Maintenant, nous avons tout ce dont nous avons besoin pour calculer Mn1,2:

    Mn = UΛnU-1 
= ( √5 )-1 [ Φ Ψ ] . [ Φn 0 ] . [ 1 -Ψ ] 
[ 1 1 ] [ 0 Ψn ] [ -1 Φ ] 

= ( √5 )-1 [ Φ Ψ ] . [ Φn -ΨΦn ] 
[ 1 1 ] [ -Ψn ΨnΦ ] 

= ( √5 )-1 [ Φ Ψ ] . [ Φn Φn-1 ] 
[ 1 1 ] [ -Ψn -Ψn-1 ] comme ΨΦ = -1 

= ( √5 )-1 [ Φn+1-Ψn+1 Φn-Ψn ] 
[ Φn-Ψn Φn-1-Ψn-1 ]

    donc

     fib(n) = Mn1,2 
= ( Φn - (1-Φ)n ) /√5

    Qui est d'accord avec la formule donnée ailleurs.

    Vous pouvez obtenir à partir d'une relation de récurrence, mais en ingénierie de l'informatique et de la simulation, le calcul de valeurs propres et vecteurs propres de matrices de grande taille est une activité importante, car elle donne de la stabilité et des harmoniques de systèmes d'équations, ainsi que de permettre d'élever des matrices à haute pouvoirs efficacement.

    • +1 Super trucs, comme d'habitude. Qu'avez-vous utilisé pour composer il? LaTeX?
    • non, juste de la patience et un éditeur de texte
    • C'est de copier-collé à partir du livre de l'Algèbre de Gilbert Strang, ou à partir d'autres bon livre d'Algèbre Linéaire.
    • il n'était pas "copier collé", mais en fait comme un exercice pour vérifier que je pouvais souviens encore de ma lin un, avec une référence à l'Université Ouverte de notes de cours et de wikipédia.
    • J'ai pris le cours de L Algèbre avec Gilbert Strang, et il était identique. Tout à fait, le problème d'exprimer la récursivité par la matrice de décomposition est classique, et peut être trouvé dans tout bon livre de texte / cours.
    InformationsquelleAutor Pete Kirkham
  3. 55

    Si vous voulez le nombre exact (qui est un "bignum", plutôt qu'un int/float), je crains que

    C'est impossible!

    Comme indiqué ci-dessus, la formule pour les nombres de Fibonacci est:

    fib n = floor (phin/√5 + 1/2)

    fib n ~= phin/√5

    Combien de chiffres est fib n?

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

    numDigits (fib n) = n * const + const

    c'est O(n)

    Depuis l'demandé résultat est de O(n), il ne peut pas être calculé en moins de O(n) temps.

    Si vous voulez seulement la baisse des chiffres de la réponse, alors il est possible de calculer des sous-linéaire dans le temps à l'aide de la matrice de l'élévation à la puissance de la méthode.

    • C'est la seule réponse correcte qui a été posté.
    • Pouvez-vous expliquer cette nouvelle? 2^n a n+1 chiffres significatifs, mais peuvent être générés en temps constant.
    • Cela dépend de ce qu'sortie que vous voulez. Si, par exemple, vous souhaitez conserver votre numéro de chiffres, puis de même pour les 2^n vous aurez pour allouer et claire un buffer de la taille appropriée et cela prendrait du temps linéaire.
    • Permettez-moi de reformuler ce, si je comprends bien. En théorie, le calcul de fib_n nécessite le calcul de n chiffres donc, pour tout arbitraire n il faudra du temps O(n) fois. Toutefois, si fib_n < sizeof(long long) puis nous avons peut calculer fib_n en O(log n) fois depuis l'architecture de la machine est de fournir un mécanisme parallèle de la définition de l'bits. (Par exemple, int i = -1; nécessite la mise en 32 bits, mais sur une machine 32 bits toutes les 32 bits peuvent être définies en temps constant.
    • Si vous souhaitez seulement à l'appui de résultats qui répondent à en 32 bits, alors vous pouvez aussi avoir une table de recherche pour ces 48 premiers résultats de la série. C'est évidemment O(1), mais: les grands-O analyse pour bornée N est idiot, comme vous pouvez toujours intégrer quoi que ce soit dans le facteur constant. Donc, ma réponse se réfère à la surabondance de l'entrée.
    • Pourriez-vous démontrer votre logique pour un exemple bien connu comme O(n*log n) pour la comparaison basée sur le tri d'une séquence de n nombres, où chacun a O(log n) chiffres?
    • Ce qui est bien ou mal en fonction de ce que vous avez l'intention "du temps" pour dire. Pour le tri (ou table de hachage look ups), "le temps" signifie le nombre de comparaisons. Dans la question, il pourrait signifier des opérations arithmétiques. Dans cette réponse, il est pris pour signifier quelque chose comme chiffres-sage des opérations.
    • Cela dépend de votre choix de base. Le calcul des nombres de Fibonacci dans la base de Phi(ou même plus trivialement, dans un de fibonacci encodage) devrait être O(1).
    • Utilisez-vous souvent non entier bases?
    • Souvent peut-être pas la meilleure façon de le décrire, mais de la base de phi est la troisième plus fréquente de base que j'utilise, après Décimal et binaire (comptage octal et hexadécimal en binaire). Dans certains cas, vous souhaitez utiliser une base aussi proche de 1 que possible. Mais le plus petit entier plus grand que 1 est 2. Si c'est trop grand, vous devez utiliser un non-entier et pour ces cas, le nombre d'or est le choix le plus courant puisque les nombres entiers ont finis représentations.
    • lorsque vous souhaitez utiliser une base aussi proche de 1 que possible? et ne serait pas entiers ont fini représentation dans la base de sqrt(2), ce qui est encore plus proche de 1, comme bien? comment est-phi mieux que sqrt(2)?
    • Entiers sera en effet a une durée de représentation dans la base de sqrt(2), mais il va juste être de zéro sur les chiffres, c'est à dire l'équivalent en base 2. Si l'un de ces étranges chiffres en base sqrt(2) est différente de zéro, vous avez un nombre irrationnel. L'un des cas où vous voudrez base de phi est en Can lors de la conversion en continu des signaux analogiques. Autant que je sache, c'est le "industrielle" de l'application de la base de phi, où il est utilisé pour réduire coarse graining d'arrondi lorsque le signal. Personnellement, j'ai utilisé la base de phi et de fibonacci encodages comme un notationally moyen commode de travailler avec de Fibonacci anyon représentations de la tresse groupe.
    • Très intéressant (en.wikipedia.org/wiki/Beta_encoder). Je n'ai pas encore assez appris, mais c'est cool de savoir que ces choses ont eu un usage pratique.
    • il est significatif de parler de la complexité des classes pour le tri d'un nombre illimité de taille fixe des objets. Ou même pour parler d'un tri bornée numéro de fixe la taille des objets, parce qu'il se développe assez lentement pour asymptotique des effets de matière sur la pratique des ordinateurs.
    • Mais Fib(n) croît de façon exponentielle et donc de frappe n'importe quelle largeur fixe aussi rapidement que nous avons besoin d'examiner la mise en œuvre des détails comme le CPU microarchitecture et constante de facteurs, pas seulement de la complexité de la classe. par exemple, Indexé branche au-dessus sur X86 64 bits mode et Langage d'Assemblage (x86): Comment créer une boucle pour calculer la suite de Fibonacci. Également liées: Écrire de la manière la plus rapide de Fibonacci Fib(20mil) à l'aide de précision arbitraire techniques (avec O(log2(n)) a prolongé la précision des mesures à l'aide de BPF).

    InformationsquelleAutor yairchu
  4. 34

    L'un des les exercices de SICP est à propos de ce, qui a la réponse décrit ici.

    À l'impératif de style, le programme devrait ressembler à quelque chose comme

    Fonction Fib(count) 
un ← 1 
b ← 0 
p ← 0 
q ← 1 

While count > 0 Ne 
Si Même(count) Puis 
p ← p2 + q2 
q ← 2pq + q2 
count ← count ÷ 2 
Else 
un ← bq + aq + pa 
b ← bp + aq 
count ← count - 1 
End if 
Fin tant que 

Retour b 
n
    InformationsquelleAutor Nietzche-jou
  5. 24

    Vous pouvez le faire par exponentiating une matrice d'entiers ainsi. Si vous avez la matrice 

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

    puis (M^n)[1, 2] va être égale à la nème nombre de Fibonacci, si [] est une matrice indice et ^ est exponentielles de matrices. Pour une taille fixe de la matrice, l'exponentiation à un positif intégrale de la puissance peut être fait en O(log n) le temps de la même manière que les nombres réels.

    EDIT: bien sûr, selon le type de réponse que vous voulez, vous pourriez être en mesure de s'en tirer avec une constante de temps de l'algorithme. Comme les autres formules de spectacle, le nème nombre de Fibonacci croît de façon exponentielle avec n. Même avec la version 64 bits des entiers non signés, vous aurez seulement besoin d'un 94-entrée de la table de recherche afin de couvrir l'ensemble de la gamme.

    DEUXIÈME EDIT: Faire de la matrice exponentielle avec un eigendecomposition première est exactement équivalente à JDunkerly la solution ci-dessous. Les valeurs propres de cette matrice sont les (1 + sqrt(5))/2 et (1 - sqrt(5))/2.

    • Utiliser les modes propres de la décomposition de M pour calculer M^n efficacement.
    • La méthode proposée est très bien pour les calculs en nombres entiers (sans doute avec de longues arithmétique). Approche avec eigen décomposition n'est pas intéressant: si vous n'avez pas besoin de calculs avec des entiers, puis utiliser la formule de Jason réponse.
    • La formule de Jason réponse est le résultat donné par eigen décomposition, de sorte que vous êtes contredire vous-même.
    • Kirkham Cette formule peut être obtenue par plusieurs méthodes: les caractéristiques de l'équation, eigen décomposition, la preuve par induction. Je ne suis pas sûr, que eigen décomposition est le plus facile. En tout cas c'est bien connu, et il est plus facile de l'utiliser immédiatement
    InformationsquelleAutor Pillsy
  6. 5

    Wikipedia a fermé solution de la forme
    http://en.wikipedia.org/wiki/Fibonacci_number

    Ou en c#:

        public static int Fibonacci(int N)
    {
        double sqrt5 = Math.Sqrt(5);
        double phi = (1 + sqrt5) /2.0;
        double fn = (Math.Pow(phi, N) - Math.Pow(1 - phi, N)) /sqrt5;
        return (int)fn;
    }
    • Vous pouvez éviter la nécessité de calculer de deux exponentielles en utilisant le fait que |1 - phi|^n / sqrt(5) < 1/2 quand n est un entier non négatif.
    • Ne savais pas que l'ajustement ont toujours utilisé l'autre forme, mais c'est une belle optimisation
    • Rapprochement du résultat, la bonne solution consiste à la multiplication de matrices.
    InformationsquelleAutor JDunkerley
  7. 4

    Pour vraiment gros, cette fonction récursive œuvres. Il utilise les équations suivantes:

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

    Vous avez besoin d'une bibliothèque qui vous permet de travailler avec de grands entiers. J'utilise le BigInteger bibliothèque de https://mattmccutchen.net/bigint/.

    Commence par un tableau de nombres de fibonacci. Utiliser des bobards[0]=0, bobards[1]=1, bobards[2]=1, bobards[3]=2, bobards[4]=3, etc. Dans cet exemple, j'utilise un tableau de la première 501 (en partant de 0). Vous pouvez trouver les 500 premiers non nuls nombres de Fibonacci ici: http://home.hiwaay.net/~jalison/Fib500.html. Il prend un peu de retouche pour la mettre dans le bon format, mais ce n'est pas trop dur.

    Ensuite, vous pouvez trouver n'importe quel nombre de Fibonacci à l'aide de cette fonction (en 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);
}

    J'ai testé cela pour les 25 000 ème nombre de Fibonacci et la comme.

    • Oups, j'ai oublié de mentionner que "big2" est un BigUnsigned variable avec la valeur 2...
    • Ce code n'est pas très efficace. Imaginez que les bobards tableau[] est seulement la taille 10 et que vous appelez Fib(101). Fib(101) appels Fib(51) et Fib(50). Fib(51) appels Fib(26) et Fib(25). Fib(50) appels Fib(25) et Fib(24). Donc Fib(25) a été appelé deux fois, ce qui est un gaspillage. Même avec des bobards jusqu'à 500, vous aurez le même problème avec Fib(100000).
    InformationsquelleAutor user3137939
  8. 3

    Voici ma version récursive qui parcourt log(n) fois. Je pense que c'est plus facile à lire dans la forme récursive:

    def my_fib(x):
  if x < 2:
    return x
  else:
    return my_fib_helper(x)[0]

def my_fib_helper(x):
  if x == 1:
    return (1, 0)
  if x % 2 == 1:
    (p,q) = my_fib_helper(x-1)
    return (p+q,p)
  else:
    (p,q) = my_fib_helper(x/2)
    return (p*p+2*p*q,p*p+q*q)

    Cela fonctionne parce que vous pouvez calculer fib(n),fib(n-1) à l'aide de fib(n-1),fib(n-2) si n est impair, et si n est pair, vous pouvez calculer fib(n),fib(n-1) à l'aide de fib(n/2),fib(n/2-1).

    Le cas de base et l'étrange cas sont simples. Pour dériver le même cas, avec a,b,c consécutive de fibonacci valeurs (par exemple, 8,5,3) et de les écrire dans une matrice, avec a = b+c. Avis:

    [1 1] * [a b]  =  [a+b a]
[1 0]   [b c]     [a   b]

    À partir de cela, nous voyons qu'une matrice des trois premiers nombres de fibonacci, fois une matrice de trois mandats consécutifs de la suite de fibonacci, est égale à la prochaine. Donc, nous savons que:

          n
[1 1]   =  [fib(n+1) fib(n)  ]
[1 0]      [fib(n)   fib(n-1)]

    Donc:

          2n                        2
[1 1]    =  [fib(n+1) fib(n)  ]
[1 0]       [fib(n)   fib(n-1)]

    La simplification de la droite conduit à la même affaire.

    • Je tiens à souligner ici que vous voulez calculer F(2n) et F(2n+1) en fonction de F(n) et F(n-1). Vous n'indiquent pas ce que vous voulez faire.
    InformationsquelleAutor Eyal
  9. 1

    à l'aide de 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 George Dontas
  10. 1

    En dehors de réglage fin par des approches mathématiques, l'une des meilleures solution optimale (je crois) est à l'aide d'un dictionnaire afin d'éviter des calculs répétitifs.

    import time

_dict = {1:1, 2:1}

def F(n, _dict):
    if n in _dict.keys():
        return _dict[n]
    else:
        result = F(n-1, _dict) + F(n-2, _dict)
        _dict.update({n:result})
        return result

start = time.time()

for n in range(1,100000):
    result = F(n, _dict) 

finish = time.time()

print(str(finish - start))

    Nous commençons avec trivial dictionnaire (les deux premières valeurs de la suite de Fibonacci) et l'ajout constant de Fibonacci valeurs pour le dictionnaire.

    Il a fallu environ 0,7 secondes pour la première 100000 Fibonacci valeurs (Intel Xeon CPU E5-2680 @ 2.70 GHz, 16 GO de RAM, Windows 10 à 64 bits de l'OS)

    • C'est dans le temps linéaire si la question demande précisément comment atteindre sublinéaire temps (ce qui est possible en utilisant une sorte de forme fermée de la solution).
    InformationsquelleAutor bilalsamioguz
  11. 0

    voir diviser et conquérir de l'algorithme de ici

    Le lien a pseudocode pour les exponentielles de matrices mentionné dans les réponses à cette question.

    InformationsquelleAutor Chinmay Lokesh
  12. 0

    Point fixe de l'arithmétique est inexacte. Jason code C# donne une mauvaise réponse, pour n = 71 (308061521170130 au lieu de 308061521170129) et au-delà.

    Pour la réponse correcte, utiliser un calcul d'algèbre système. Sympy est une bibliothèque pour le langage Python. Il y a une console interactive à http://live.sympy.org/ . Copier et coller cette fonction

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

    Puis calculer

    >>> f(10)
55

>>> f(71)
308061521170129

    Vous pouvez essayer d'inspection phi.

    InformationsquelleAutor Colonel Panic
  13. 0

    Vous pouvez utiliser le bizarre carré rooty équation pour obtenir une réponse exacte. La raison en est que le $\sqrt(5)$ tombe à la fin, vous avez juste à garder la trace des coefficients avec votre propre multiplication format.

    def rootiply(a1,b1,a2,b2,c):
    ''' multipy a1+b1*sqrt(c) and a2+b2*sqrt(c)... return a,b'''
    return a1*a2 + b1*b2*c, a1*b2 + a2*b1

def rootipower(a,b,c,n):
    ''' raise a + b * sqrt(c) to the nth power... returns the new a,b and c of the result in the same format'''
    ar,br = 1,0
    while n != 0:
        if n%2:
            ar,br = rootiply(ar,br,a,b,c)
        a,b = rootiply(a,b,a,b,c)
        n /= 2
    return ar,br

def fib(k):
    ''' the kth fibonacci number'''
    a1,b1 = rootipower(1,1,5,k)
    a2,b2 = rootipower(1,-1,5,k)
    a = a1-a2
    b = b1-b2
    a,b = rootiply(0,1,a,b,5)
    # b should be 0!
    assert b == 0
    return a/2**k/5

if __name__ == "__main__":
    assert rootipower(1,2,3,3) == (37,30) # 1+2sqrt(3) **3 => 13 + 4sqrt(3) => 39 + 30sqrt(3)
    assert fib(10)==55
    InformationsquelleAutor Scott
  14. 0

    Voici un one-liner qui calcule F(n), en utilisant des entiers de taille O(n), O(log n) opérations arithmétiques:

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

    En utilisant des entiers de taille O(n) est raisonnable, étant donné que c'est comparable à la taille de la réponse.

    Pour comprendre cela, laissez-phi être le nombre d'or (la plus grande solution de x^2=x+1) et F(n) le n-ième nombre de Fibonacci, où F(0)=0, F(1)=F(2)=1

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

    Preuve par induction: phi^1 = 0 + 1*phi = F(0) + F(1)phi. Et si phi^n =
    F(n-1) + F(n)phi, puis 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. La seule étape délicate dans ce calcul est celui qui remplace phi^2 (1+phi), qui suit parce que phi est le nombre d'or.

    Également des nombres de la forme (a+b*phi), où a, b sont des entiers sont fermés en vertu de la multiplication.

    Preuve: (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.

    À l'aide de cette représentation, on peut calculer phi^n en O(log n) opérations sur entiers en utilisant l'exponentiation par la quadrature. Le résultat sera F(n-1)+F(n)phi, à partir de laquelle on peut lire le n-ième nombre de Fibonacci.

    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])

    Noter que la majorité de ce code est un standard de l'exponentiation par la quadrature de la fonction.

    Pour obtenir le one-liner qui commence cette réponse, on peut noter que représentant dmp par un assez grand nombre entier X, on peut effectuer (a+b*phi)(c+d*phi) comme l'entier de l'opération (a+bX)(c+dX) modulo (X^2-X-1). Puis le pow fonction peut être remplacé par le standard de Python pow fonction (qui comporte un troisième argument z qui calcule le résultat modulo z. Le X choisi est 2<<i.

    InformationsquelleAutor Paul Hankin