Algoritmo di Booth: differenze tra le versioni

Versione delle 13:10, 31 mag 2010

Versione attuale delle 12:29, 12 gen 2024

(33 versioni intermedie di 28 utenti non mostrate)

Riga 1:

{{F|programmazione|febbraio 2013}}

{{A||matematica|maggio 2010|firma=[[Utente:Sandr0|<span style="color:navy;">'''San'''</span>]][[Discussioni utente:Sandr0|<span style="color:gold;">'''dro'''</span>]] 13:10, 31 mag 2010 (CEST)}}

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

{{O|matematica|maggio 2010}}

L''''Algoritmo del prodotto di Booth''' è un algoritmo per il calcolo del prodotto tra due [[numeri binari]] con segno, espressi nella notazione [[complemento a due]].

==Procedimento==

<noinclude>{{Categorizzare|matematica}}</noinclude>

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.

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

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

[[cs:Boothův algoritmus]]

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

[[de:Booth-Algorithmus]]

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

[[en:Booth's multiplication algorithm]]

#Osservare i due bit meno significativi (più a destra) di P

[[es:Algoritmo de Booth]]

##Se sono "01", calcolare il valore di P + A, ignorando eventuali overflow.

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

##Se sono "10", calcolare il valore di P + S, ignorando eventuali overflow.

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

##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 = 0000 110'''0 0'''. Gli ultimi bit sono "00", si lavora direttamente su P.

#*P = 0000 0110 0. Shift a destra.

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

#*P = 0000 0011 0. Shift a destra.

#P = 0000 001'''1 0'''. Gli ultimi bit sono "10".

#*P = 1101 0011 0. Calcolo P = P + S.

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

{{O...|matematica|maggio 2010}}

==Funzionamento==

{{...|matematica}}

{{Portale|matematica}}

[[Categoria:Algoritmi aritmetici|Booth]]