Algoritmo di Booth

Da Wikipedia, l'enciclopedia libera.

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.

  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[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.
  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.

Implementazione tipica[modifica | modifica wikitesto]

Funzionamento[modifica | modifica wikitesto]