facciamo cultura

[misterx]

l'algoritmo di booth......

come diamine funziona ?

[Harvester]

Originariamente inviato da misterx
algoritmo di booth......

come diamine funziona ?


booohth..........:boh:

[Noia]

l'algoritmo di booth......
è un piatto tipipo di quale regione? :D

[break]

e che cultura e questa?

[misterx]

Originariamente inviato da break
e che cultura e questa?


una volta che qualcuno ce lo ha spiegato ti sarai pure tu acculturato.....

fidati :)

[break]

mi fido! :cool:

[misterx]

oppete

[break]

Originariamente inviato da misterx
l'algoritmo di booth......

come diamine funziona ?


http://bonda.cnuce.cnr.it/Documentation/ateach/arch1/materialeArch1/parte4/parte4_5.html#4.5.5

[misterx]

l'ho trovato pure io ma non mi è molto chiaro

[spinbird]

ho solo sentito sta lezione a reti logiche, ma non mi ricordo nulla :(

per caso ti avevo già linkato delle dispense?

[Scoperchiatore]

cosa riguarda?

[misterx]

Originariamente inviato da spinbird
ho solo sentito sta lezione a reti logiche, ma non mi ricordo nulla :(

per caso ti avevo già linkato delle dispense?



ho letto un pò di tutto ma mi sfugge il meccanismo in pratica

ho capito la versione stile (carta e penna) ma di booth ho capito poco

[misterx]

Originariamente inviato da Scoperchiatore
cosa riguarda?


è un metodo per velocizzare la moltiplicazione

[Alien]

Originariamente inviato da misterx
è un metodo per velocizzare la moltiplicazione

io per far ciò uso la calcolatrice :p :D

[spinbird]

Originariamente inviato da Alien
io per far ciò uso la calcolatrice :p :D

e la calcolatrice cosa fa?:p

[Berserker]

Il principio è molto semplice: si vuole rappresentare uno dei due numeri (diciamo, ad esempio, il moltiplicatore) in una forma che sia una potenza di due: ad esempio, supponiamo di voler moltiplicare 3 x 15, ovvero 00011 x 01111. Ora, noi vogliamo riscrivere la cosa come 00011 x (10000 - 00001). Dunque avremo un "debito" di 00011 (il bit di ordine più basso a uno che moltiplica il 3, mentre lo scalamento è ancora a zero), seguito da tre scalamenti (corrispondenti ai tre bit a 1 successivi a quello di ordine più basso in 001111). Al quarto scalamento, abbiamo 00110000 (ci sarebbe uno zero, ma a noi interessa la transizione da 1 a 0 - è quella che ci fa capire che la stringa di bit è terminata e che siamo in presenza dell'unico bit a 1), cui dobbiamo sottrarre 3 (il debito di prima). Risultato: 00101101, ovvero 45, il risultato giusto. Spero che l'esempio abbia chiarito, anziché oscurato, le idee...

[Berserker]

Ovviamente, non è (particolarmente) difficile dimostrare il principio di funzionamento in maniera generica, piuttosto che basandosi su un esempio. Se avete bisogno di aiuto, ripasso di qui domani in serata.

[Berserker]

Già stanchi di fare cultura? :p
Seriamente: è chiaro il principio di funzionamento?

[misterx]

Originariamente inviato da Berserker
Già stanchi di fare cultura? :p
Seriamente: è chiaro il principio di funzionamento?


stanco mai.....

riusciresti a riproporre il tuo esempio

3x15

step by step ?

mi sono leggermente perso :)

[Berserker]

Facciamo passo passo.

3 = 00000011
15 = 00001111

Immaginiamo di scandire i bit, partendo dal primo a destra, nel moltiplicatore (che è 15). Ad ogni passo, ci muoviamo di una posizione verso sinistra, incrementando di una unità lo scalamento (che inizialmente è pari a 0).
I primi due bit di 15 sono "11", quindi è l'inizio di una serie di 1. Devo tener conto di un "debito" di 3 scalato opportune volte: in questo caso, essendo lo scalamento 0, il debito è proprio di 3 (00000011). Gli altri 1 non fanno niente: li ignoriamo.
Alla fine della serie di bit a 1, sul primo zero, lo scalamento sarà pari a 4. Prendo 3 e lo scalo (shiftandolo a sx) di quattro volte, e ottengo quindi 00110000. Finisco la scansione dei bit di 15, tutti a zero (non fanno nulla e quindi li ignoriamo), e sottraggo da 00110000 il debito precedente, 00000011, ottenendo il risultato corretto.
Questo operativamente. Concettualmente, quello che stiamo facendo è, a tutti gli effetti, moltiplicare 3 x (16 - 1).
L'idea è, avendo un numero che ha una composizione tipo questa:

0...01...10...0

dove il primo 1, partendo da destra (numerando a partire da 0), è in posizione n e il primo zero dopo la serie di bit a 1 è in posizione m, di scalare n volte verso sinistra l'altro termine della moltiplicazione (chiamiamolo b) e sottrarre questo risultato a b scalato m volte, di nuovo verso sinistra. E' più chiaro così?

[misterx]

mi sa che non è giornata, ho capito poco :muro:

[Berserker]

Originariamente inviato da misterx
mi sa che non è giornata, ho capito poco :muro:
Boh, forse dipende anche dal fatto che sono un pessimo insegnante... :p
Cmq, mi sono reso conto di una cosa, riguardo all'algoritmo di Booth: è una cazzata, ma è difficile da spiegare. E gli esempi numerici non aiutano particolarmente. Bisogna prima afferrare il principio, e poi, al limite, "convincersene" con qualche esempio.
Faccio un ultimo tentativo: supponi di avere due numeri, a e b, che vuoi moltiplicare. La forma di a non ci interessa particolarmente. Prendiamo in considerazione il moltiplicatore b, che supporremo (per semplicità) avere una forma di questo tipo:

0...01...10...0

ovvero una fila di bit a 0, poi una di 1, e una di 0. Partendo da destra, e numerando a partire da 0, diremo che il primo bit alto è in posizione n, mentre il primo bit a 0, dopo la serie di 1, è in posizione m.
Ora, l'idea è quella di rappresentare b come una semplice potenza di due, meno qualcosa. Questo "meno qualcosa" avrà questa forma: 0...010...0 con l'unico 1 alla posizione n. In questo modo, puoi riscrivere b come: 0...010...0 (l'unico bit alto è in posizione m) - 0...010...0 (l'unico bit alto è in posizione n).
L'algoritmo che esegue la scansione di b tiene conto degli scostamenti per poter shiftare opportunamente a: in pratica, questa è la forma della distributività della moltiplicazione rispetto alla sottrazione, "alla Booth". Dunque dire che a viene shiftato verso sinistra di n posizioni è come dire moltiplicare, nell'esempio fatto prima, 3 per -1, e analogamente shiftare a di m posizioni vuol dire moltiplicare 3 per 16. Spero che sia sufficiente questa spiegazione... altrimenti non saprei come fare!

[misterx]

devo essermi rincitrullito ma sinceramente mi continua a sfuggire

ci scommetto che quando lo capirò daro le :muro:


usa questo esempio e se non ti scoccia:

0101x (5)
1110= (14)
----------

scrivimi passo passo il procedimento; ti assicuro che non è affatto semplice comprenderlo

ti sarei grato se scrivi una cosa nel modo seguente:

0101x
1110=

1- analizzo il moltiplicatore
2- il LSB è zero quindi non faccio niente
3- rianalizzo il moltiplicatore ed il 2° bit vale 1 quindi shifto moltiplicando a sx di un bit ed ottengo

e così via....

01010x
1110=


occhio che è solo un esempio

e grazie 1000 per la pazienza :)

[Berserker]

Riproviamoci! :)

