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

Question

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

Answer 1

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

M = [1 1] 
 [1 0] 

alors

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 de division et de conquête qui donne Mⁿ en O(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 nmême
 = M.Mn-1 si n est impair

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

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

Élever un la diagonale de la matrice de Λ pour la nième puissance est une simple question de la levée de chaque élément dans Λ à la nde la th, de sorte que cela donne un O(1) méthode de collecte de M à la nde la th de puissance. Cependant, les valeurs de Λ 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]

Pour trouver chaque λ, nous résolvons

 |M - λI| = 0

ce 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 de X₁ et X₂:

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

 M.X1 1 = λ1X1X1,1 + X1,2 = λ1X1,1X1,1 = λ1X1,2

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

Ces vecteurs donner U:

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

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

L'inversion de U à l'aide de

A = [ a b ]
 [ c d ]
=>
Un-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

Si la vérification générale détient.

Maintenant, nous avons tout ce dont nous avons besoin pour calculer Mⁿ_1,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 le calculer à 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 de manière efficace.

Answer 2

L' 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 le nème nombre de Fibonacci en O(log n) du 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);
}

Answer 3

Si vous souhaitez que 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 (phiⁿ/√5 + ¹/₂)

fib n ~= phiⁿ/√5

Combien de chiffres est - 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

il est O(n)

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

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.

Answer 4

L'un des exercices dans SICP est à propos de ce, qui a la solution décrite ici.

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

La fonction Fib(le comte)
 une ← 1
 b ← 0
 p ← 0
 q ← 1

 Alors que count > 0 Faire
 Si Même(le comte) , Puis
 p ← p2 + q2
 q ← 2pq + q2
 le comte ← compter ÷ 2
 D'autre
 une ← bq + aq + ap
 b ← bp + aq
 le comte ← count - 1
 Fin De Si
 Fin Tant Que

 De retour de b
Fin De La Fonction

Answer 5

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

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

ensuite, (M^n)[1, 2] va être égale à l' nème nombre de Fibonacci, si [] est un indice de la matrice et de l' ^ est exponentielles de matrices. Pour une taille fixe de la matrice, de l'élévation à la puissance d'un positif de l'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, l' nème nombre de Fibonacci croît de façon exponentielle avec l' 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: en Faisant la matrice exponentielle avec un eigendecomposition première est exactement équivalente à JDunkerly la solution ci-dessous. Les valeurs propres de cette matrice sont l' (1 + sqrt(5))/2 et (1 - sqrt(5))/2.