transformation d'un produit d'entiers en somme d'entiers
Bon, encore une entrée sur Fibonacci (relation (I):F_i=F_{i-1}+F_{i-2}):
On travaille a priori dans les indices i positifs avec les conventions F_0=0 et F_1=1 mais on aura besoin de définir ce qui se passe du côté négatif grâce à la relation :
(N): F_{-i} = - (-1)^(i) F_i.
On montre que la représentation binaire d'un entier n>0 dans la base des F_i,i>0 est unique (modulo le fait que F_1=F_2 et sans tenir compte des 0 initiaux) dans la mesure où on impose que les coefficients de deux F_i consécutifs soient choisis dans {(0,0),(0,1),(1,0)}.
Exemple : 17 = 1+3+5+8 = 0.F_1 + 1.F_2 + 0.F_3 + 1.F_4 + 1.F_5 + 1.F_6 : mauvais choix car F_4 et F_5 sont consécutifs et le couple de coefficients correspondant est (1,1). On dira que ce découpage est non conforme (mais il a quand même une signification). On choisira alors :
17 = 1+3+13 = F_2+F_4+F_7 et on écrira 17=(0...01001010)Fib
Supposons alors 2 nombres n1=17=(1001010)Fib et n2=29=(10100000)Fib à multiplier.
On va utiliser, en plus des 4 relations vues précédemment, 3 relations (démontrables à partir de (I),(N) et des conventions):
I]
(D): i>1, 2 F_i = F_{i+1} + F_{i-2}
II]
on a aussi (G): F_i = 1 + sum( j = 1 , j = i-2 , F_j ) dont on déduit :
III]
(S): i>j>1, F_i - F_j = sum( k = j-1, k = i-2, F_k)
Comme n2 a moins de 1 que n1, on va cumuler dans c (initialement nul) les contributions successives de la multiplication de n1 par chacune des 2 composantes de n2 (une composante par 1 rencontré dans n2).
Il convient alors de considérer un nombre s (initialement nul) qui va cumuler tout ce qui est à soustraire.
1) contribution associée à F_8:
a) on écarte le premier 1 de n1:
le premier nombre est alors (on omet les "Fib") réduit à (0001010) et grâce à la relation 4 avec r=3 et i=8 on a directement : (F_2+F_4) F_8 = F_11 - F_5.
On stocke donc (10000000000) dans c et (00000010000) dans s.
b) on reprend le 1 écarté en a) et on réalise une transformation pour faire apparaître des "101" grâce aux relations (I) et (G):
(1000000) = (1)+(0011111) = (1)+(0100111) = (1)+(0101001) = (0101011)
c) on écarte les deux derniers 1 du nombre obtenu en b) et grâce à la relation 4 avec r=5 et i=8 on a directement (F_4+F_6) F_8 = F_13 - F_3.
On stocke donc (1000000000000) dans c et (0000000000100) dans s.
d) on reprend les deux 1 écartés en c) et grâce à la relation (D) on stocke directement
(0000011) . (10000000) = (100100000) dans c.
2) contribution associée à F_6:
a) on écarte le premier 1 de n1:
le premier nombre est alors réduit à (0001010) et grâce à la relation 4 avec r=3 et i=6 on a directement : (F_2+F_4) F_6 = F_9 - F_3.
On stocke donc (100000000) dans c et (000000100) dans s.
b) voir 1)b)
c) on écarte les deux derniers 1 du nombre obtenu en b) et grâce à la relation 4 avec r=5 et i=6 on a directement (F_4+F_6) F_6 = F_11 - F_1.
On stocke donc (10000000000) dans c et (00000000001) dans s.
d) on reprend les deux 1 écartés en c) et grâce à la relation (D) on stocke directement:
(0000011) . (100000) = (1001000) dans c.
3) Assemblage conforme du résultat:
le cumul de c est (1020201101000) et on peut le réduire à (10010100001000), celui de s est (00000010201) qu'on peut réduire à (00000100100).
En considérant les derniers chiffres de c et les derniers chiffres de s, on a grâce à la relation (S)
(1000)-(100)=(10) qui remplace donc (1000) et -(100) dans l'assemblage et on peut considérer que c'est sur (10010100000000) qu'on travaille maintenant.
On fait de même pour traiter le 1 qui reste dans s avec
(100000000)-(100000)=(001110000) avec un nombre résiduel valant (10010000000000) et le résultat est alors (10010000000000) +(001110000)+(10)=(10010001110010) qu'on peut réduire à (10010010010010) qui donne au final
17.29 = F_2 + F_5 + F_8 + F_11 + F_14 = 1+5+21+89+377=493
On travaille a priori dans les indices i positifs avec les conventions F_0=0 et F_1=1 mais on aura besoin de définir ce qui se passe du côté négatif grâce à la relation :
(N): F_{-i} = - (-1)^(i) F_i.
On montre que la représentation binaire d'un entier n>0 dans la base des F_i,i>0 est unique (modulo le fait que F_1=F_2 et sans tenir compte des 0 initiaux) dans la mesure où on impose que les coefficients de deux F_i consécutifs soient choisis dans {(0,0),(0,1),(1,0)}.
Exemple : 17 = 1+3+5+8 = 0.F_1 + 1.F_2 + 0.F_3 + 1.F_4 + 1.F_5 + 1.F_6 : mauvais choix car F_4 et F_5 sont consécutifs et le couple de coefficients correspondant est (1,1). On dira que ce découpage est non conforme (mais il a quand même une signification). On choisira alors :
17 = 1+3+13 = F_2+F_4+F_7 et on écrira 17=(0...01001010)Fib
Supposons alors 2 nombres n1=17=(1001010)Fib et n2=29=(10100000)Fib à multiplier.
On va utiliser, en plus des 4 relations vues précédemment, 3 relations (démontrables à partir de (I),(N) et des conventions):
I]
(D): i>1, 2 F_i = F_{i+1} + F_{i-2}
II]
on a aussi (G): F_i = 1 + sum( j = 1 , j = i-2 , F_j ) dont on déduit :
III]
(S): i>j>1, F_i - F_j = sum( k = j-1, k = i-2, F_k)
Comme n2 a moins de 1 que n1, on va cumuler dans c (initialement nul) les contributions successives de la multiplication de n1 par chacune des 2 composantes de n2 (une composante par 1 rencontré dans n2).
Il convient alors de considérer un nombre s (initialement nul) qui va cumuler tout ce qui est à soustraire.
1) contribution associée à F_8:
a) on écarte le premier 1 de n1:
le premier nombre est alors (on omet les "Fib") réduit à (0001010) et grâce à la relation 4 avec r=3 et i=8 on a directement : (F_2+F_4) F_8 = F_11 - F_5.
On stocke donc (10000000000) dans c et (00000010000) dans s.
b) on reprend le 1 écarté en a) et on réalise une transformation pour faire apparaître des "101" grâce aux relations (I) et (G):
(1000000) = (1)+(0011111) = (1)+(0100111) = (1)+(0101001) = (0101011)
c) on écarte les deux derniers 1 du nombre obtenu en b) et grâce à la relation 4 avec r=5 et i=8 on a directement (F_4+F_6) F_8 = F_13 - F_3.
On stocke donc (1000000000000) dans c et (0000000000100) dans s.
d) on reprend les deux 1 écartés en c) et grâce à la relation (D) on stocke directement
(0000011) . (10000000) = (100100000) dans c.
2) contribution associée à F_6:
a) on écarte le premier 1 de n1:
le premier nombre est alors réduit à (0001010) et grâce à la relation 4 avec r=3 et i=6 on a directement : (F_2+F_4) F_6 = F_9 - F_3.
On stocke donc (100000000) dans c et (000000100) dans s.
b) voir 1)b)
c) on écarte les deux derniers 1 du nombre obtenu en b) et grâce à la relation 4 avec r=5 et i=6 on a directement (F_4+F_6) F_6 = F_11 - F_1.
On stocke donc (10000000000) dans c et (00000000001) dans s.
d) on reprend les deux 1 écartés en c) et grâce à la relation (D) on stocke directement:
(0000011) . (100000) = (1001000) dans c.
3) Assemblage conforme du résultat:
le cumul de c est (1020201101000) et on peut le réduire à (10010100001000), celui de s est (00000010201) qu'on peut réduire à (00000100100).
En considérant les derniers chiffres de c et les derniers chiffres de s, on a grâce à la relation (S)
(1000)-(100)=(10) qui remplace donc (1000) et -(100) dans l'assemblage et on peut considérer que c'est sur (10010100000000) qu'on travaille maintenant.
On fait de même pour traiter le 1 qui reste dans s avec
(100000000)-(100000)=(001110000) avec un nombre résiduel valant (10010000000000) et le résultat est alors (10010000000000) +(001110000)+(10)=(10010001110010) qu'on peut réduire à (10010010010010) qui donne au final
17.29 = F_2 + F_5 + F_8 + F_11 + F_14 = 1+5+21+89+377=493
Publicité