Système de numération d'Avizienis

L'algorithme d'addition d'Avizienis sans propagation de retenue[3] - [1] - [5] - [6] suppose une base ${\displaystyle b>2}$ et ${\displaystyle 2a+1}$ chiffres ${\displaystyle {\bar {a}},\ldots ,a}$, avec ${\displaystyle b/2<a<b}$[7]. La condition ${\displaystyle b/2<a}$ est plus forte que la relation ${\displaystyle b/2-1<a}$, qui assure que tout entier est représentable, et garantit l'absence de propagation de retenue. La deuxième condition, à savoir ${\displaystyle a<b}$, assure que les chiffres sont plus petits en valeur absolue que la base.

Étant donné deux entiers

${\displaystyle x=x_{n-1}\cdots x_{0}}$ et ${\displaystyle y=y_{n-1}\cdots y_{0}}$

écrits sur ${\displaystyle n}$ chiffres dans cette base, on cherche à calculer dans cette base

${\displaystyle z=z_{n}\cdots z_{0}}$

où

${\displaystyle z=x+y}$

Pour cela, pour ${\displaystyle i=0,\ldots ,n-1}$, on calcule la retenue qui est prise comme un chiffre prenant deux valeurs : ${\displaystyle 1}$ et ${\displaystyle {\bar {1}}}$.

${\displaystyle t_{i+1}={\begin{cases}{\bar {1}}&{\text{si }}\ x_{i}+y_{i}\leq -a,\\0&{\text{si }}\ {-a}<x_{i}+y_{i}<a,\\1&{\text{si }}\ x_{i}+y_{i}\geq a.\end{cases}}}$

et on pose :

${\displaystyle w_{i}=x_{i}+y_{i}-bt_{i+1}}$.

On pose également :

${\displaystyle w_{n}=t_{0}=0}$.

Les calculs de retenues ${\displaystyle t_{i}}$ peuvent se faire en parallèle; en d'autres termes, il n'y a pas d'ordre à respecter dans leur évaluation. On a enfin, pour ${\displaystyle i=0,\ldots ,n}$,

${\displaystyle z_{i}=w_{i}+t_{i}}$.

On prend la base ${\displaystyle b=4}$. La condition ${\displaystyle b/2<a<b}$ s'écrit ici ${\displaystyle 2<a<4}$, et on prend donc ${\displaystyle a=3}$. Les chiffres autorisés sont ${\displaystyle {\bar {3}},{\bar {2}},{\bar {1}},0,1,2,3}$[8] - [5]. Les nombres à additionner sont à ${\displaystyle n=5}$ chiffres

${\displaystyle x=(-697)_{10}={\bar {3}}102{\bar {1}}}$ et ${\displaystyle y=(498)_{10}=20{\bar {1}}1{\bar {2}}}$

Les calculs sont regroupés dans le tableau que voici

${\displaystyle i}$	5	4	3	2	1	0
${\displaystyle x_{i}}$		${\displaystyle {\bar {3}}}$	${\displaystyle 1}$	${\displaystyle 0}$	${\displaystyle 2}$	${\displaystyle {\bar {1}}}$
${\displaystyle y_{i}}$		${\displaystyle 2}$	${\displaystyle 0}$	${\displaystyle {\bar {1}}}$	${\displaystyle 1}$	${\displaystyle {\bar {2}}}$
${\displaystyle x_{i}+y_{i}}$		${\displaystyle {\bar {1}}}$	${\displaystyle 1}$	${\displaystyle {\bar {1}}}$	${\displaystyle 3}$	${\displaystyle {\bar {3}}}$
${\displaystyle t_{i}}$	${\displaystyle 0}$	${\displaystyle 0}$	${\displaystyle 0}$	${\displaystyle 1}$	${\displaystyle {\bar {1}}}$	${\displaystyle 0}$
${\displaystyle w_{i}}$	${\displaystyle 0}$	${\displaystyle {\bar {1}}}$	${\displaystyle 1}$	${\displaystyle {\bar {1}}}$	${\displaystyle {\bar {1}}}$	${\displaystyle 1}$
${\displaystyle z_{i}}$	${\displaystyle 0}$	${\displaystyle {\bar {1}}}$	${\displaystyle 1}$	${\displaystyle 0}$	${\displaystyle {\bar {2}}}$	${\displaystyle 1}$

