Thomas Kramer

IT-COW | Januar 2011

Modulo-Rechnung

By Administrator at Januar 31, 2011 21:36
Filed Under: Studium

Ein weiterer Schwerpunkt im Grundlagen-Fach war die Modulo-Rechnung - mittels dieser wird der Rest einer Division errechnet.

 

Normale Modulo-Rechnung

 

Beispielrechnung: 123456 mod 97

 

Zunächst wird der Abstand des Teilers zur nächsten 10er-Potenz berechnet, bei dieser Beispielrechnung also 100-97=3.

 

Der Teiler 97 hat zwei Stellen, die ursprüngliche Zahl wird demnach nach 2er-Stellen folgendermaßen aufgeteilt:


   12 *3 *3  = 108 => 108 ist größer 97, also wird 108 mod 97 gerechnet = 11

+  34 *3     = 102 => 102 ist größer 97, also wird 102 mod 97 gerechnet = 5

+  56

------------------

=  72 (11+5+56)

 

Wenn bei den Teilergebnissen eine Zahl kleiner als der Teiler herauskommt, muss die Modulo-Rechnung als Zwischenschritt nicht gemacht werden und es wird direkt mit dieser Zahl weitergerechnet.

 

Modulo-Rechnung bei hohen Potenzen

 

Beispielrechnung: 5^66 mod 97

 

Zunächst wird der Exponent in eine binäre Zahl umgewandelt, bei 66 also 1000010. Dann wird die erste Ziffer dieser Zahl gestrichen, so das 000010 übrigbleibt. Diese Zahl hat 6 Ziffern, es sind also 6 Teilrechnungen nötig.

 

Bei jeder Teilrechnung wird nach 0 und 1 unterschieden. Bei jeder 0 muss das Ergebnis der vorherigen Rechnung einfach nur quadriert werden, bei jeder 1 wird das Ergebnis der vorherigen Rechnung quadriert und das Ergebnis mit der Basiszahl multipliziert.

 

Am besten schreibt man sich das so auf und streicht bei jeder Teilrechnung einen Teil weg:

 

((((((5^2)^2)^2)^2)^2*5)^2)

=((((((25)^2)^2)^2)^2*5)^2)

 

25^2=625. 625 ist größer als 97, also wird 625 mod 97 gerechnet = 43.

 

(((((43)^2)^2)^2*5)^2)

 

43^2=1849. 1849 ist größer als 97, also wird 1849 mod 97 gerechnet = 6.

 

((((6)^2)^2*5)^2)

 

6^2=36, 36 ist kleiner als 97, demnach muss keine Modulo-Rechnung ausgeführt werden.

 

(((36)^2*5)^2)

 

36^2=1296, 1296 ist größer als 97, also wird 1296 mod 97 gerechnet = 35. Zweiter Schritt: 35*5 ergibt 175. 175 ist größer als 97, demnach wieder Modulo-Rechnung, Ergebnis = 78.

 

((78)^2)

 

78^2=6084, 6084 ist größer als 97, also wird 6084 mod 97 gerechnet = 70. Dies ist das Endergebnis der gesamten Modulo-Rechnung.

 

Fazit

 

Beide Verfahren sind recht einfach. Zum Überprüfen am besten den Windows-Rechner benutzen, dieser besitzt einen Mod-Button. OpenOffice Calc kann theorethisch auch verwendet werden, aber bei hohen Potenzen versagt die REST()-Funktion in Calc und gibt immer 0 aus.

 

In Programmiersprachen wird übrigens der Modulo-Operator % verwendet, dieser Operator ist ganz praktisch wenn bei Schleifendurchläufen nur bei jedem x. Durchlauf eine bestimmte Aktion erfolgen soll - oder auch wenn man herausfinden will ob eine Zahl ohne Rest durch 2 teilbar ist, also gerade ist.

 

In Wikipedia gibt es natürlich auch einen Artikel zu dem Thema, aber ich denke das meine obige Erklärung schneller aufzunehmen ist wenn man sich noch nicht mit der Materie befasst hat.

 

Ein Teil der Erklärung in Wikipedia zum zweiten Modulo-Verfahren ist unter dem Stichwort Binäre Exponentiation zu erreichen, dies ist allgemein ein Verfahren zum schnellen Potenzieren. Bei der Modulo-Rechnung mit hohen Potenzen wurde demnach die binäre Exponentiation mit der Modulo-Rechnung kombiniert.

 

Mit dem Chinesischen Restsatz soll sich die Modulo-Rechnung bei hohen Potenzen noch weiter verkürzen lassen, damit muss ich mich noch weiter beschäftigen. In diesem Link gibt es eine interessante Rechenaufgabe zu dem Thema.

 

Ergänzung 8.3.2011: Mit der Modulo-Rechnung kann man beispielsweise auch die Anzahl (bestimmter) Ziffern einer Zahl berechnen. Man nimmt eine Dezimalzahl als Eingabe, bestimmt den Rest der Modulo-Division mit 10 und das Ergebnis ist immer die letzte Ziffer der Zahl. Dann teilt man den Ausgangswert durch 10 und behält den Vorkommaanteil davon, indem man einfach das Ergebnis der Division in einer Integer-Variablen speichert. Diesen Wert übernimmt man dann als neuen Ausgangswert usw. usf.

 

Das lässt man in einer Schleife solange durchlaufen, wie der Ausgangswert größer Null bleibt. Das hat etwas mit dem Stellenwertsystem zu tun, mit dem wir rechnen.

 

Ergänzung 08.11.2011: Wenn der Divisor eine Zweiterpotenz ist kann die Modulo-Operation performanter auch durch ein bitweises & erreicht werden. Beispiel:

 

int a=16;

int b=4;     // divisor

int c= a & (b-1);

 

Weitere Links:

 

  • Zeichnen von Binärbäumen mithilfe des Reingold-Tilford-Algorithmus: Link
  • Lineares Sondieren bei Hashing-Tabellen: Link
  • Beim Rabin-Karp-Algorithmus für das String-Matching: Link

 

Tag-Wolke

Monats-Liste