Algoritmo di Booth

L'algoritmo del prodotto di Booth, o semplicemente algoritmo di Booth, è un algoritmo per il calcolo del prodotto tra due numeri binari con segno, espressi nella notazione complemento a due. Fu inventato dal fisico Andrew Donald Booth nel 1951, originariamente allo scopo di velocizzare i calcoli necessari a una ricerca che Booth stava svolgendo nel settore della cristallografia, avendo a disposizione una calcolatrice lenta nelle somme ma veloce nello shift.

Procedimento

Siano m e r rispettivamente il moltiplicando e il moltiplicatore, e siano x e y le rispettive lunghezze in bit della codifica in complemento a due dei due numeri.

1. Determinare i valori di A, di S e il valore iniziale di P. Questi numeri devono essere codificati su x + y + 1 bit.
   1. A viene generato scrivendo sui bit più significativi (a sinistra) il valore di m in complemento a due. I rimanenti y + 1 bit vanno riempiti con zeri.
   2. S viene generato scrivendo sui bit più significativi il valore opposto di m in complemento a due. I rimanenti y +1 bit si riempiono con zeri.
   3. P viene generato riempiendo i primi (a sinistra) x bit con degli zeri, successivamente va inserito il valore di r in complemento a due, eventuali bit ancora liberi vanno settati a zero.
2. Osservare i due bit meno significativi (più a destra) di P
   1. Se sono "01", calcolare il valore di P + A, ignorando eventuali overflow.
   2. Se sono "10", calcolare il valore di P + S, ignorando eventuali overflow.
   3. Se sono "00" oppure "11", usare direttamente il valore di P.
3. Calcolare il nuovo valore di P eseguendo uno shift a destra del valore ottenuto nel punto precedente.
4. Ripetere i punti 2 e 3 per un numero di volte pari a y.
5. Eliminare il bit meno significativo (più a destra) da P, il valore ottenuto è il prodotto tra m e r.

Esempio

Troviamo m * r, con m = 3 e r = -4, la codifica di entrambi i valori può avvenire su 4 bit, quindi lavoreremo su 4 + 4 + 1 = 9 bit.

• A = 0011 0000 0
• S = 1101 0000 0
• P = 0000 1100 0
• Dobbiamo eseguire i punti 2 e 3 ciclicamente per quattro volte.

1. P = 0000 1100 0. Gli ultimi bit sono "00", si lavora direttamente su P.
   • P = 0000 0110 0. Shift a destra.
2. P = 0000 0110 0.Gli ultimi bit sono "00".
   • P = 0000 0011 0. Shift a destra.
3. P = 0000 0011 0. Gli ultimi bit sono "10".
   • P = 1101 0011 0. Calcolo P = P + S.
   • P = 1110 1001 1. Shift a destra.
4. P = 1110 1001 1. Gli ultimi bit sono "11".
   • P = 1111 0100 1. Shift a destra.

• Il prodotto è 1111 0100 (eliminando il bit più a destra), che in decimale è -12.