Quote:
Originariamente inviato da misterx
scusa se torno indietro ma con questo esempio vuoi dirmi che il 15 mi serve solo per sapere di quanto devo scalare il 3 ?
e cioè scalo il 3 di 4 posizioni in quanto ho 4 uno di seguito ottenendo:
00110000
e poi da questo sottraggo il 3 ottenendo il risultato corretto ?
|
Esatto! Hai avuto l'illuminazione?
Quanto al paragone fra algoritmo "classico" e quello di Booth: sì, alla fin fine quello di Booth è solo una variante del classico. Sulle sequenze di due o più bit a 1 c'è un vantaggio proporzionale alla lunghezza della sequenza stessa, perché si evitano un bel po' di addizioni (pensa a tutti i bit a 1 subito dopo il primo: non viene effettuata alcuna operazione oltre allo scostamento dell'altro numero). C'è da dire che nel caso peggiore, l'algoritmo di Booth è significativamente peggiore dell'algoritmo tradizionale: nel caso di una moltiplicazione di un numero per una sequenza di tipo ...01010101... con n bit a 1, l'algoritmo tradizionale esegue n addizioni, mentre Booth esegue n sottrazioni
e n addizioni...