Algorithme de multiplication de Booth
# 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 = $111110100_2.$ 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) = $1000011100_2.$

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 : $-2^8$ pour un octet, $-2^{16}$ pour un mot de 16 bits etc. Dans ce cas, un signe négatif entraîne une soustraction initiale.

