Algoritmo di Booth: differenze tra le versioni

Versione delle 18:56, 1 dic 2012

Versione attuale delle 12:29, 12 gen 2024

(19 versioni intermedie di 18 utenti non mostrate)

Riga 1:

{{F|programmazione|febbraio 2013}}

{{S|matematica applicata}}

L{{'}}'''algoritmo del prodotto di Booth''', o semplicemente '''algoritmo di Booth''', è un [[algoritmo]] per il calcolo del [[moltiplicazione|prodotto]] tra due [[numeri binari]] con segno, espressi nella notazione [[complemento a due]]. Fu inventato dal [[fisica|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.

# 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 ===

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 = 11100000 100110'''10 10'''. Gli ultimi bit sono "1100", si lavora direttamente su P.

#* P = 11100000 10010110 10. Shift a destra.

* Dobbiamo eseguire i punti 2 e 3 ciclicamente per quattro volte.

#P = 0000 011'''0 0'''.Gli ultimi bit sono "00".

# *P = 0000 110'''00011 0'''. GliShift ultimia bit sono "00", si lavora direttamente su Pdestra.

#* P = 0000 0110001'''1 0'''. ShiftGli ultimi bit asono destra"10".

# *P = 00001101 011'''00011 0'''.Gli ultimi bitCalcolo P = P sono+ "00"S.

#* P = 00001110 00111001 01. Shift a destra.

# P = 00001110 001100'''1 01'''. Gli ultimi bit sono "1011".

#* P = 11011111 00110100 01. Calcolo P = PShift +a Sdestra.

#* P = 1110 1001 1. Shift a destra.

# P = 1110 100'''1 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==

{{S...|matematica applicata}}

==Funzionamento==

{{...|matematica}}

{{Portale|matematica}}

[[Categoria:Algoritmi aritmetici|Booth]]

[[ar:خوارزمية بووث للضرب]]

[[cs:Boothův algoritmus]]

[[de:Booth-Algorithmus]]

[[en:Booth's multiplication algorithm]]

[[es:Algoritmo de Booth]]

[[fa:الگوریتم بوث]]

[[fr:Algorithme de multiplication de Booth]]

[[ja:ブースの乗算アルゴリズム]]

[[lv:Buta algoritms]]

[[pt:Algoritmo de multiplicação de Booth]]

[[ru:Алгоритм Бута]]

[[zh:布斯乘法算法]]