title: Algorithme de multiplication de Booth
text: # 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.
  
  