Modulo vs. Remainder in C#

Wer programmieren möchte kommt um Modulare Arithmetik oft nicht herum. Ob man aufwändige Berechnungen anstellen oder einfach nur den Ggt zweier Zahlen berechnen möchte. Doch was ist Modulo eigentlich, wie benutzt man es und warum macht es nicht immer das was man möchte? Im Folgenden möchte ich diese Frage beantworten und gleichzeitig eine neue Methode einführen um in Zukunft Verwirrung beim Coden zu vermeiden.

Wisst ihr noch damals in der Grundschule hat man uns regelmäßig Dinge vorenthalten, um unsere jungen Hirne nicht unnötig zu strapazieren. So hat man uns beispielsweise lange verschwiegen, dass zwischen zwei ganzen Zahlen noch unendlich viele andere Zahlen liegen.

Aus diesem Grund haben wir damals auch Dinge machen müssen wie z.B. das Dividieren mit Rest. Tja und unter dem Strich ist Modulo nichts Anderes als das. Lasst es uns an einem einfachen Beispiel betrachten. Man nehme zwei ganze Zahlen, hier 9 und 3. Dann ist:

9 mod 3 = 0

Gesprochen 9 modulo 3, ist das Ergebnis nichts Anderes als der Rest der sich bei der Division von 9 durch 3 ergibt, also 0. So würde sich z.B. für die zahlen 7 und 3 Folgendes ergeben.

7 mod 3 = 1

Im Klartext, bedeutet das, die 3 passt insgesamt 2 Mal in die 7 und dabei bleibt 1 als Rest. Wie in der Grundschule, oder? Viele Jahre später bekommt man dann aber eine aussagekräftige Definition des Modulo bzw. der Division mit Rest.

„Es seien zwei ganze Zahlen a und b mit b ≠ 0. So gibt es dazu immer zwei eindeutig bestimmbare Zahlen r und q mit a=qb+r, sodass gilt r=a mod b.“

Soweit die Lightvariante der Definition. Im Klartext bedeutet das für die Zahlen a=7 und b=3:

7 = 2 * 3 + 1

Dabei ist q = 2 und r = 1. Soweit kein Problem, doch was ist mit negativen Zahlen? Auch die hat man uns lange vorenthalten. Schauen wir doch mal was gängige Rechner uns für Modulo Operationen mit negativen Zahlen ausspucken. Hierzu nehmen wir die Zahlen -7 und 3, also -7 mod 3.

So liefert uns der gute, alte Windows Taschenrechner -1 als Ergebnis für diese Operation:

winCalc

Doch Google sagt das Ergebnis wäre 2:

googleCalc

Lassen wir uns den Modulo in C# mit dem Befehl -7%3 („%“ ist der „Modulo“-Operator in C#) berechnen, so erhalten wir wieder -1.

csharpMod

Wenn wir uns den Modulo auf Wolfram Alpha berechnen lassen, bekommen wir wieder 2 als Ergebnis.

csharpMod

Das ist verwirrend, warum erhalten wir nun unterschiedliche Ergebnisse für die scheinbar gleiche Rechnung?

Nun die Antwort liegt auf der Hand. Es existieren zwei unterschiedliche Varianten wie man den Modulo berechnen kann, die mathematische und die symmetrische Variante. Dabei wird das Ganze nicht einheitlich gehalten. Sprachen wie Ruby, Python und Perl benutzen die mathematische Variante, während Java, C, JavaScript und PHP die symmetrische Version benutzen. Deswegen ist es möglich, dass man sich seine eigene Modulo Funktion basteln muss um beide Optionen zu haben.

Zuerst sollte man klären worin eigentlich der Unterschied zwischen den beiden Varianten besteht. Nun das symmetrische „Modulo“ wird im englischen als Remainder (Rest) bezeichnet und liefert als Ergebnis, wie der Name sagt einen Rest. Nehmen wir an wir haben a = -5 und b=4, dann ergibt sich folgendes:

