Newsgroup: it.comp.lang.c
Titolo: Ancora sulla divisione modulo 2.....

Qualcuno si chiederà perchè rompo tanto con questa divisione modulo 2.
PerchŠ sto preparando l'esame di Reti di calcolatori e tale operazione Š
fondamentale nel
calcolo delle checksum dei pacchetti che si spediscono in rete i vari
calcolatori
Non sono un fanatico dell'aritmetica binaria   :-)
Penso di essermi spiegato male nella  precedente mail, quindi mi spiego
meglio in questa
e rimando un esempio sicuramente corretto ( Š tratto dal Tanenbaum, un
"sacro testo"!!!!)
      1 1 0 1 0 1 1 0 1 1 0 0 0 0    |  1 0 0 1 1
                                                   ----------------
      1 0 0 1 1                               |  1 1 0 0 0 0 1 0 1 0
     -----------
        1 0 0  1 1
        1 0 0  1 1
        -----------
           0 0 0 0 1
           0 0 0 0 0
          -----------
             0 0 0 1 0
             0 0 0 0 0
             ----------
               0 0 1 0 1
               0 0 0 0 0
               ----------
                 0 1 0 1 1
                 0 0 0 0 0
                -----------
                    1 0 1 1 0
                    1 0 0 1 1
                   -----------
                       0 1 0 1 0
                       0 0 0 0 0
                       ----------
                         1 0 1 0 0
                         1 0 0 1 1
                         ----------
                            0 1 1 1 0
                            0 0 0 0 0
                            ----------
                              1 1 1 0
 Nota: la sottrazione viene eseguita MODULO 2, il che equivale a fare
l'addizione (OR Esclusivo)
           Inoltre:     ragionando in base 10, si tratta di eseguire
13774/19; otterrei un quoziente pari a 723
           ed un resto pari a 7, cioŠ gli stessi che otterrei ragionando
con la divisione in base 2 "normale"
           Invece i risultati di questa divisione MODULO 2 in base 10
valgono 778 (quoz) e 14 (resto).
           Naturalmente moltiplicando MODULO 2 quoziente e divisore
(usando cioŠ l'EXOR al momento di
          fare le somme) e sommando (ancora con l'exor) il resto
riottengo il risultato di partenza come
          èi facile verificare.
          Un'ultima osservazione: se al dividendo sottraggo (cioè
aggiungo con l'exor) il resto e continuo a
          dividere per il solito dividendo avrò come resto zero ( in
base 10 sarebbe come fare:
          18/5=3 con resto=3 ==>(18-3)/5=3 con resto 0).Dunque nel caso
precedente:
          (1 1 0 1 0 1 1 0 1 1 0 0 0 0 exor 1 1 1 0) / 1 0 0 1 1
fornisce zero come resto(calcoli analoghi
          per la verifica)
Ora vi faccio vedere dove puntualmente mi pianto io nella divisione
proposta nella mail precedente
     1 0 0 1 0 0   |  1 1
                         -------------
        1 1           | 1 1 1 1
    ------
     1 1 1 1             <----------------------
           1 1                                                 \
    --------                                                  \
    1 1 0 0 0           <------------------------\
             1 1
/---------Ma questi resti sono più grandi del divisore, possibile???????
    ----------                                              /
    1 1 0 1 1 0         <---------------------/
                1 1                                         /
    ------------                                      /
    1 1 0 1 0 1         <-----------------/
                                  ALT!!!!!!!!!!!!!!   I conti
sembrerebbero tornare!!!!!!!!!!
Infatti:     1 1 1 1 *
                    1 1=
             --------
               1 1 1 1
            1 1 1 1
           -----------
           1 0 0 0 1  + (exor)
        1 1 0 1 0 1
        ------------
        1 0 0 1 0 0
Ora però se andiamo a sommare exor il resto al dividendo e a
rieffettuare la divisione:
        1 0 0 1 0 0 + (divid)
        1 1 0 1 0 1 = (resto)
        -----------
        0 1 0 0 0 1    <--------> dividendolo per  1 1 dovrei avere
resto zero
        1 0 0 0 1  | 1 1
                        --------
           1 1        | 1 1 1
        -----
        1 1 1 0
              1 1
        -------
        1 1 0 1 1
                 1 1
        ---------
        1 1 0 0 0   ----------->Col cavolo che è uguale a
zero.............
Se non vi rompe e avete lumi in proposito vi ringrazio.Ciao

 proposta nella mail precedente
[..]
Ti svolgo anche questa, anche se valgono anche qui le considerazioni
precedenti...:
1 0 0 1 0 0 : 1 1 = 1 1 0 0
  1 1-
-----
    1 1
    1 1-
    ----
      0 0 0
cioè, in decimale: 36 : 3 = 12 (resto 0)
Spero ti sia utile, se hai altri dubbi...
ciao
--
 
     _
    / 7		
   /_(   
   |_|
   |_|		
   |_|		Cujo®, sometimes referred to as:
   |_| /\
 /\|=|/ /
 \ |_| /         Francesco C.
  ) _  \           e-mail: 
cu...@energy.it
 / |_|  \            ICQ#: 2199793
/  -=-o /
\  /~\_/
 \/      
http://yourweb.energy.it/cujo

negativi, senza pensare a rappresentazioni c2, ecc.) vale quanto segue:
Be', io credo che se il nostro amico e' arrivato a dare l'esame di
Reti di Calcolatori lo sappia come si fa una sottrazione/addizione in
binario ;)
Se parla di divisione modulo 2 e' forse perche' questo procedimento
particolare si applica nel contesto che a lui serve (Neanch'io
comunque ne ho mai sentito parlare ed il procedimento mi risulta molto
strano, comunque mi fido del grande Andrew Tanenbaum ;)...
Comunque, per rifarci allo xor, in realta' sia nell'addizione che
nella sottrazione, lo xor equivale al calcolo senza i riporti e i
prestiti.
Nel senso, un'addizione normale e' :
10001010101 +
00101010011 =
----------- 
10110101000
escludendo i riporti si ha :
10100000110 
che equivale all'operazione di xor tra i due numeri e come puoi notare
e' il risultato dell'addizione tra essi senza riporti e della
sottrazione tra essi senza prestiti.
Andrea Laforgia        (
andrea_...@bigfoot.com
)
----------------------------------------------------
There is nothing better for understanding a kangaroo
than seeing it jump.
----------------------------------------------------

     1 0 0 1 0 0   |  1 1
Puo' darsi che mi stia sbagliando, ma 100100 / 11, secondo il tuo
procedimento, non e' uguale a 11100 con resto 0 ?
Difatti :
  1 1 1 0 0 *
        1 1
  -----------
  1 1 1 0 0 xor  
1 1 1 0 0 
-------------
1 0 0 1 0 0


 valgono 778 (quoz) e 14 (resto).
Aspetta... scusa, ma non avevo fatto caso a quella frase prima (e l'ho
pure quotata...;-)), quindi forse cade tutto quello che ho scritto nel
post precedente... Potresti per favore darmi la definizione di
"divisione modulo X in base Y" ??? 
Io per modulo intendo un operatore binario tale che X MOD Y = "il resto
generato da X / Y"... mi sono perso qualcosa? ;-))
Ciao


"divisione modulo X in base Y" ??? 
Credo che per divisione modulo 2 si intenda non una serie di
sottrazioni (come la divisione normale), ma una serie di sottrazioni
senza riporto (quindi una serie di xor).
