Modulo mit negativen Zahlen

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.