---

7 Multiplications

Pour la multiplication, il existe aussi de multiples algorithmes. Nous allons en voir deux, l'algorithme classique enseigné à l'école élémentaire, et un algorithme dont l'origine, lointaine, est controversée : certains prétendent qu'il nous vient de l'antiquité égyptienne, d'autres prétendent qu'il a été inventé (ré-inventé ?) et utilisé dans les grandes plaines russes (ces deux explications ne sont pas contradictoires : l'algorithme a pu être découvert une première fois dans l'antiquité, oublié, puis retrouvé).

L'<< avantage >> du deuxième algorithme sur le premier est qu'il nécessite très peu de connaissances arithmétiques pour être exécuté : savoir additionner deux nombres, multiplier par deux (ce qui revient à une addition), diviser par deux, savoir reconnaître un nombre pair. Ces deux dernières compétences ne semblent pas très difficiles à acquérir, surtout quand la base de représentation des nombres utilisée est paire, ce qui, à ma connaissance, a toujours été le cas dans l'histoire.

Le cadre est le même que pour l'addition : on a deux nombres x et y de k+1 chiffres écrits en base b, et on cherche leur produit, écrit lui aussi en base b. Les opérations de bases ne sont pas les mêmes pour les deux algorithmes, nous les préciserons dans chaque cas.

7.1 L'algorithme << classique >>

Les opérations de bases sont ici

• la multiplication de deux chiffres en base b, le résultat étant un entier écrit en base b (ce qu'on appelle les tables de multiplication),
• l'addition de deux entiers,
• la division euclidienne par b d'un nombre écrit en base b,
• et la multiplication par b^k (pour k³ 0), ce qu'on appelle le décalage arithmétique.

Soient donc deux entiers x et y écrits en base b à multiplier, avec

x =

k å i=0

xi.bi  ,     y =

k å i=0

yi.bi

On peut écrire

x.y = x.

æ ç ç è

k å i=0

yi.bi

ö ÷ ÷ ø

=

k å i=0

x.yi.bi

et le problème de multiplier x et y revient à celui de multiplier un entier par un chiffre en base b, puisque, par hypothèse, nous savons additionner deux entiers écrits en base b, et multiplier par bⁱ.

Nous allons donc résoudre le problème suivant : étant donnés un nombre, x, de k+1 chiffres en base b, et un chiffre, f, de la base b, donner la représentation en base b de leur produit. À cet effet, on définit, comme d'habitude, deux suites, (r_i)_i=0,...,k+1 et (c_i)_i=0,...,k+1 (r pour retenue et c pour chiffre), de la façon suivante :

r0	=	0	et, pour  iÎ {0,...,k},	ri+1	=	(xi.f+ri)div b
ck+1	=	rk+1	et, pour iÎ {0,...,k},	ci	=	xi.f+ri-b.ri+1

On a alors (les preuves sont laissées en exercice)

	" iÎ{0,...,k+1},	ci	Î{0,...,b-1}	(2)
	x.f	=	k+1 å i=0 ci.bi	(3)

7.2 La multiplication des paysans russes (TD)

Le cadre est le même que précédemment : soient à multiplier deux entiers x et y, écrits en base b. Les opérations de bases sont ici

• additionner deux entiers;
• multiplier par 2;
• diviser par 2 (en fait trouver le quotient de la division euclidienne par 2);
• déterminer si un entier est pair.

On définit les suites (x_i)_{i ³0}, (y_i)_{i ³0} et (z_i)_{i ³0} comme suit :

ì ï í ï î x0 = x xn+1= ê ê ê ë xn 2 ú ú ú û

ì í î y0 = y yn+1=2.yn

ì í î z0 = 0 zn+1= é ë zn+yn  si  xn  est impair  zn  sinon

1. Faire tourner l'algorithme avec x=13 et y=7. Que constatez-vous sur la suite (x_i)_{i ³0} ? Et sur la suite (z_i)_{i ³0} ?
   
   
2. Montrer que la suite (x_i)_{i ³0} est stationnaire à partir d'un certain rang (noté n₀ dans la suite). Quelle est sa limite ? Montrer que z_n0=x× y (indication : considérer l'écriture de x en base 2).
   
   
3. Effectuer, en utilisant cet algorithme, les opérations suivantes :
   
   153 x 26 52 x 74 1542 x 43

Exercices de la partie 7

1. Montrer que la multiplication d'un entier de k chiffres (en base b) par un chiffre de la base b produit un entier ayant au plus k+1 chiffres en base b.
2. Prouver l'algorithme classique de multiplication.
3. Combien d'opérations élémentaires l'algorithme classique effectue-t-il pour multiplier des entiers de k chiffres ?
4. Programmer cet algorithme avec un tableur.
5. (Problème issu de Jeux & Stratégies, 43, Février-Mars 1987) Trouver le chiffre désigné par un << ? >> dans l'opération ci-dessous, effectuée en base 10 (aucun nombre ne commence par 0) :

   	.	.	.
   ×		7	.
   .	.	1	.
   8	.	.
   .	.	.	?

6. Combien d'opérations élémentaires l'algorithme des paysans russes effectue-t-il pour multiplier des entiers de k chiffres ?
7. Programmer cet algorithme avec un tableur.
8. Comparer les deux algorithmes, en nombre d'opérations élémentaires. Examiner en particulier le cas où b=2.

---