Algorithme de multiplication de Booth
Cet article est une ébauche concernant l’informatique.
Vous pouvez partager vos connaissances en l’améliorant (comment ?) selon les recommandations des projets correspondants.
L'algorithme de Booth a pour but de multiplier deux nombres binaires signés représentés en complément à deux, en supposant les opérations de décalage nettement moins onéreuses que les additions/soustractions.
Cet algorithme a été inventé par Andrew Booth en 1950 alors qu'il effectuait des recherches en cristallographie.
Principe[modifier | modifier le code]
Soit à calculer 500×A ; 500 = 256+128+64+32+16+4 = 1111101002 . Mais 1 = 2-1 ; 3 = 4-1; 7=8-1; 127 = 128-1 etc. On peut donc remplacer un train d'additions binaires par une addition de tête et une soustraction de queue. Précisément, l'algorithme de Booth traite 500 comme (512 - 16) + (8 - 4) = 10000111002.
Cela revient à utiliser une transcription simplifiée du multiplicateur dans un système binaire symétrique utilisant les chiffres signés ( 1, 0, 1) ; le but est de multiplier les zéros (non-action) ; 1 commandant une addition convenablement cadrée du multiplicande, 1 = -1 celle de son opposé. Soit ici 4 opérations au lieu de 6.
Pour un multiplicande signé en complément à deux, le signe s'interprète comme l'opposé de la puissance de 2, poids du bit le plus significatif : -28 pour un octet, -216 pour un mot de 16 bits etc. Dans ce cas, un signe négatif entraîne une soustraction initiale.
Voir aussi[modifier | modifier le code]
Articles connexes[modifier | modifier le code]
Références[modifier | modifier le code]
- Andrew D. Booth. A signed binary multiplication technique. The Quarterly Journal of Mechanics and Applied Mathematics, Volume IV, Pt. 2, 1951 [1]
