Modulo mit negativen Zahlen

Hallo zusammen,

Modulo gibt bei positiven Zahlen den Rest einer Divison zurück - das ist mir soweit klar.
Doch wie verhält sich der Operator bei negativen Zahlen?

Unser Lehrer gab uns 6 als Lösung auf (3-6)%9.
Wenn man dies in einem Online-Modulo Rechner (nicht Windows-Rechner) nachprüft, stimmt dies auch.
Nur, die Frage ist 'Warum?'.
Die Erklärung der Lehrperson ist leider komplett unbrauchbar & darum liegt es mittlerweile an der Einzelperson dies herauszufinden.

Schaut man sich den Artikel auf Wikipedia (http://de.wikipedia.org/wiki/Modulo#Modulo) sticht einem folgende Mathematische Definition ins Auge:

( -a ) % m -> -( a%m )

Das würde folgendes bedeuten:

( 3 - 6 ) % 9 -> ( -3 ) % 9 -> -( 3 % 9 ) = -3

Oder begehe ich hier bereits den ersten Fehler?

Ausserdem machten mich folgende Beispiele "stutzig".

−7 :  3 = −1 Rest −4
−7 :  3 = −2 Rest −1
−7 :  3 = −3 Rest  2

Das Ergebnis kann also quasi irgendetwas sein, hauptsache schlussendlich stimmt (Ergebnis * ModOperator + Rest = Nenner) wieder?
Dies sollte nicht wirklich passieren, da laut meinem Lehrer der Modulo-Operator oft in einem Komprimierungsverfahren eingesetzt wird.

Kann mir jemand auf die Sprünge helfen?

Gruess,
Moduloprinz

Sorry für den kopierten - komischen - Code aus Wikipedia.
Richtig sieht das so aus:

-7 : 3 = −1 Rest −4
−7 : 3 = −2 Rest −1
−7 : 3 = −3 Rest 2

(ich hoffe nun klappt es.. anonsten schaut einfach auf der Seite unter "Ganze Zahlen" nach.

Dasd

Dein Lehrer hat recht. Führe dir mal vor Augen, dass -x das additiv Inverse zu x ist, d.h.

x + (-x) = 0 (mod m)
6 + 3 = 0 (mod 9)

otze

Moduloprinz schrieb:

Das Ergebnis kann also quasi irgendetwas sein, hauptsache schlussendlich stimmt (Ergebnis * ModOperator + Rest = Nenner) wieder?
Dies sollte nicht wirklich passieren, da laut meinem Lehrer der Modulo-Operator oft in einem Komprimierungsverfahren eingesetzt wird.

Das was Wikipedia sagt, ist korrekt. Das Ergebnis des Modulooperators ergibt nie eine einzelne Zahl. Das heißt a%s ≡ r+n*s wobei n jede ganze Zahl ist und r ein gültiger Rest. Das Ganze nennt man eine Kongruenzklasse (deswegen teht auch oben kein = sonder ein ≡). Du darfst das aber nicht mit uneindeutigkeit verwechseln. Im Sinne vom Modulo haben alle diese Zahlen den selben "Wert", es sind nur andere Darstellungen der selben Zahl.

Deswegen dürfen wir in der Kompression folgendes machen:
( -3 ) % 9 = ( -3 ) % 9 + 0 = ( -3 ) % 9 + (9 % 9)= (-3+9) % 9 = 6%9 = 6.

Oder nochmal anders ausgedrückt:

Wenn man mod 9 rechnet (oder genauer: im Ring der Zahlen modulo 9) sind
...-21, -12, -3, 6, 15, 24, ...
alles unterschiedliche Darstellungen derselben "Zahl".

Entsprechend sind auch
...-20, -11, -2, 7, 16, 25, ...
alles die selben Dinger.

Es ist bloß unglaublich bequem, nur mit 0,1,2,3,4,5,6,7,8 zu rechnen und nicht mit
9,19,11,12,13,14,15,16,17 oder mit -9,-8,-7,-6,-5,-4,-3,-2,-1 oder (noch unangenehmer) mit irgendeiner komischen Mischung daraus.

wxSkip

Wegen inkorrektem Modulo in vielen Programmiersprachen (die negative Zahlen in diesem Fall zurückgeben) sind AFAIK viele Gauß-Wochentags-Berechnungen seit dem 1.1.2000 falsch gelaufen und man dachte auch noch, die Formel sei falsch

Bitte ein Bit

Wegen inkorrektem Modulo in vielen Programmiersprachen (die negative Zahlen in diesem Fall zurückgeben) sind AFAIK viele Gauß-Wochentags-Berechnungen seit dem 1.1.2000 falsch gelaufen und man dachte auch noch, die Formel sei falsch

Weis jemand eigentlich warum die Programmiersprachen dies so machen ? Ich bin da gerade wieder drübergestolpert.

Bashar

"inkorrekt"? Man zeige mir eine Sprache mit einem "Modulo"-Operator, der falsch arbeitet. Tipp: In den C/C++-Standards wird % nicht Modulo genannt.

krümelkacker

% ist in C und C++ nicht der "Modulo-Operator" sondern gibt einem nur den Divisionsrest. Also, a % b ist das, was übrig bleibt, wenn man a durch b mit Rest teilt. Es gilt dann

(a/b) * b + a%b == a

und ich denke mal, dass das eher dem entspricht, was eine CPU so bei einer Ganzzahldivision ausrechnet. Zumindest berechnet das so eine x86-CPU (IDIV) ... und das sogar gleichzeitig, also die Division auch den Rest, wobei diese beiden Werte dann in zwei verschiedenen Registern abgelegt werden. Es würde mich nicht wundern, wenn das andere CPUs ähnlich machten. Dann läge es auch nahe, dafür in C bzw in C++ einen entsprechenden Operator zu definieren.

Übrigens: In Python läuft das anders. Da ist das Vorzeichen von a % b nur Abhängig von b. Ist b positiv, ist auch automatisch a%b entweder Null oder auch positiv.

Bashar

krümelkacker schrieb:

% ist in C und C++ nicht der "Modulo-Operator" sondern gibt einem nur den Divisionsrest. Also, a % b ist das, was übrig bleibt, wenn man a durch b mit Rest teilt. Es gilt dann
(a/b) * b + a%b == a
und ich denke mal, dass das eher dem entspricht, was eine CPU so bei einer Ganzzahldivision ausrechnet.

Das ist sowieso klar. Die obige Gleichung muss immer gelten. Der Unterschied der beiden Lesarten liegt darin, ob die Ganzzahldivision immer abrundet oder ob sie die Nachkommastellen abschneidet.

Beispiele:

Abrunden (-12/7 = -2)
(-12)/7 * 7 + (-12)%7 = -12 → (-2) * 7 + (-12)%7 = -12 → (-12)%7 = 2
12/(-7) * (-7) + 12%(-7) = 12 → (-2) * (-7) + 12%(-7) = 12 → 12%(-7) = -2
Abschneiden: (-12/7 = -1)
(-12)/7 * 7 + (-12)%7 = -12 → (-1) * 7 + (-12)%7 = -12 → (-12)%7 = -5
12/(-7) * (-7) + 12%(-7) = 12 → (-1) * (-7) + 12%(-7) = 12 → 12%(-7) = 5

Das obere heißt gewöhnlich Modulo.

krümelkacker

Bashar, da irrst du dich. C99 und C++11 schreiben bei der Ganzzahldivision das Runden in Richtung Null vor.

Bashar

Stimmt, da hat wohl das Wunschdenken überwogen. Hab den Satz gelöscht.