Salve gente,
scusate la banalità, ma:

$-14\quad mod\quad 16$

a che cosa è uguale? a -14 o a 2?

sul blog di U.Cerruti ho trovato un calcolatore implementato in javascript, che permette di effettuare anche il modulo di un numero e mi da che è uguale a 2;
mentre io pensavo fosse uguale a -14.
Questo è il link:

http://alpha01.dm.unito.it/personalpage ... calc8.html

Come funziona l'aritmetica modulare per i negativi?

Admin

la pensavo anche io come te...
ma devi tener presente che sono tra i meno accreditati al mondo nel campo dell'aritmetica modulare.
e di tutte le aritmetiche, se è per questo....
_________________
Enrico
(E' la divergenza di opinioni che rende possibili, e interessanti, le corse di cavalli-M.Twain)

Per quanto ne so, sono la stessa cosa:

7 Mod 3 = 1 = -2 (ove -2 è dato da 3-1)

A volte conviene utilizzare il segno negativo, altre no.

Se il resto è positivo, posso indicare anche un valore negativo (quello che manca per raggiungere il valore del modulo); se è negativo, posso indicare il valore positivo (con lo stesso significato di cui sopra).

Esempio:

(9+7) (mod 4) = 9 (mod 4) + 7 (mod 4) = (1 + 3) (mod 4) = 4 (mod 4) = 0

Avrei potuto scrivere:

(9+7) (mod 4) = 9 (mod 4) + 7 (mod 4) = -3 + 3 = 0 ed avrei terminato prima


Ancora:

(22 - 14) (mod 16) = 22 (mod 16) - (14 mod 16) = 6 - 14 = - 8

Posso scrivere anche:

(22 - 14) (mod 16) = 22 (mod 16) + (-14 mod 16) = 6 + 2 = 8

(22 - 14) (mod 16) = 22 (mod 16) + (-14 mod 16) = -10 +2 = -8

ma poiché:

(22 - 14) (mod 16) = 8 (mod 16) = 8, allora, ai fini delle operazioni modulari, in questo caso: 8 = - 8

Ultimo:

(22 + 16) (mod 17) = 22 (mod 17) + 16 (mod 17) = (5 + 16) (mod 17) = 21 (mod 17) = 4

ed infatti:

(22 + 16) (mod 17) = 38 (mod 17) = 4

ma avrei potuto anche scrivere:

(22 + 16) (mod 17) = 22 (mod 17) + 16 (mod 17) = (5 - 1) (mod 17) = 4 (mod 17) = 4
_________________
Checché: è la somma che fa il totale (Totò) - Ciao

Ciao Pietro, ciao Pasquale,

Se ammettiamo che una divisione possa avere due resti, allora dobbiamo anche ammettere che possa avere due risultati.
Non c'è problema, ma a me personalmente mette un po' di ansia...

Per quel che riguarda i numeri relativi, io la penso così (ma si tratta solo di convenzioni, forse)

Mi è capitato di leggere che...
Se a, b sono interi relativi, allora il resto, o meglio un resto r è un intero relativo tale che:

a = qb + r

con 0 ≤ |r| =0

N.B. Probabilmente il calcolatore di Cerruti funziona applicando questa condizione.


Gianfranco Bo

approfitto di questo topic per un commento (abbastanza in tema) alla pagina, testè aggiunta da GFBo al sito.
Sotoo il titolo "per diventare pitagorici" o qualcosa di simile, si propone la costruzione di un cubo con l'uso di cubetti più piccoli.
Ai tredici cubetti già presenti, occorre aggiungerne altri per formare un cubo compatto.
Alla risposta corretta e tradizionale, mi viene da accostare anche:
aggiungiamo "cinque cubi negativi" per ottenere un cubo di lato 2....
_________________
Enrico
(E' la divergenza di opinioni che rende possibili, e interessanti, le corse di cavalli-M.Twain)

Mbeh Gianfrà, non so spiegarmi bene, perché non conosco a fondo la materia: comunque non ho voluto dire che esistono due resti diversi, ma che nei calcoli con i moduli non cambia il risultato finale se considero un resto per quello che è, oppure in sua vece la differenza fra il modulo (divisore) ed il resto, presa col segno opposto.

Riporto ancora un esempio:

(50 - 11) (mod 19) = 50 (mod 19) - 11 (mod 19) = 12 - 11 = 1

(50 - 11) (mod 19) = 50 (mod 19) - 11 (mod 19) = 12 + 8 = 20, ma 20 (mod 19) = 1

Insomma, aggiungendo 8 invece di sottrarre 11, è come se dovendo fare (50-11)=39 (mod 19) avessi detto che il quoziente è 1 invece di 2; infatti se dico che il quoziente è 1, il resto diventa 20, cioè non ho terminato la divisione, intesa come successione di sottrazioni, e quindi sottraendo ancora un 19, riporto le cose a posto, cioè il quoziente a 2 ed il resto a 1, perché nell'aritmetica modulare, come nella divisione, le operazioni terminano quando il risultato finale è minore del modulo, ma se in una fase intermedia questo non è, non è un problema, perché si continua.

Se n (mod d) = 0 e invece in una fase delle operazioni dico che è d, non dico che i resti sono due (0 e d), ma che sono equivalenti, nel senso che continuando le operazioni, facendo cioè d(mod d), ottengo 0 e non altro numero fra 0 e d-1.

Ritornando all'esempio di sopra rifatto con segni diversi:

(50 + 11) (mod 19) = 50 (mod 19) + 11 (mod 19) = 12 + 11 = (12+11)(mod 19) = 23 (mod 19) = 4

oppure:

(50 + 11) (mod 19) = 50 (mod 19) + 11 (mod 19) = 12 - 8 = 4

Che significa 11 (mod 19) = -8 ? Che ho considerato il quoziente della divisione 11/19 uguale a 1, invece di zero e quindi il resto diventa -8, perché 1x19 - 8 = 11.

Conclusione: -14 (mod 16) significa cercare il resto della divisione fra -14 e 16, tale che detto q l'intero del quoziente ed R il resto, 16q + R = -14; se dico che q=0, allora R=-14, perché 16*0 + (-14) = -14; se dico che q= -1, allora R=2, perché 16(-1) + 2 = -14. Nell'aritmetica modulare si cerca l'equivalenza fra numeri o espressioni, in base ai resti e se due numeri diversi hanno lo stesso resto, secondo un certo modulo, diciamo che quei due numeri sono equivalenti, secondo quel modulo.
Vogliamo sapere se 54 e 27 sono divisibili per 3: vediamo che il resto della divisione per 3 per ambedue i numeri è 0 e allora diciamo che 54 e 27, in modulo 3, sono equivalenti; non ci interessa il quoziente, ma solo il resto, per cui considerando con artificio quozienti diversi dal solito, riusciamo ad ottenere delle equivalenze anche fra resti negativi e positivi, secondo un certo modulo.


Meglio non so spiegare...vedete voi.
_________________
Checché: è la somma che fa il totale (Totò) - Ciao

Intervengo nella questione.

Gianfranco ha scritto:Se però i a, b sono entrambi positivi, questa definizione suona male:

19/5 = 3, r=4

19/5 = 4, r=-1 (chi è disposto ad ammettere questa?)

Possibile che 19/5 abbia due risultati?
Può anche essere, ma non mi convince.
E allora?

Io sono dispostissimo ad ammettere che una divisione ammeta due risultati,se accettiamo che i resti possano essere negativi. A condizione che non prendiamo il risultato "impossibile" per una divisione reale:se devo dividere una torta di dodici fette tra otto amici più me e propongo di dare due fette a testa aggiungendo sei fette negative i miei amici mi mandano a spendere e si prendono la mia fetta di torta(la fetta positiva).Altro che dividere con due rette perpendicolari passanti per un punto P... Laughing
La divisione 12/9=2 con resto di -6 ha senso in matematica e può anche essere utilizzabile in determinati casi (una variante del famoso Problema dei Cinque Marinai,della Scimmia e delle Noci di cocco si risolve proprio usando quattro noci negative).Ripeto che se ci mettiamo a giocare coi resti negativi possiamo tirarne fuori di tutti i colori.
Mi chiedo cosa succederebbe nelle divisioni tra polinomi se accettiamo divisioni coi resti negativi.Hmm,sembra un terreno scivoloso...qualcuno ha idee in proposito?
Domanda per GFBo:io che sono un novellino,come posso inviare i miei contributi al sito?Non ho avuto pensate geniali,ma vorrei poter contribuire(soprattutto circa la pagina delle stanze e delle porte da percorrere).Posso?
§aluti§§imi,
0-§
_________________
Voglio tutto!Per favore...
(Io)
$\displaystyle \sum_{n=0}^{\infty}\;\int_{0}^{\infty}\;\prod_{k=0}^{\infty}\;\lim_{0\to\infty}=Zerinfinito...$

oncordo con tutto, ma lo scopo dell'aritmetica modulare, per certi tipi di indagine, non è quello di conoscere i quozienti, ma solo i resti.
_________________
Checché: è la somma che fa il totale (Totò) - Ciao

Ciao Pasquale, ciao Zerinf,
non volevo contestare la risposta di Pasquale, che è matematicamente corretta e può anche essere utile dal punto di vista operativo.

Intendevo solo segnalare che se accettiamo l'esistenza di due resti distinti allora dobbiamo accettare anche l'esistenza di due quozienti (o quoti, non so come si dice) distinti e fare attenzione a tutto quel che ne consegue.

Infatti: a MOD b è definito come il resto della divisione a:b

Allora, più precisamente, dovremmo dire che: a MOD b è definito come ciascuno dei due resti della divisione a:b

Poi ho aggiunto che io preferirei che la divisione avesse resto e risultato unici (in N e Z), così, perché ci sono abituato fin da piccolo...

Comunque questo è un campo in cui basta mettersi d'accordo.

Per Zerinf: se vuoi inviare aggiunte, correzioni, contributi al sito, basta che mi invii una mail. Ehm... però non troppo materiale, perché non riesco a star dietro a tutte le e-mail che ricevo e allora vado troppo in ansia, che non fa bene.


Ciao
Gianfranco Bo

Gianfranco ha scritto:In questo caso si ha:

-42/(-5) = 8, r=-2: esatta
-42/(-5) = 9, r=3: errata
-23/9 = -2, r=-5: esatta
-23/9 = -3, r=4: errata
19/5 = 3, r=4: esatta
19/5 = 4, r=-1: errata

Ho appena letto questo topic.
Se non ho capito male, allora, per la stessa convenzione sarebbe anche:

42/(-5)=-8, r=2: esatta
42/(-5)=-9, r=-3: errata
23/(-9)=-2, r=5: esatta
23/(-9)=-3, r=-4: errata
19/(-5)=-3, r=4: esatta
19/(-5)=-4, r=-1: errata,

è così?


_________________
Invisibile un vento / l'ha apena sfioragia / sospension d'un momento; /
e la bola iridessente gera 'ndagia. (Biagio Marin)

Io la vedo così

-14 mod 16 = 2

in quanto

(-14-2+2) mod 16 = (-16+2) mod 16 = -16 mod 16 + 2 mod 16 = 0 + 2 = 2

nel caso

14 mod -16

avremmo

(14+2-2) mod -16 = 16 mod -16 - 2 mod -16 = 0-2 = -2


Altri esempi:

-16 mod 14 ---> (-16-12+12) mod 14 = -28 mod 14 + 12 mod 14 = 0+12 = 12

16 mod -14 ---> (16+12-12) mod -14 = 28 mod -14 - 12 mod -14 = 0-12 = -12

-16 mod -14 ---> (-14-2) mod -14 = -14 mod -14 -2 mod -14 = 0-2 = -2


Per cui quello che ha scritto Bruno secondo è proprio al contrario:

42 mod -5 = (42+3-3)mod -5= 45 mod -5 - 3 mod-5 = 0-3 = -3

quindi:

42/(-5)=-8, r=2: errata
42/(-5)=-9, r=-3: esatta
23/(-9)=-2, r=5: errata
23/(-9)=-3, r=-4: esatta
19/(-5)=-3, r=4: errata
19/(-5)=-4, r=-1: esatta,



Ciao.

Edmund ha scritto: Per cui quello che ha scritto Bruno è proprio al contrario

...possibilissimo! Evidentemente devo leggermi il post con molta più attenzione
Intanto grazie, Edmund!

(Bruno)
_________________
Invisibile un vento / l'ha apena sfioragia / sospension d'un momento; /
e la bola iridessente gera 'ndagia. (Biagio Marin)

Ciao a tutti,
Edmund, Bruno, Pasquale, Pietro, Zerinf,
credo che abbiamo ragione tutti.

Infatti circolano diverse definizioni tutte autorevoli di quoziente, resto, e operatore MOD, quando si considerano gli interi relativi.
Per questo motivo, diversi software possono dare diverse risposte, sebbene riconducibili le une alle altre, come ha detto Pasquale.

Se accettiamo il seguente teorema e le definizioni che ne conseguono, allora è corretta l'interpretazione di Edmund
---
Teorema (tratto da un testo di matematica)
Siano a; b due interi, con b 0.
Allora esistono due, e due soli, interi q; r, tali che:
a = bq + r con 0 =0 (il più piccolo intero minore di x)
TRUNC(x) = ceiling(x) se x<0 (il più piccolo intero maggiore di x)
Esempi:
TRUNC(3.4)=3
TRUNC(-3.4)=-3

Definiamo le operazioni div (divisione intera), rem (resto), mod, come segue:
n div d = TRUNC(n/d)
Esempi:
19 div 5 = -19 div -5 = 3
-19 div 5 = 19 div - 5 = -3

n rem d = n-d*TRUNC(n/d)
19 rem 5 = 4
-19 rem -5 = -4
-19 rem 5 = -4
19 rem - 5 = 4
Cioè il resto ha lo stesso segno del dividendo.

n mod d = n - d * floor(n/d)
42 mod (-5) = 2
23 mod (-9) = 5
19 mod (-5) = 4
come dice Bruno

Personalmente preferisco le definizioni del MIT, ma ciò è irrilevante.
Aggiornerò la pagina del sito che è veramente poco chiara.

Buona notte a tutti
Gianfranco Bo

...

Gianfranco, grazie!

(Bruno)
_________________
Invisibile un vento / l'ha apena sfioragia / sospension d'un momento; /
e la bola iridessente gera 'ndagia. (Biagio Marin)

Ringrazio tutti per le risposte;
credevo fosse una banalità, ed invece tutt'altro.

Il dubbio comunque mi è sorto analizzando la rappresentazione in complemento a 2, che è quella utilizzata sulla maggiorparte dei computer per rappresentare in binario i numeri. (i bit del numero in binario hanno pesi positivi pari a potenze successive di 2, tranne il bit più significativo che ha peso negativo: es. $1010_{c2}\quad\Longrightarrow\quad -8+2=-6$)

In genere i linguaggi di programmazione comuni, utilizzano una aritmetica a precisione fissa, che vuol dire che se ho 2 numeri rappresentati in binario su n bit anche la loro somma sarà ad n bit.
In alcuni casi però la somma dei 2 numeri richiederebbe n+1 bit;
in questi casi il bit più significativo della rappresentazione della somma ad n+1 bit non viene considerato.

Ed è qui che viene il dubbio:

se ho i seguenti numeri x e y rappresentati in complemento a 2 a 4 bit:

$x\quad\Rightarrow\quad -7_{10}\quad\Longrightarrow\quad 1001_{c2}$
$x\quad\Rightarrow\quad 2_{10}\quad\Longrightarrow\quad 0010_{c2}$

la moltiplicazione mi da -14 che in complemento a 2 ha 5 bit:

$-7\cdot 2=-14\quad\Longrightarrow\quad 1001_{c2}\cdot 0010_{c2}=10010_{c2}$
ma con un linguaggio che utilizza l'aritmetica di precisione fissa, l'operazione di cui sopra da come risultato 0010 e non 10010.

Ora su di un testo di informatica che possiedo, l'operazione di moltiplicazione tra numeri in complemento a 2 rappresentati su n bit è definita matematicamente come:

$(x\cdot y)\quad mod\quad 2^n$

e quindi in compl. a 2

$(-14)\quad mod\quad 2^4$ veniva 2 e non -14 come io pensavo.

Da qui la perplessità.

Devo dire che mi piace molto la scomposizione di Edmund.

Admin
_________________
Pietro Vitelli
(Amministratore del Forum)
"Un matematico è una macchina che converte caffè in teoremi" Paul Erdös