Additions

6	Additions

Il existe certainement une foultitude d'algorithmes d'addition. Nous allons en voir deux, l'algorithme classique tel qu'il est enseigné à l'école élémentaire, et l'algorithme d'Avizienis, basé sur la représentation des entiers dans les systèmes d'Avizienis.

Le problème résolu par chacun des deux algorithmes est le suivant : obtenir la représentation en base b de la somme de deux entiers x et y, en utilisant leurs représentations en base b (dont nous supposerons qu'elles comportent chacune k+1 chiffres). Les opérations de bases, ou élémentaires, c'est-à-dire celles que l'on suppose connues du processeur qui exécutera l'algorithme, sont les suivantes :

comparaisons entre entiers,
addition de deux chiffres en base b, le résultat étant un entier écrit en base b (les fameuses tables d'addition),
soustraction de b.

6.1

Algorithme << classique >>

Soient donc à additionner deux entiers x et y, avec

x =

i=0

x_i.bⁱ ; y =

i=0

y_i.bⁱ

Tout le monde est censé connaître l'algorithme, qui consiste à ajouter les chiffres de même poids, des poids faibles vers les poids forts, en propageant éventuellement une << retenue >> vers le rang suivant lorsque la somme des deux chiffres dépasse la base de la représentation. Nous allons l'étudier en détail, d'abord pour le justifier, ensuite pour se familiariser avec une présentation que nous utiliserons dans les sections suivantes.

On définit les suites (r_i)_{i=0, ...,k+1} et (c_i)_{i=0, ...,k+1} (r pour retenue et c pour chiffre) par

r₀ = 0, et pour i Î {0, ...,k}, r_i+1 =

ì
í
î

0	si	x_i+y_i+r_i< b
1	si	x_i+y_i+r_i ³ b

(la première retenue est nulle, et la retenue au rang i+1 vaut 0 ou 1 selon que l'addition au rang i est inférieure ou égale à la base). Pour les chiffres : le chiffre de poids fort de la somme est égal à la dernière retenue, et les autres chiffres de la somme sont obtenus en ajoutant les chiffres correspondant des nombres x et y et la retenue, et en enlevant b si le total dépasse b. Plus mathématiquement : si 0 £ i £ k, c_i = x_i + y_i+r_i -b.r_i+1 et c_k+1=r_k+1. On a alors

x+y=s=

k+1

i=0

c_i.bⁱ (1)

Justifier cet algorithme va se faire en deux étapes : d'abord montrer que les c_i sont bien des chiffres en base b, c'est-à-dire que, pour tout i Î {0,...,k+1}, c_i Î {0,...,b-1}, enfin montrer que l'égalité (6.1) est vérifiée.

Commençons par montrer que pour tout i Î {0,...,k+1}, c_i Î {0,...,b-1} : tout d'abord, on a par définition c_k+1=r_k+1, ce qui montre que c_k+1Î {0,1}Í{0,...,b-1}. Soit maintenant i Î {0,...,k}. On doit montrer que c_i Î {0,...,b-1}, c'est-à-dire que 0£ c_i £ b-1. Deux cas se présentent, selon la valeur de r_i+1 :

r_i+1=0 : alors c_i = x_i + y_i+r_i, et donc, puisque r_i+1=0, c_i £ b-1. Par ailleurs, comme par hypothèse 0£ x_i, 0£ y_i et 0£ r_i, on a aussi 0 £ c_i, en additionnant ces 3 inégalités membre à membre.
r_i+1=1 : alors c_i = x_i + y_i+r_i -b. Si r_i+1=1, c'est que, par définition, x_i+y_i+r_i ³ b, et donc 0£ c_i. Par ailleurs, on a x_i£ b-1, y_i£ b-1 et r_i£ 1, donc

c_i = x_i + y_i + r_i - b (par définition de c_i)

£ b-1 + b-1 + 1 - b (en utilisant les majorations ci-dessus)

= b-1

Montrons maintenant l'égalité (6.1) :

k+1

i=0

c_i.bⁱ (par définition)

r_k+1.b^k+1+

i=0

c_i.bⁱ (par définition de c_k+1)

r_k+1.b^k+1+

i=0

(x_i + y_i+r_i -b.r_i+1).bⁱ (par définition de c_i)

i=0

x_i.bⁱ+

i=0

y_i.bⁱ+r_k+1.b^k+1 +

i=0

r_i.bⁱ -

i=0

r_i+1.bⁱ⁺¹

x+y+

k+1

i=1

r_i.bⁱ-

k+1

i=1

r_i.bⁱ (car r₀=0)

x+y

Nous allons maintenant nous intéresser au coût de cet algorithme, c'est-à-dire au nombre d'opérations élémentaires à exécuter pour additionner deux entiers de k+1 chiffres en base b.

Commençons par le calcul des retenues : le calcul de r₀ ne nous coûte rien, et, d'après la définition, le calcul de r_i+1, pour iÎ{0,...,k}, nous coûte deux additions de chiffres en base b plus un test, c'est-à-dire 3 opérations élémentaires. En tout, le calcul de toutes les retenues prend 3(k+1) opérations élémentaires.

En ce qui concerne les chiffres : le calcul de c_k+1 ne nous coûte rien (puisqu'il est égal à r_k+1, déjà calculé). Pour i Î {0,...,k}, on n'a, au pire, qu'une seule soustraction, puisque la somme x_i + y_i+r_i a déjà été calculée pour r_i+1. En tout, le calcul de tous les chiffres nous coûte k+1 opérations, au pire. Résumons :

Théorème 6.1 L'algorithme d'addition classique effectue au plus 4k opérations élémentaires pour additionner deux entiers de k chiffres.

6.2

Algorithme d'Avizienis

La représentation d'Avizienis permet d'utiliser un algorithme d'addition très rapide, puisqu'il peut être exécuté en parallèle sur les chiffres des opérandes. Le temps pris pour additionner deux nombres ne dépend donc pas de leurs tailles, il est constant. C'est cette propriété qui rend cette représentation intéressante, et effectivement utilisée dans certains coprocesseurs dits <<mathématiques>>.

Soit b>1 la base de la représentation,

{-a, ..., 0, ..., a}

l'ensemble des chiffres, avec a£ b-1 et b+1£ 2.a. On veut additionner x et y, avec

x =

i=0

x_i.bⁱ ; y =

i=0

y_i.bⁱ

On définit les suites (r_i)_{i=0, ...,k+1} et (c_i)_{i=0, ...,k+1} (r pour retenue et c pour chiffre) par

r₀ = 0, et pour i Î {0, ...,k}, r_i+1 =

ì
ï
í
ï
î

x_i+y_i < -a+1

-a+1£ x_i+y_i £ a-1

x_i+y_i > a-1

Pour les chiffres : si 0 £ i £ k, c_i = x_i + y_i -b.r_i+1 et c_k+1=0. On définit enfin la suite (s_i)_{i=0, ...,k+1} (avec s pour somme) par s_i = c_i+r_i. On a alors (la preuve est dans le théorème ci-dessous)

x+y=s=

k+1

i=0

s_i.bⁱ

Justifions au passage l'allégation du début de la section, selon laquelle on peut calculer en parallèle la somme x+y : on a

s_i=c_i+r_i=x_i+y_i-b.r_i+1+r_i

et r_i est déterminé par les valeurs de x_i-1 et de y_i-1. Donc, pour calculer s_i, il suffit de connaître x_i, y_i, x_i-1 et y_i-1.

Exemple et disposition pratique des calculs : posons b=10, a=9, x=397, y=418 et donc, puisqu'il y a 3 chiffres, k=2. L'addition s'écrit comme suit :

Indice

x_i

y_i

r_i

c_i

s_i

soit x+y=195. Vérifions : x=397=300-97=203, y=418=-400+10-8=-398 et x+y=203-398=-195. Sur cet exemple, le résultat est correct...On a en fait le résultat suivant :

Théorème 6.2 Avec les notations précédentes :

" i Î {0,...,k+1}, s_i Î {-a,...,a};
s=å_i=0^k+1 s_i.bⁱ=x+y

Preuve :

On a c_k+1=0 par définition, et r_k+1 Î {-1,0,1} donc s_k+1 Î {-1,0,1} Í {-a,...,a}; pour i Î {0,...,k}, s_i=c_i+r_i avec r_i Î {-1,0,1} : il suffit donc de montrer que c_i Î {-a+1,...,a-1}, c'est-à-dire que -a+1£ c_i£ a-1. Il y a trois possibilités, selon la valeur de r_i+1 :
1. r_i+1=1 : montrons tout d'abord que c_i£ a-1. Si r_i+1=1, c'est que, par définition de r_i+1, x_i+y_i< -a+1, d'où l'on déduit c_i=x_i+y_i+b < -a+1+b. Comme, par hypothèse, b+1£ 2a, on a -a+1+b £ -a+2a=a, et par transitivité, c_i < a c'est-à-dire c_i £ a-1.
  
  Montrons maintenant que -a+1 £ c_i. Les assertions -a £ x_i, -a£ y_i et c_i=x_i+y_i+b entraînent l'inégalité -2a+b £ c_i. Comme a £ b - 1, on a aussi a+1 £ b, et on peut minorer la quantité -2a+b par -2a+a+1=-a+1, ce qui implique par transitivité que -a+1£ c_i.
2. r_i+1= 0 : c'est que, par définition de r_i+1, -a+1£ x_i+y_i£ a-1. Le résultat découle de ce que, par définition, c_i=x_i+y_i-b.r_i+1, et de l'hypothèse r_i+1= 0.
3. r_i+1= 1 : la preuve est similaire au cas où r_i+1=1, elle est donc laissée en exercice au lecteur.

k+1

i=0

s_i.bⁱ

k+1

i=0

(c_i+r_i).bⁱ par définition de s_i

k+1

i=0

c_i.bⁱ +

k+1

i=0

r_i.bⁱ

i=0

c_i.bⁱ +

k+1

i=1

r_i.bⁱ car c_k+1=0 et r₀=0

i=0

(x_i+y_i-b.r_i+1).bⁱ +

k+1

i=1

r_i.bⁱ par définition de c_i

i=0

x_i.bⁱ +

i=0

y_i.bⁱ -

i=0

r_i+1.bⁱ⁺¹ +

k+1

i=1

r_i.bⁱ

x+y -

k+1

i=1

r_i.bⁱ+

k+1

i=1

r_i.bⁱ

x+y

Exercices de la partie 6

Programmer l'algorithme classique d'addition avec un tableur.
Effectuer les additions suivantes (b désigne la base, a désigne le plus grand chiffre positif) :
- b=10,a=9 : 2541 + 9878
- b=10,a=6 : 2541 + 5665
- b=10,a=9 : 2541 + 5665
- b=10,a=7 : 1643 + 6542
- b=4,a=3 : 23313 + 3203
- b=16,a=9 : 6879 + 8658
- b=16,a=F : 6879 + 8658
Calculer le coût, en nombre d'opérations élémentaires, de l'algorithme d'Avizienis.
Programmer l'algorithme d'Avizienis avec un tableur.
Donner un algorithme d'addition pour la << base >> de Fibonacci.
Donner un algorithme d'addition pour la base -2.

c_i	=	x_i	+	y_i	+	r_i	-	b	(par définition de c_i)
	£	b-1	+	b-1	+	1	-	b	(en utilisant les majorations ci-dessus)
	=	b-1