a % b = -5 % 4

a = -1 * 4 -1

a = -5 und r = -1

D.h. im Klartext, dass die 4, -1 Mal in die -5 passt und sich ein Rest von -1 ergibt, wie in der Grundschule. Somit ergibt sich für x mod 4 folgender Zahlenstrahl.

symmetrisch

Symmetrische Variante

Ich denke es sollte ersichtlich seit warum diese Variante, symmetrisch genannt wird. Außerdem erkennen wir, dass für den Remainder auch negative Ergebnisse zugelassen sind. Betrachten wir hingegen den Zahlenstrahl der sich für die mathematische Variante ergibt, so stellen wir fest, dass sich hier die Ergebnisse von links nach rechts immer weiter wiederholen.

mathem

Mathematische Variante

Was ist wenn wir jetzt beispielsweise einen C# Code schreiben und nicht den mitgelieferten %- bzw. den Restoperator benutzen sondern die mathematische Variante berechnen lassen wollen?

Nun wenn wir den Zahlenstrahl beider Varianten genauer betrachten fällt uns für -5 mod 4 folgendes auf:

a = -5 und b = 4

Symmetrisch: -5 % 4 = -1

Mathematisch: -5 % 4 = 3

-1 + 4 = 3

Das bedeutet, dass wir um die mathematische Variante zu berechnen einfach (a%b)+b rechnen müssen. Dabei ist % wieder der Operator für die Berechnung der symmetrischen Version.

Wie könnte so eine Methode nun aussehen?

//Die Methode bekommt a und b als Parameter übergeben und soll das "mathematische" Modulo berechnen.
private public int Modulo(int dividend, int divisor)
        {
            //Berechne den "symmetrischen" Rest
            int rest = dividend % divisor;

            if(rest < 0)
            {
                //Wenn das Ergebnis kleiner 0 ist addieren wir den Divisor um das Modulo zu berechnen
                return rest + divisor;
            }else
            {
                //Ist der Rest positiv, so ist der Rest auch das Ergebnis
                return rest;
            }
        }

Das wird zwar seinen Zweck erfüllen, man kann die Methode jedoch weiter vereinfachen:

private public int Modulo(int dividend, int divisor)
        {
            int rest = dividend % divisor;
            //In dieser Version der Methode wird die if/else-Abfrage durch den unten stehenden Code ersetzt. Macht aber im Prinzip das Gleiche.
            return rest < 0 ? rest + divisor : rest;
        }

That’s it folks. Nun könnt ihr in eurem C#-Code den %-Operator verwenden oder euch bei Bedarf das Modulo mit der Modulo()-Methode berechnen lassen.

Advertisements
Dieser Beitrag wurde unter .NET, Algorithmen, Beispiel, Beispiel, c#, Mathematik, Modulo, Programmierung, Remainder, Rest, Uncategorized abgelegt und mit , , , , , , , , , , verschlagwortet. Setze ein Lesezeichen auf den Permalink.

4 Antworten zu Modulo vs. Remainder in C#

  1. Pingback: Caesar Chiffre/Verschlüsselung in C# | RealityBites

  2. Pingback: Die Vigenère-Verschlüsselung in C# | RealityBites

  3. Pingback: Einführung in das Binärsystem am Beispiel der XOR Verschlüsselung in C# | RealityBites

  4. Pingback: Die Playfair Verschlüsselung in C# | RealityBites

Kommentar verfassen

Trage deine Daten unten ein oder klicke ein Icon um dich einzuloggen:

WordPress.com-Logo

Du kommentierst mit Deinem WordPress.com-Konto. Abmelden /  Ändern )

Google+ Foto

Du kommentierst mit Deinem Google+-Konto. Abmelden /  Ändern )

Twitter-Bild

Du kommentierst mit Deinem Twitter-Konto. Abmelden /  Ändern )

Facebook-Foto

Du kommentierst mit Deinem Facebook-Konto. Abmelden /  Ändern )

Verbinde mit %s