transformation d'un produit d'entiers en somme d'entiers

Publié le par jö

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
 

Publié dans mathblog

Pour être informé des derniers articles, inscrivez vous :

Commenter cet article