Algorithme efficace pour calculer le

11

Le ème nombre de Fibonacci peut être calculé en temps linéaire en utilisant la récurrence suivante: $n$

def fib(n):
    i, j = 1, 1
    for k in {1...n-1}:
        i, j = j, i+j
    return i

Le ème nombre de Fibonacci peut également être calculé comme $n$ . Cependant, cela a des problèmes avec les problèmes d'arrondi pour mêmerelativement petit. Il y a probablement desmoyens de contourner cela,mais je préfère ne pas le faire. $\left[\varphi^n / \sqrt{5}\right]$ $n$

Existe-t-il un algorithme efficace (logarithmique dans la valeur ou mieux) pour calculer le ème nombre de Fibonacci qui ne repose pas sur l'arithmétique à virgule flottante? Supposons que les opérations entières ( , , , ) peuvent être effectuées en temps constant. $n$ $n$ $+$ $-$ $\times$ $/$

algorithms time-complexity recurrence-relation augurar
la source

5

À titre de suggestion, l'article de Wikipedia sur les nombres de Fibonacci a beaucoup de méthodes.

Pseudonyme le

cf. stackoverflow.com/questions/14661633/… et des liens à l'intérieur et autour.

Will Ness

14

Vous pouvez utiliser une alimentation matricielle et l'identité Dans votre modèle de calcul, il s'agit d'un algorithme si vous utilisez la quadrature répétée pour implémenter la mise sous tension.

{[\begin{matrix} 1 & 1 \\ 1 & 0 \end{matrix}]}^{n} = [\begin{matrix} F_{n + 1} & F_{n} \\ F_{n} & F_{n - 1} \end{matrix}] .

$\begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix}^n = \begin{bmatrix} F_{n+1} & F_n \\ F_n & F_{n-1} \end{bmatrix}.$

O (\log n)

$O(\log n)$

Yuval Filmus
la source

1

C'est un classique.

dfeuer

8

Vous pouvez également utiliser cette identité pour dériver les récurrences

et

.

F_{2 n - 1} = F_{n}^{2} + F_{n - 1}^{2}

$F_{2n-1} = F_n^2 + F_{n-1}^2$

F_{2 n} = F_{n}^{2} + 2 F_{n - 1} F_{n}

$F_{2n} = F_n^2 + 2F_{n-1}F_n$

août 2015

4

Vous pouvez lire cet article mathématique: Un algorithme rapide pour calculer de grands nombres de Fibonacci (Daisuke Takahashi): PDF .

Plus simple, j'ai implémenté plusieurs algorithmes de Fibonacci en C ++ (sans et avec GMP) et Python. Sources complètes sur Bitbucket. À partir de la page principale, vous pouvez également suivre des liens vers:

La documentation en ligne HTML C ++.
Un petit document mathématique: les nombres de Fibonacci - plusieurs relations pour implémenter de bons algorithmes

Les formules les plus utiles sont:

$F_{2n} = F^2_{n + 1} - F^2_{n - 1} = 2 F_n F_{n - 1} + F^2_n$
$F_{2n + 1} = F^2_{n + 1} + F^2_n$

Soyez prudent sur l'algorithme. Vous ne devez pas calculer plusieurs fois la même valeur. Un algorithme récursif simple (en Python):

def fibonacci_pair(n):
    """Return (F_{n-1}, F_n)"""
    if n != 0:
        f_k_1, f_k = fibonacci_pair(n//2)  # F_{k-1},F_k with k = n/2

        return ((f_k**2 + f_k_1**2,
                 ((f_k*f_k_1)*2) + f_k**2) if n & 1 == 0  # even
                else (((f_k*f_k_1)*2) + f_k**2,
                      (f_k + f_k_1)**2 + f_k**2))
    else:
        return (1, 0)

$O(\log n)$

Olivier Pirson
la source

2

Bienvenue en informatique . Pourriez-vous ajouter plus d'informations à votre réponse? Pour le moment, ce ne sont que deux liens, donc votre réponse n'aura plus de sens si ces liens meurent ou si les serveurs sur lesquels ils se trouvent ne sont pas disponibles. Les liens vers plus d'informations sont bien, mais les liens ici sont les seules informations. Veuillez également noter que la question concerne très certainement les algorithmes, pas les implémentations C ++. Les implémentations ont tendance à masquer les algorithmes derrière les détails spécifiques au langage.

David Richerby

David, le premier lien est un lien vers un article mathématique. Le titre Un algorithme rapide [...] répond à la question "Existe-t-il un algorithme efficace (logarithmique dans la valeur n ou mieux) [...]?" Le deuxième lien est un lien vers mes différentes implémentations, en C ++ et Python, et un petit document mathématique avec plusieurs formules.

Olivier Pirson

2

Non, le titre de l'article, qui contient votre réponse, ne répond à rien. Le texte de l'article, dont votre réponse ne contient presque aucun, semble qu'il répond probablement à la question. Mais Stack Exchange est un site de questions et réponses, pas une batterie de liens. (Et, non, je ne vous suggère pas de copier-coller l'article dans votre réponse. Mais un résumé est nécessaire.)

David Richerby

Si vous voulez un résumé, écrivez-le!

Olivier Pirson

0

$O(\log_2 n)$

Consultez le livre gratuit Matters Computational et le code pari / gp.

joro
la source

5

Mieux vaut résumer les idées au lieu de simplement publier des liens.

août 2015 à 16h29

Algorithme efficace pour calculer le

Réponses: