facciamo cultura

[misterx]

mi sa che non è giornata, ho capito poco

[Berserker]

Originariamente inviato da misterx
mi sa che non è giornata, ho capito poco

Boh, forse dipende anche dal fatto che sono un pessimo insegnante...
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


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

grazie

[misterx]

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


eppure dovrebbe essere così semplice


devo resettarmi e ripartire da zero

[Berserker]

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


eppure dovrebbe essere così semplice


devo resettarmi e ripartire da zero

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

[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!!!!!

[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!!!!!

[misterx]

help

[misterx]

Berserker

perchè mi hai abbandonato ?????

ero quasi arrivato alla meta