x 0101 [5]
= 1110 [14]
--------
+ 0000 [scostamento = 0; il primo bit è zero, quindi verrà aumentato solo lo scostamento; l'algoritmo nota il bit successivo e si prepara a ricevere una eventuale sequenza di 1]
- 0101 [scostamento = 1; il terzo bit è a 1, quindi questo è effettivamente l'inizio di una sequenza di bit. Viene sottratto 0101 shiftato di 1, quindi 01010]
+ 0000 [scostamento = 2; secondo bit della serie a 1, non faccio nulla]
+ 0000 [scostamento = 3; terzo bit della serie a 1, non faccio nulla; l'algoritmo esamina il bit successivo e nota che questo era l'ultimo della serie]
+ 0101 [scostamento = 4; essendo il primo zero dopo la fila di bit alti, prendo 0101, lo shifto di 4 e addiziono. Fine]
--------
= 01000110 [70]

[misterx]

domani mi ci butto a capofitto e speriamo che questa volta il buon Dio mi dia una mano :D:D:D

grazie:)

[misterx]

non mi vergogno affatto ad ammettere che non ci sto capendo più un tubo :muro:


eppure dovrebbe essere così semplice


devo resettarmi e ripartire da zero :p

[Berserker]

Originariamente inviato da misterx
non mi vergogno affatto ad ammettere che non ci sto capendo più un tubo :muro:


eppure dovrebbe essere così semplice


devo resettarmi e ripartire da zero :p
Non ti scoraggiare. ;)
L'essenza dell'algoritmo sta tutta nel riconoscimento della fila di 1: è quello che permette di considerare, nell'esempio precedente, 14 come 16 - 2. Quello che fa l'algoritmo, sia pur implicitamente, è un'operazione come questa: 0101 x 1110 = 0101 x (10000 - 00010) = 0101 shiftato a sx di 4 - 0101 shiftato a sx di 1 = 01010000 - 01010 = 01000110.

