Algorithme de multiplication de Booth
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
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.