On obtient bien: ${\displaystyle {\bar {1}}10{\bar {2}}1=(-199)_{10}=(-697)_{10}+(498)_{10}}$.

On a

${\displaystyle z_{i}=w_{i}+t_{i}=x_{i}+y_{i}+t_{i}-bt_{i+1}}$.

À chaque position ${\displaystyle i}$, le chiffre calculé est la somme des chiffres ${\displaystyle x_{i}}$ et ${\displaystyle y_{i}}$, plus la retenue ${\displaystyle t_{i}}$ de la position précédente; si la somme de ${\displaystyle x_{i}}$ et ${\displaystyle y_{i}}$ dépasse les bornes autorisées, on en soustrait ou ajoute la base, pour rentrer dans les bornes permises. Ce qui est particulier dans cet algorithme, c'est que la retenue ${\displaystyle t_{i+1}}$ ne dépend pas de la retenue précédente ${\displaystyle t_{i}}$. Dans l'addition classique avec retenue, on fait la même opération, mais dans le cas où la somme des deux chiffres ${\displaystyle x_{i}}$ et ${\displaystyle y_{i}}$ et de la retenue ${\displaystyle t_{i}}$ dépasse la base, il faut la reporter, conduisant dans le cas classique, à calculer la valeur de la retenue précédente avant celle de la retenue courante, d'où une séquentialisation des calculs. Ici, le test laisse assez de marge pour pouvoir absorber la retenue ${\displaystyle t_{i}}$, puisque ${\displaystyle -a<w_{i}<a}$. Les calculs de retenues peuvent donc se faire en parallèle. Le seul ordonnancement est la nécessité d'avoir calculé la retenue courante et la retenue précédente avant de calculer chaque chiffre de la somme.

Pour être précis, il faut d'abord vérifier que les chiffres ${\displaystyle z_{i}}$ sont bien compris dans l'intervalle de ${\displaystyle -a}$ à ${\displaystyle a}$. Pour cela[9], on part de

${\displaystyle z_{i}=w_{i}+t_{i}=x_{i}+y_{i}+t_{i}-bt_{i+1}}$.

Si ${\displaystyle -a<x_{i}+y_{i}<a}$, alors ${\displaystyle t_{i+1}=0}$, et comme ${\displaystyle t_{i}\in \{0,{\bar {1}},1\}}$, on a ${\displaystyle -a\leq x_{i}+y_{i}\leq a}$. Si au contraire ${\displaystyle x_{i}+y_{i}\geq a}$ (par exemple), alors ${\displaystyle t_{i+1}=1}$ et donc ${\displaystyle z_{i}=x_{i}+y_{i}+t_{i}-b\leq 2a-b+1\leq a}$, et aussi${\displaystyle z_{i}\geq a-b>-a}$.

Il faut ensuite vérifier que le nombre ${\displaystyle z}$ est bien égal à ${\displaystyle x+y}$. Pour cela, en se souvenant que ${\displaystyle t_{0}=0}$, on calcule

${\displaystyle {\begin{aligned}\sum _{i=0}^{n}z_{i}b^{i}&=\sum _{i=0}^{n}(w_{i}+t_{i})b^{i}=\sum _{i=0}^{n-1}(x_{i}+y_{i}-bt_{i+1}+t_{i})b^{i}+t_{n}b^{n}\\&=\sum _{i=0}^{n-1}x_{i}b^{i}+\sum _{i=0}^{n-1}y_{i}b^{i}-\sum _{i=0}^{n-1}t_{i+1}b^{i+1}+\sum _{i=1}^{n-1}t_{i}b^{i}+t_{n}b^{n}\\&=x+y\end{aligned}}}$.

Les systèmes de numération redondants ont plusieurs applications[1] : le codage de multiplieurs, les quotients dans les opérations de division ou d'opérations qui s'y rattachent, l'arithmétique en ligne. Les additions redondantes sont couramment employés dans les opérateurs de multiplication et de division (même si les données sont présentées, en entrée et en sortie, dans un système non redondant, les calculs internes sont réalisés dans un système redondant). Par exemple, la plupart des multiplieurs utilisent, au moins implicitement, un système de numération à redondant. Un processeur particulier utilisait même deux systèmes redondants différents : les itérations dans les divisions sont réalisées dans une notation à retenues conservées, et le quotient est d'abord calculé en base 4 avec des chiffres entre −2 et 2 avant d'être converti dans la notation binaire usuelle.