[misterx]

stavo considerando la 1a versione dell'algoritmo di moltiplicazione che dovrebbe essere la più semplice e cioè:

1101x
1101= 169 dec

essendo il primo bit LSB del moltiplicatore a 1, procedo col sommare ciò che è presente nel registro chiamato prodotto(inizialmente posto uguale a 00000000) con il moltiplicando, e ciò avviene ogni volta che trovo un bit a 1 dopo lo shift nel moltiplicatore

siccome il moltiplicatore nel nostro caso vale 1101 avremo tre somme

svolgimento

somma del valore presente nel registro prodotto col moltiplicando in quanto il primo bit del moltiplicatore è a 1

00000000+
00001101
-------------
00001101


shifto moltiplicando e moltiplicatore

11010 sx
00110 dx


siccome il bit LSB del moltiplicatore vale zero, shifto senza fare alcuna somma

110100 sx
000011 dx


questa volta invece sommo perchè bit LSB del moltiplicatore vale 1

00001101+
00110100
-------------
01000001


shifto nuovamente

1101000
0000001

ed ho l'ultima somma in quanto il bit LSB=1

01000001+
01101000
-------------
10101001


quello di booth dovrebbe essere una variazione di questo procedimento o no ?

ok, insisto ancora:p

[misterx]

Originariamente inviato da Berserker
Facciamo passo passo.

3 = 00000011
15 = 00001111

Immaginiamo di scandire i bit, partendo dal primo a destra, nel moltiplicatore (che è 15). Ad ogni passo, ci muoviamo di una posizione verso sinistra, incrementando di una unità lo scalamento (che inizialmente è pari a 0).



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 ?

[Berserker]

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

[misterx]

Originariamente inviato da Berserker
Esatto! Hai avuto l'illuminazione? :)

...



è grazie alla tua pazienza se ne sto uscendo :)

[misterx]

ma dove cavolo è l'errore ??????


0011 x
0010 =
----
0110
------------------
(1)
inizializzo parte sx del registro prodotto col moltiplicando
0000|0010

0011
0010(0)

siccome ho (00) non faccio nulla, shifto a dx prodotto e moltiplicando

prodotto
0000|0001

moltiplicando
0011
0001(0)

siccome ho (10) sottraggo moltiplicando a parte sx dell prodotto
0000|0001-
0011|0000
---------
1101|0001

shifto a dx prodotto e moltiplicando
01101|0000

0011
0000(1)

siccome ho (01) sommo moltiplicando a parte sx dell prodotto
0110|1000
0011|0000
---------
1001|1000

shifto a dx prodotto e.....................
0100|1100



risultato errato!!!!!:muro: :muro: :muro:

[a2000]

è molto semplice:


più me lo meno, più vengo a meno
per non venir più non me lo meno più
ma se non me lo meno più, non vengo più
per non venir più, meno, quindi me lo meno di più per tutta la notte


capito adesso ? ;)

[misterx]

Originariamente inviato da a2000
è molto semplice:


più me lo meno, più vengo a meno
per non venir più non me lo meno più
ma se non me lo meno più, non vengo più
per non venir più, meno, quindi me lo meno di più per tutta la notte


capito adesso ? ;)



a te l'acido solforico fa brutti effetti

[misterx]

ma dove cavolo è l'errore ??????


0011 x
0010 =
----
0110
------------------
(1)
inizializzo parte sx del registro prodotto col moltiplicando
0000|0010

0011
0010(0)

siccome ho (00) non faccio nulla, shifto a dx prodotto e moltiplicando

prodotto
0000|0001

moltiplicando
0011
0001(0)

siccome ho (10) sottraggo moltiplicando a parte sx dell prodotto
0000|0001-
0011|0000
---------
1101|0001

shifto a dx prodotto e moltiplicando
01101|0000

0011
0000(1)

siccome ho (01) sommo moltiplicando a parte sx dell prodotto
0110|1000
0011|0000
---------
1001|1000

shifto a dx prodotto e.....................
0100|1100



risultato errato!!!!!:muro: :muro: :muro:

[misterx]

help:( :ave:

[misterx]

:O Berserker

perchè mi hai abbandonato ?????

ero quasi arrivato alla meta