Algoritmo di Booth
Ciao a tutti, in questi giorni mi sto preparando per l'esame di Architettura degli Elaboratori.
La mia domanda è questa: qualcuno mi può spiegare come funziona l'algoritmo di Booth e a cosa serve??
Grazie mille!!!
La mia domanda è questa: qualcuno mi può spiegare come funziona l'algoritmo di Booth e a cosa serve??
Grazie mille!!!
Risposte
Ciao,
da un po' non sentivo parlare dell'algoritmo di Booth
Vado a memoria...
serve per fare le moltiplicazioni in codifica binaria,
è vantaggioso rispetto alla moltiplicazione naive, mi sembra che ricodificando a coppie i bit, riduce le somme da fare. Se ricordo bene c'è una versione "migliorata" che codifica a tre bit, ma è una versione diversa...
Se hai un'esempio su cui non riesci a fare la codifica, perchè alla fine è una cosa automatica, mostralo che ti si da una mano
da un po' non sentivo parlare dell'algoritmo di Booth
Vado a memoria...
serve per fare le moltiplicazioni in codifica binaria,
è vantaggioso rispetto alla moltiplicazione naive, mi sembra che ricodificando a coppie i bit, riduce le somme da fare. Se ricordo bene c'è una versione "migliorata" che codifica a tre bit, ma è una versione diversa...
Se hai un'esempio su cui non riesci a fare la codifica, perchè alla fine è una cosa automatica, mostralo che ti si da una mano
Per esempio io voglio fare questa moltiplicazione:
10011 * 01011 che corrispondono rispettivamente a -13 e 11. Come faccio a trasformare i numeri con l'algoritmo di booth??
Grazie della disponibilità!
10011 * 01011 che corrispondono rispettivamente a -13 e 11. Come faccio a trasformare i numeri con l'algoritmo di booth??
Grazie della disponibilità!
Prendi tabellina di ricodifica dell'algoritmo di Booth (standard):
00 -> 0
01 -> +1
10 -> -1
11 -> 0
regole di calcolo:
- 0: scrivi 0 per tutta l'estensione del risultato
- +1: ricopi il moltiplicando
- -1: fai il complemento a 2 del moltiplicando
il resto è tutto uguale alla moltiplicazione normale tra due numeri binari (perciò le regole di shift sinistro, somme a coppie e risultato occupa il doppio dei bit, sono validi)
prendi il moltiplicatore: 01011
aggiungi un bit in posizione meno significativa: 010110
poi vai a coppie e ricodifichi:
01 -> +1
10 -> -1
01 -> +1
11 -> 0
10 -> -1
adesso devi moltiplicare:
10011* (+1 -1 +1 0 -1)
utilizzi le regole di calcolo che ti ho scritto sopra e il gioco è fatto, se sei capace di moltiplicare in binario...
se hai dubbi chiedi pure
PS: sono andato un po' a memoria, ma calcolando è corretto quanto detto
00 -> 0
01 -> +1
10 -> -1
11 -> 0
regole di calcolo:
- 0: scrivi 0 per tutta l'estensione del risultato
- +1: ricopi il moltiplicando
- -1: fai il complemento a 2 del moltiplicando
il resto è tutto uguale alla moltiplicazione normale tra due numeri binari (perciò le regole di shift sinistro, somme a coppie e risultato occupa il doppio dei bit, sono validi)
prendi il moltiplicatore: 01011
aggiungi un bit in posizione meno significativa: 010110
poi vai a coppie e ricodifichi:
01 -> +1
10 -> -1
01 -> +1
11 -> 0
10 -> -1
adesso devi moltiplicare:
10011* (+1 -1 +1 0 -1)
utilizzi le regole di calcolo che ti ho scritto sopra e il gioco è fatto, se sei capace di moltiplicare in binario...
se hai dubbi chiedi pure
PS: sono andato un po' a memoria, ma calcolando è corretto quanto detto
Ho capito come trasformare il numero con l'algoritmo di booth, ma non ho capito cosa intendi con "scrivi 0 per tutta l'estensione del risultato";
cioè la somma +1-1+1+0-1 fa 0 quindi moltiplico 10011*0 e poi?
cioè la somma +1-1+1+0-1 fa 0 quindi moltiplico 10011*0 e poi?
Ma no...
sono simboli non sono "somme". Diventa una "matrice" da moltiplicare, come un qualsiasi numero binario
01001*
+1-1+1 0-1
Primo passo:
01001*(-1) perciò fai complemento a 2 del numero. Ed estendi il segno...come una moltiplicazione normale.
Secondo passo:
01001*(0) shift a sinistra di una pozione e riporti tutto zero
Terzo passo:
01001*(+1) shift a sinistra di due posizioni e riporti 01001 ed estendi il segno
ecc...
una normale moltiplicazione...
sono simboli non sono "somme". Diventa una "matrice" da moltiplicare, come un qualsiasi numero binario
01001*
+1-1+1 0-1
Primo passo:
01001*(-1) perciò fai complemento a 2 del numero. Ed estendi il segno...come una moltiplicazione normale.
Secondo passo:
01001*(0) shift a sinistra di una pozione e riporti tutto zero
Terzo passo:
01001*(+1) shift a sinistra di due posizioni e riporti 01001 ed estendi il segno
ecc...
una normale moltiplicazione...
Ho capito!! Grazie!!!
P.S. Però non mi pare che siano di meno le somme da fare, o sbaglio?
P.S. Però non mi pare che siano di meno le somme da fare, o sbaglio?
non sempre è vantaggioso, alle volte è uguale ad una normale moltiplicazione.
Dipende dai numeri binari (dal moltiplicatore), un esempio può essere se hai più bit attivi consecutivi, in quel caso avrai molti $0$ dalla codifica come risultato... e perciò molte somme (interne) in meno da fare
Dipende dai numeri binari (dal moltiplicatore), un esempio può essere se hai più bit attivi consecutivi, in quel caso avrai molti $0$ dalla codifica come risultato... e perciò molte somme (interne) in meno da fare
Un'ultima domanda:
guardando nella dispensa dell'esercitatore di Architettura ho trovato il paragrafo "Moltiplicazione con metodo bit-pair recoding";
questo metodo usa le triple al posto delle coppie per trasformare il numero, mi potresti spiegare in che modo le usa le triple?
Nella dispensa c'è scritto veramente poco..
Grazie!!
guardando nella dispensa dell'esercitatore di Architettura ho trovato il paragrafo "Moltiplicazione con metodo bit-pair recoding";
questo metodo usa le triple al posto delle coppie per trasformare il numero, mi potresti spiegare in che modo le usa le triple?
Nella dispensa c'è scritto veramente poco..
Grazie!!
ah ecco si chiama "bit-pair recoding" l'algoritmo di Booth migliorato, non lo ricordavo
al momento però non ricordo la sua codifica e funzionamento esatto. Ma sicuramente sarà molto simile a quello sopra.
prova a googlare...o al massimo cerco qualcosa dopo...
al momento però non ricordo la sua codifica e funzionamento esatto. Ma sicuramente sarà molto simile a quello sopra.
prova a googlare...o al massimo cerco qualcosa dopo...
Allora il bit pair recoding è praticamente simile all'algoritmo di booth, come detto.
Tabella di ricodifica:
000 -> 0
001 -> +1
010 -> +1
011 -> +2
100 -> -2
101 -> -1
110 -> -1
111 -> 0
Le uniche modifiche sono:
- +2: shift sinistra sempre di una posizione e ricopio moltiplicando
- -2: shift a sinistra sempre di una posizione e faccio complemento a due
- se serve estendi il segno nella ricodifica con un bit (stesso caso dello zero in posizione meno significativa)
rispetto alla moltiplicazione standard:
- shift a sinistra di due posizioni invece che uno
pui ricodificare anche la codifica fatta con l'algoritmo di Booth
se hai dubbi chiedi pure, ma se hai capito A. di Booth non avrai problemi...
Tabella di ricodifica:
000 -> 0
001 -> +1
010 -> +1
011 -> +2
100 -> -2
101 -> -1
110 -> -1
111 -> 0
Le uniche modifiche sono:
- +2: shift sinistra sempre di una posizione e ricopio moltiplicando
- -2: shift a sinistra sempre di una posizione e faccio complemento a due
- se serve estendi il segno nella ricodifica con un bit (stesso caso dello zero in posizione meno significativa)
rispetto alla moltiplicazione standard:
- shift a sinistra di due posizioni invece che uno
pui ricodificare anche la codifica fatta con l'algoritmo di Booth
se hai dubbi chiedi pure, ma se hai capito A. di Booth non avrai problemi...
ok, ora è tutto chiaro!!! Grazie!!!
piccolo dubbio: nella codifica di Booth, lo zero che hai aggiunto nella posizione meno significativa va aggiunto sempre??
da quello che mi ricordo, deve essere sempre messo per "stabilità". Invece in mosizione più significativa (l'estensione del segno) solo "se necessario".
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo