x MOD y

-5 Mod 3 ist 1, denn

-10 -9 -8 -7 -6 -5 -4 -3 -2 -1 0 1 2 3 4 5 6 7 8 9 10
2 0 1 2 0 1 2 0 1 2 0 1 2 0 1 2 0 1 2 0 1 (x mod 3=1)

-5 mod 3 kann nur 1 sein , sonnst musste sich bei 0 die Reihenfolge ändern)

c++ macht es möglicherweise anders

So ist die Zuordnung besser zu sehen

(x) (x mod 3)
. .
. .
-10 2
-9 0
-8 1
-7 2
-6 0
-5 1 !
-4 2
-3 0
-2 1
-1 2
0 0
1 1
2 2
3 0
4 1
5 2
6 0
7 1
8 2
9 0
10 1
. .
. .
. .

Gary

Danke Leute.
Jetzt ists klarer.

WebFritzi

Original erstellt von <MisterX>:
sonnst musste sich bei 0 die Reihenfolge ändern

Na und? Was ist denn gegen

(x) (x mod 3)
.    .
.    .
-10 -1
-9   0
-8  -2
-7  -1
-6   0
-5  -2       
-4  -1
-3   0
-2  -2
-1  -1
0    0
1    1
2    2
3    0
4    1
5    2
6    0
7    1
8    2
9    0 
10   1
.    .
.    .
.    .

zu sagen? Wie gesagt: Ist alles Definitionssache!

[ Dieser Beitrag wurde am 15.04.2003 um 02:46 Uhr von WebFritzi editiert. ]

Es ist etwas gegen -x als Ergebnis zu sagen, weil modulo (mathematisch) so def. ist, dass es keine negativen Elemente geben darf!

Das Rechnen mit dieser Struktur beruht daruaf, dass die Körperaxiome erfüllt sind!

Ohne diese Axiome würde z.B. dies nicht möglich sein:

(k mod p) + (l mod p) = (k+l) mod p
(k mod p) * (l mod p) = (k*l) mod p

Denn sei ( k mod p) = [r] und (l mod p) =[s], dann gibt es a,b Element Z
mit k=a*p+r, l=b*p+s Also:

k+l=(a+b)p +(r+s)
k*l=(a*b*p+a*s+b*r)*p+r*s

Also haben k+l und r+s sowie k*l und r*s denselben Rest bei der Division durch p.
Statt mit r und s können wir also mit k und l rechnen.
Aber nur, wenn man KEINE negativen Zahlen als Ergebnis zulässt!

ps. Sollte ich einen Fehler eingebaut haben , bitte schreiben!

malfunction

Also ein x86 Prozessor scheint ebenfalls 2 als Lösung für 5 MOD -3 als richtig anzusehen. Hier ein wenig Code:

mov eax,5
cdq
mov ecx,-3
idiv

Danach ist EAX gleich -1 (Ergebnis) und EDX ist gleich 2 (Rest). Und noch ein Zitat: "The sign of the remainder is always the same as the sign of the dividend" (aus: "Intel Pentium Instruction Set Reference", bei der Beschreibung der IDIV Instruktion).

Gary

Das heißt ja, ich hatte recht.

elise

[ Dieser Beitrag wurde am 22.04.2003 um 19:15 Uhr von elise editiert. ]

Bashar

sorry elise das kommt davon wenn man vergißt sich umzumelden ...

Gary: Nö, es ging ja ursprünglich um -5 mod 3, nicht 5 mod -3 :p

Außerdem ist es fraglich, ob der IDIV-Befehl wirklich modulo rechnet, in der Befehlsbeschreibung steht ja "remainder", also Rest (nein das ist nicht das gleiche)

Blue-Tiger

worin liegt denn der Unterschied zwischen REM und MOD?

WebFritzi

Original erstellt von <MisterX>:
**Das Rechnen mit dieser Struktur beruht daruaf, dass die Körperaxiome erfüllt sind!

Ohne diese Axiome würde z.B. dies nicht möglich sein:

(k mod p) + (l mod p) = (k+l) mod p
**

*lol* Das ist nicht dein Ernst, oder? Bis hierhin habe ich gelesen, aber nicht weiter. Da redest du von Körperaxiomen und schreibst so einen Müll. Das disqualifiziert dich, mein Junge! Setz mal p = 8, k = 15 und l = 14. Aha, nach deinem Gesetz wäre dann 7 + 6 = 5. Uiuiui. Allerdings stimmt das "Gesetz":

((k mod p) + (l mod p)) mod p = (k+l) mod p