Guillaume Revy[5] présente une extension de la notation qu'il appelle encore la notation d'Avizienis. Au lieu de prendre, pour une base ${\displaystyle b}$, les chiffres de ${\displaystyle -a}$ à ${\displaystyle a}$, il prend les chiffres d'un autre intervalle, formé de ${\displaystyle q+1}$ chiffres, allant de ${\displaystyle \omega }$ à ${\displaystyle \omega +q}$. Le cas classique s'obtient pour ${\displaystyle \omega =-a}$ et ${\displaystyle q=2a}$. On peut distinguer trois cas :

• si ${\displaystyle q+1<b}$, il n'y a pas assez de chiffres pour représenter tous les nombres ;
• si ${\displaystyle q+1=b}$, il y a exactement le nombre de chiffres nécessaire pour représenter les nombres et ils ont une représentation unique ; c'est le cas par exemple des chiffres ${\displaystyle {\bar {1}},0,1}$ en base 3, appelée « notation ternaire équilibrée »[10];
• si ${\displaystyle q+1>b}$, la représentation est redondante.

La méthode d'Avizienis nécessite une base plus grande que 2. Pour la base ${\displaystyle b=2}$, deux méthodes d'addition en parallèle ont été développées, appelée en anglais « carry save » et « borrow save »; la première est traduite par addition à retenues conservées, la deuxième par addition à retenues conservées signées. On appelle la première aussi méthode de Chow et Robertson d'après leurs inventeurs qui l'ont décrite en 1978[1]. Les chiffres sont composés par des couples ${\displaystyle (c,s)}$, dont la valeur est ${\displaystyle c+s}$. Ainsi, en base 2, l'entier ${\displaystyle x=2}$ a les deux représentations ${\displaystyle (1,1)}$ et ${\displaystyle (0,1)(0,0)}$. La valeur de la représentation

${\displaystyle (c_{n-1},s_{n-1})\cdots (c_{0},s_{0})}$

est

${\displaystyle \sum _{i=0}^{n-1}(c_{i}+s_{i})2^{i}}$.

Les méthodes à retenues conservées s'étendent à d'autres bases.

• Système de numération
• Algirdas Antanas Avižienis
• Notation positionnelle

L'article original d'Avizienis, difficile à trouver :

• Algirdas Avizienis, « Signed-Digit number representations for fast parallel arithmetic », IRE Transactions on Electronic Computers, vol. EC-10, n^o 3,‎ septembre 1961, p. 389 - 400 (ISSN 0367-9950, DOI 10.1109/TEC.1961.5219227).

Exposés :

• Bruno Pettazoni, Seize problèmes d'informatique, Springer, coll. « Scopos » (n^o 8), 2001, 226 p. (ISBN 3-540-67387-3, présentation en ligne), « Problème 14, deuxième partie : Numération d'Avizienis Numération d'Avizienis. Énoncé p. 166, corrigé p. 173-174 », p. 166 (énonce) et 173-174 (corrigé).
• (en) Jean-Michel Muller, Elementary Functions : Algorithms and Implementation, Boston, Birkhäuser, 2005, 2^e éd., 265 p. (ISBN 0-8176-4372-9, présentation en ligne), « 2.2. Redundant number systems », p. 19-22.

Exposé didactique :

• Guillaume Revy, « Systèmes de représentation des nombres : Les nombres entiers », Licence 2 Sciences, Technologies, Santé, 2010/2011 (consulté le 2 août 2014), p. 24 - 34 ter.

Autre mention :

• (en) Christiane Frougny, Edita Pelantová et Milena Svobodová, « Parallel addition in non-standard numeration systems », sur Université Perpignan, 4^e Rencontres Arithmétique de l'Informatique Mathématique, 7 au 10 février 2011 (consulté le 2 août 2014).

Knuth a un long paragraphe sur les notations positionnelles :

• (en) Donald E. Knuth, The Art of Computer Programming, vol. 2 : Seminumerical algorithms, Reading (Mass.), Addison-Wesley, 1997, 3^e éd., 762 p. (ISBN 0-201-89684-2, présentation en ligne)