Expression du n-ième nombre de Fibonacci

acetonik
acetonik
dans Arithmétique
Bonsoir,


L'expression du $n^{ieme }$ nombre de Fibonacci $ u_n=u_{n-1}+u_{n-2} $ avec $u_0=0$ et $u_1=1$, est bien connue en utilisant le nombre d'or et son conjugué , mais peu intéressante pour programmer un calcul rapide et exact de $u_n$ pour $n$ assez grand.

Connaissez-vous une méthode simple pour démontrer que l'entier suivant est bien $u_n$ pour $ n \geq 2$
\[E(\dfrac{2^{n^2+n}}{2^{2n}-2^n-1} )\mod 2^{n-1}\]
$E$ désigne la partie entière (inférieure)

Cette expression me permettrait de montrer l'intérêt et l'efficacité d'un calcul sur les bits par décalage.
Par avance merci.
Cordialement

Réponses

  • soland
    soland
    L'arrondi de $\varphi^n/\sqrt{5}$, où $\varphi$ est le nombre d'or, est égal au $n$-ième nombre de Fibonacci.
  • GaBuZoMeu
    GaBuZoMeu
    Je dirais même plus : cet arrondi est égal au $n$-ème nombre de Fibonacci dès que $n\geq 1$
  • soland
    soland
    J'ai corrigé et nettoyé ma casserole.
  • acetonik
    acetonik
    Merci pour votre intérêt à la question.
    J'aurai dû préciser je souhaite un calcul (non récurrent) qui n'utilise que les entiers ou les fractions.
    Le fait d'utiliser $\dfrac{\varphi^n}{\sqrt{5}}$ conduit plus ou moins rapidement, à des calculs approchés pour lesquels l'arrondi ne correspond plus à $u_n $ , par exemple :
    -pour Maple à partir de $u_{32}=2178309$ , on a $\dfrac{\varphi^n}{\sqrt{5}}=2178309.6...$
    -pour Python à partir de $u_{71}=308061521170129$ , on a $\dfrac{\varphi^n}{\sqrt{5}}=308061521170129.7...$

    J'en renviens donc à ma question initiale concernant l'expression en puissances de $2$, qui permet de ne travailler que par décalage sur les bits.
  • GaBuZoMeu
    GaBuZoMeu
    Maple et Sage65014
    65016
  • JLT
    JLT
    Soit $F_n$ le $n$-ième nombre de Fibonacci, avec $F_0=0$ et $F_1=1$.

    On a $\dfrac{1}{1-X-X^2}=\sum_{n=0}^\infty F_{n+1}X^n$. Soit $x=2^n$. Notons
    $$A_n=\frac{2^{n^2+n}}{2^{2n}-2^n-1}=\frac{x^{n-1}}{1-\frac{1}{x}-\frac{1}{x^2}}=\sum_{k=0}^\infty F_{k+1}x^{n-1-k}.$$

    On en déduit que $E(A_n)=\sum_{k=0}^{n-1}F_{k+1}x^{n-1-k}$. Comme $x\equiv 0\pmod{2^{n-1}}$, on a $A_n\equiv F_n\pmod{2^{n-1}}$. D'autre part, on a aussi $F_n<2^{n-1}$ pour $n\geqslant 2$, d'où le résultat.
  • christophe c
    christophe c
    arrondi = partie entière?
    Aide les autres comme toi-même car ils sont toi, ils sont vraiment toi
  • GaBuZoMeu
    GaBuZoMeu
    Non, arrondi = l'entier le plus proche (et pour les $n+1/2$ avec $n$ entier, euh ... on arrondit à $n+1$ si $n\geq 0$ et à $n-1$ si $n<0$, enfin c'est comme ça que font les systèmes de calcul formel que j'utilise).
  • ev
    ev
    GaBuZ a écrit:
    et pour les \( n+1/2 \) avec \( n \) entier, on arrondit à \( n-1 \) si \( n<0 \),

    Sûr,sûr ?

    amicalement,

    e.v.
    Personne n'a raison contre un enfant qui pleure.


  • acetonik
    acetonik
    @JLT
    La réponse parfaite que je souhaitais !! ( une jolie idée au début)

    @ GBZM
    Je n'ai qu'une version assez ancienne de Maple qui refuse $round(((1+sqrt(5))/2)^{32}/sqrt(5))$
    mais accepte $evalf((1+sqrt(5))/2)^{32}/sqrt(5))$ et me donne bien $2178309.6$ dont l'arrondi n' est pas $u_{32}$.
    Sage donne la bonne réponse pour $u_{1000}$ , mais rien ne garantit que pour n assez grand le calcul soit encore exact ou au mieux refusé comme me l'a fait Maple , d'où l'intérêt de l'expression démontrée par JLT. La seule limite en Python pour cette expression étant la capacité mémoire ou le temps de calcul.

    @cc
    "arrondi entier" = "l'une des partie entière" ( inférieure ou supérieure) selon selon que la première décimale est strictement inférieure à 5 ou non.

    Merci à tous
  • GaBuZoMeu
    GaBuZoMeu
    @ ev : bon, $n$ si tu préfères.
  • bisam
    bisam
    @acetonik : Je doute que la complexité en temps soit améliorée par ce résultat. En effet, il faut que tu calcules une division entière d'un nombre ayant $n^2$ bits.
    Même si tu n'es pas obligé de le stocker puisque c'est une puissance de 2 et qu'une simple boucle permettra de faire la division, elle ne sera pas plus efficace que l'algorithme linéaire classique... et bien moins efficace que les algorithmes logarithmiques connus (utilisant les relations entre $F_{2n}$, $F_{2n+1}$ et $F_n$).

    Je me trompe peut-être... mais c'est à toi d'apporter la preuve de l'intérêt calculatoire de cette formule.
  • acetonik
    acetonik
    Ma priorité est de calculer avec des entiers et ne pas faire d'approximations pour que les calculs restent exacts pour de très grandes valeurs de n. Pour l'instant j'en suis là :

    (2 << (n*n+n-1)) // ((2 << (2*n-1)) - (2 << (n-1)) - 1) & ((2 << (n-1)) - 1)

    reste à améliorer, effectivement comparer avec ceci , ...mais j'ai ma réponse concernant l'arithmétique (par les séries génératrices ) et ne voudrait faire dévier ce fil vers l'informatique.

    Cordialement
  • abstract
    abstract
    Avec wolfram exemple
    round(goldenratio^n/sqrt5), for n=7
    https://goo.gl/8H1CJK
  • claude quitté
    claude quitté
    @acetonik
    Juste une petite remarque. Il y a une communauté dite du Calcul Formel dont le job est de réaliser en particulier des algorithmes efficaces pour le calcul de ceci ou cela. Dans ton histoire, on peut utiliser l'anneau quotient :
    $$
    \Z[x] := \Z[X] /\langle X^2-X -1\rangle
    $$
    Et calculer $x^n = F_n x + F_{n-1}$ de manière intelligente. Aucune approximation ici. Et la multiplication par $x$ est une fausse multiplication car $x(ax+b) = \cdots$. Et on dispose de deux algorithmes d'exponentation dichotomique dont les schémas récursifs sont les suivants ($r = 0, 1$):
    $$
    x^{2m + r} = (x^2)^m \times x^r, \qquad\qquad x^{2m+r} = (x^m)^2 \times x^r
    $$
    A gauche, ``schéma dit classique'', à droite schéma dit ``exponentiation dichotomique à la Horner''.

    Ces deux schémas (dérécursifés si l'on veut) ont même complexité en nombre d'opérations mais ne font pas du tout les mêmes multiplications. J'attache une page mais je ne sais pas si on y voit bien. On peut évidemment simuler l'anneau $\Z[x]$.

    Un jour, peut-être que tu pourras nous dire comment calculer $a, b, q$ avant la réduction modulo $2^{n-1}$. Bon courage.

     
    > Z := IntegerRing() ;
> ZX<X> := PolynomialRing(Z,1) ;la réduction 
> A<x> := ZX/Ideal(X^2 - X - 1) ;
> 
> n := Random(50,100) ;
> x^n ;
10610209857723*x + 6557470319842
> assert x^n eq Fibonacci(n)*x + Fibonacci(n-1) ;
> 
> // Vu sur le Forum
> a := 2^(n^2 + n) ;
> b := 2^(2*n) - 2^n - 1 ;
> a ;
1926557440885621868560031687917115836168560130839133852909299029236024329686495\
3451975783125609337202706891894055752829372779259049048849018567796016647978249\
4320336721435253706889685234460590136285591753701239489738876016223524153376135\
8778390143115771391072163514350524218848239879144597788987085672570081018844871\
4416395219199733290890214848429695386768627446124561793658458237854861580774810\
8317391200533587318136838731891886465813787316676069703916678941451890180158380\
5424685190177081981685291358284870430708241596199127313230841546546706481928713\
4740964819970177430629819576241173693240875467379586282755435136954232749745940\
4348903491513479147471062917896592692263621628656306058726913127184481214778420\
4041063033085269473812674258452411984860381453546708564026536074782076818962094\
7326395211890906209573342796395379503104183656613087082367802688872137179142212\
0994603935541913007943986233971523161003260282112919889978830555231125000590182\
7358162058286574426544078960438454720532993132542593854754210793558244114940000\
2864803102996889701723765653080462436614622355043934031552072410147967106052221\
0846915378913968656302538356756321633680393738679023305771111358708480559909561\
68400775171493725436036875734110868413039015782427458025778080382976
> b ;
340282366920938463444927863358058659839
> q := Quotrem(a,b) ; 
> q ;
5661643470739229049689979176175021370912689372133214039519001076679799070291971\
5144519297820311694218338272366377239120046349347083553774175186415225326011465\
5494405127281411083404620176184514108294378784087918417785198596982196150741856\
8524972347743403475244263623558362002739957568963725757264779973783150981438411\
4689786887320066936180642624644970678996786609737458960920663706177670685600490\
1150424092739102668270526100062352347394683114561181880490110702357203861674810\
0987008422416596043256772300647583929365586057492649876581929877393320634313670\
8368226997527800489756230725607390521863523076440893154195003438991805240487613\
5281274425070221347579807732664001149093423076038536997008561363682657732920775\
0403392472384234160708743506702760521006637960680146212714631249789486833985203\
3752740039534255558061486444229820549872033308835775090192408012482468255560666\
3078951538435839774143425629652289644227030924108218755268414948126592133057990\
6376512457088782813649329849799380988783615708233397788967831386788517293965809\
6138874546950413127537146961277703171304949198750289525611737578764441250391844\
9618151508753235977615999408115422843256075443103976709040385497222391944231637\
85971108499370061096790139067
> Fn := q mod 2^(n-1);                                                          
> assert Fn eq Fibonacci(n) ;
  • acetonik
    acetonik
    En relisant ce fil dans lequel je suis intervenu, et une pièce jointe, je croyais obtenir un calcul des $F_n$ plus rapide que par l'algorithme naïf (en calculant sur les bits).
    En réalité la complexité en $O(n^2)$ n'est pas compensée par un calcul sur les bits, comme le prévoyait Bisam (le serait-t-elle d'ailleurs en langage assembleur?).

    Pour le reste, il faut considérer que ce n'est pour moi qu'une distraction passagère.

    Cordialement
  • acetonik
    acetonik
    Le temps est maussade, je reprends ma distraction avec une nouvelle approche.
    $(u_n)$ étant la suite de Fibonacci, soit $F_n=[u_n, u_{n-1}]$ la suite des couples de Fibonacci associée
    Pour deux couples $F=[a,b]$ et $G=[c,d]$ quelconques , la loi * est définie par $F*G=[ac+bc+ad,ac+bd]$
    (* donne une bonne structure facile à deviner ,d'élément neutre $[0,1]$)
    On a alors pour tous les couples de Fibonacci $F_n * F_m =F_{m+n} $

    Le programme donne les couples $F_0$ à $F_{10}$ , puis les couples $F_{10.2^n}$ en quantité suffisante pour servir de base pour le calcul de tout F_N 
    ################ Debut du programme #######################
def multiplie (F1, F2):
    [a,b]=F1
    [c,d]=F2
    return [a*c+b*c+a*d,a*c+b*d]
#----------------------------------------------------------   
def puissance(L,nbr):
    T=[L]
    for i in range(1,nbr+1):
        L=multiplie(L,L)
        T.append(L)
    return T # T= L^(2^nbr)


####### programme principal - calcul de F(N) ############## 

N=int(input("rang de Fn n-eme nombre de Fibonacci : "))
N1=N//10 
N2=N%10

#=Ecriture de N/10 en base 2
Nc=str(bin(N1))
l1=list(Nc)
l1.reverse()
n=len(l1)-3 

#creation des couples F[0] Ã  F[10]
F=[[0,1],[1,0],[1,1]]
for k in range(2,10):
    M=multiplie(F[k-1],[1,1])
    F.append(M)

#creation des couples F[10*2^n]=R[n]
R=puissance(F[10],n)
#n=0-> F[10]=R[0]
#n=1-> F[20]=R[1]
#n=2-> F[40]=R[2]
#--------------
#n=15->F[327680]=R[15]
#n=16->F[655360]=R[16]
# etc ....


F=F[N2] ##initialisation (N2 est chiffre des unités de N)
# et calcul de F[N] avec la "base" des R[n] 
for k in range(0,n+1):
    if  l1[k]=='1':
        F=multiplie(F,R[k])
        
print(F[0])


################ Fin du programme ############################

    Pour $F_{1000000}$ le calcul est 100 fois plus rapide que par l'algorithme naïf ( moins de 4s sur vieux PC)
    Je ne sais si cette méthode est connue, elle est presque aussi rapide que celle de certains logiciels de calcul formel.
    (Maxima 5.31 refuse le calcul de $F_{1000000}$)

    Je ne suis pas plus intelligent , mais satisfait du résultat.

    Cordialement

    PS/ Désolé pour les réeditions je ne comprends pas pourquoi la fin du code passe en italique....
    PS2/ Eureka !! le l1 à la fin devient l1 et fait passer le texte en italique !!
    i est maintenant changé en k pour avoir un code affiché correctement...
Connectez-vous ou Inscrivez-vous pour répondre.

Bonjour!

Pour participer au forum, cliquer sur l'un des boutons :

Connexion S'inscrire

Catégories

In this Discussion

Qui est en ligne 29

BouzarCidrolinJLTJLapinMathurinMatricule_63biguine_equationjelobreuilnicolas.patroispozzar +19 Invités