Dieses wäre aber bei unserer Definition des Modulo-Operators (obige Aufgabe: -2) gültig.

Jester

Wo ist das Problem bei 7+6=5? Modulo 8 stimmt das doch... funktioniert also.

Aber abgesehen davon: Warum geben wir uns so viel Mühe nachzuweisen, daß die Verknüpfung _repäsentantenunabhängig_ ist, wir also einen beliebigen Vertreter der Nebenklasse auswählen können, um danach darüber zu streiten welchen wir nehmen.

Ob wir das Kind jetzt 2 oder -1 nennen, in Z/3Z ist es dasselbe. Und da modulo n rechnen rechnen in Z/nZ bedeutet ist es auch wurscht, ob wir Vorzeichen zulassen oder nicht. Ich persönlich mag's lieber ohne Vorzeichen, aber das ist *reine* Geschmacksache.

@Jester: welches Semester := S?
Wenn S>4: hast du Zahlentheorie oder Algebra und was noch?

Jester

S=4
Schreibe morgen Algebra I
Keine Zahlentheorie und auch sonst nix wirklich tiefergehendes gehört bis jetzt

malfunction

@Bashar: Also da musst du mir mal den Unterschied zwischen Rest und Modulo erklären. Ich dachte immer Modulo sei so definiert, dass es den Rest einer Division zurückgibt.

@malfunction

Bashar

malfunction:

ich kenne die genaue Definition nicht, ich würde aber sagen, dass es bei modulo darauf ankommt, dass für positive y gilt: 0 <= x mod y < y, weil alle x auf ihre Restklasse mod y abgebildet werden. Ich halte mich ansonsten an die Definitionen aus Common Lisp und Ada:

(mod x y) und (rem x y)
bzw. x mod y und x rem y

In beiden Sprachen hat das Ergebnis von mod das Vorzeichen von y, und rem das Vorzeichen von x. Für x und y > 0 fallen sie zusammen. Wenn jemand andere Definitionen kennt, die dem widersprechen oder es unterstützen, nur her damit.

An WebFritzi

"... *lol* Das ist nicht dein Ernst, oder? Bis hierhin habe ich gelesen, aber nicht weiter. Da redest du von Körperaxiomen und schreibst so einen Müll. Das disqualifiziert dich, mein Junge! Setz mal p = 8, k = 15 und l = 14. Aha, nach deinem Gesetz wäre dann 7 + 6 = 5. Uiuiui. Allerdings stimmt das "Gesetz":

((k mod p) + (l mod p)) mod p = (k+l) mod p
..."

OK.
Für Dich gaannzz ausführlich:
p = 8, k = 15 und l = 14

(k mod p)=(15 mod =7
(l mod p)=(14 mod =6

=>(k mod p) + (l mod p))= 7+6=13
13 mod 8=5 !
Möglicherweise war hier der Fehler, denn ich habe vorausgesetzt,
dass es bekannt ist, dass auch mod gerechnet wird wenn das Ergebnis >=8 ist.
Dies ist so, weil wir uns ja genau in diesem Körper befinden,in dem immer
mod p gerechnet wird.(Abgeschlossenheit))

((k+l) mod p) =(15+14) mod 8=29 mod 8=5 !!!!!!

5=5 also ((k mod p) + (l mod p))= (k+l) mod p

Noch ein Argument gegen -2
Wir rechnen in mod x,mit Zahlen 0...x-1
Minuszahlen vertragen sich nicht mit der oben erwähnten Abgeschlossenheit!

malfunction

@Bashar: Ich kenne beide Sprachen leider nicht, aber ich akzeptiere das mal so. Ich persönlich nehme die Dinge meist nicht ganz so genau. Liegt wahrscheinlich daran, dass ich in Assembler programmiere. Eine absolut gar nicht formale Sprache

Jester

@MisterX:

Bitte nimm Dir nochmal ein Algebra Skript oder sowas ähnliches und lies Dir die Definition einer Nebenklasse durch. Es ist egal welchen Vertreter wir wählen. Und wenn DU von Körpern redest, dann betrachtest Du nur modulo Primzahlen, das ist Dir sicher auch klar. Also immer fein Ring sagen, wenn Du Körper meinst.
Und wie schon gesagt, auf die Wahl des Repräsentanten kommt es nicht an. Das hast Du oben sogar selbst nachgewiesen.

Wenn ich also mod m rechne, dann kann ich -1 oder m-1 schreiben, ist absolut das gleiche! Die Nebenklassen sind identisch.

MfG Jester