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
[modifica | modifica wikitesto]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.
- Determinare i valori di A, di S e il valore iniziale di P. Questi numeri devono essere codificati su x + y + 1 bit.
- 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.
- 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.
- 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.
- Osservare i due bit meno significativi (più a destra) di P
- Se sono "01", calcolare il valore di P + A, ignorando eventuali overflow.
- Se sono "10", calcolare il valore di P + S, ignorando eventuali overflow.
- Se sono "00" oppure "11", usare direttamente il valore di P.
- Calcolare il nuovo valore di P eseguendo uno shift a destra del valore ottenuto nel punto precedente.
- Ripetere i punti 2 e 3 per un numero di volte pari a y.
- Eliminare il bit meno significativo (più a destra) da P, il valore ottenuto è il prodotto tra m e r.
Esempio
[modifica | modifica wikitesto]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.
- P = 0000 1100 0. Gli ultimi bit sono "00", si lavora direttamente su P.
- P = 0000 0110 0. Shift a destra.
- P = 0000 0110 0.Gli ultimi bit sono "00".
- P = 0000 0011 0. Shift a destra.
- P = 0000 0011 0. Gli ultimi bit sono "10".
- P = 1101 0011 0. Calcolo P = P + S.
- P = 1110 1001 1. Shift a destra.
- 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.
