Die Ganzzahlige Division und der Rest
Die ganzzahlige Division mit Rest wird bereits im Grundschulunterricht behandelt: Teilt man eine Zahl durch eine andere Zahl, so bleibt neben einem ganzzahligen Ergebnis ein Rest (der auch Null sein kann). So ist Sieben geteilt durch Drei gleich Zwei Rest Eins. Der Rest dieser Division von Sieben geteilt durch Drei wird auch als „Sieben modulo Drei“ bezeichnet. „Sieben modulo Drei“ ist also der Rest, der bei der Division von Sieben durch Drei übrig bleibt, nämlich Eins.
Wird eine Zahl z durch eine Zahl n geteilt, dann kann man das Ergebnis wieder durch zwei ganze Zahlen darstellen, nämlich das Ergebnis q der „ganzzahligen Division“ und den „Rest“ r. Man schreibt auch z : n = q Rest r und es gilt: q · n + r = z.
Die ganzzahlige Division wird auch als „div“ geschrieben, um sie von der normalen Division zu unterscheiden, die Operation zur Bestimmung des Restes wird auch Modulo-Operation genannt und mod geschrieben.
Es gilt mit diesen Bezeichnungen also: q =( z div n ), r = (z mod n ) und ( z div n ) · n + (z mod n ) = z, so ist 7 div 3 gleich 2 und 7 mod 2 gleich 1.
Die Menge der ganzen Zahlen mit gleichem Rest bei Division durch eine ganze Zahl n bezeichnet man auch als eine Restklasse mod n. So bilden beispielsweise die Zahlen 2, 12, 22, 32 u.s.w. eine Restklasse modulo 10. Man sagt auch, sie seien kongruent modulo 10.
Anwendungsbeispiele
Beginnt man mit einer Zeitzählung um 0 Uhr am Neujahrestag, so sind um 16 Uhr am 2. Januar bereits 40 Stunden vergangen. Eine normale Digitaluhr zeigt aber immer nur den Rest an, der sich bei der Division der seitdem vergangenen Stunden durch 24 ergibt. Dazu sagt man auch, die Digitaluhr zeigt die Stunden modulo 24 an. Eine Analoguhr zeigt die Stunden auf einem Ziffernblatt sogar nur modulo 12 an. Auf solch einer Analoguhr kann man beispielsweise ablesen, daß es zwei Stunden nach 11 Uhr 1 Uhr ist, also mit anderen Worten, daß modulo 12 die Summe 11 + 2 gleich 1 ist.
Kreisdarstellung von Stunden auf einer Analoguhr
+ 2
11 _____ =1
.-' 0 '-.
.' 11 1 '.
/10 2\
; ;
|9 3|
; ;
\8 4
'. 7 5 .'
'-.__6__.-'
Geschieht das Rechnen auch auf diese Weise, so spricht man von einer Modulo-Arithmetik oder einem Restklassensystem. Das Ergebnis der Restklassenaddition modulo n erhält man aus der normalen Addition durch eine nachfolgende Modulo-n -Operation.
20 + 20 ist modulo 24 beispielsweise gleich 16, denn 20 + 20 ist 20 + 4 + 16 und 20 + 4 ergibt modulo 24 den Wert 0. Man zählt modulo 24 also 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 0, 1, 2, 3, 4, 5, 6, u.s.w.
Da nicht nur Stunden im Alltag mit Modulo-Arithmetik behandelt werden, ergibt sich die Notwendigkeit dieser Art des Rechnens in formalen Sprachen auch aus verschiedenen anderen Anwendungsgebieten.
Entsprechend der Darstellung von Stunden auf einem Ziffernblatt kann man sich die Modulo-Arithmetik als Rechnen auf einem Kreis veranschaulichen, bei dem Winkel addiert oder subtrahiert werden. Geht man in eine bestimmte Richtung, kommt man irgendwann einmal wieder dort an, wo man losgegangen ist. (Der Stundenzeiger kommt nach 12 Stunden wieder bei der „12“ ab.) Die normale Arithmetik entspricht dabei dem Rechnen auf einer Gerade, bei dem Strecken addiert und subtrahiert werden. Auf einer Geraden kann man unendlich lange in eine Richtung gehen.
Da es in unserer Welt zwar Kreise mit endlichem Radius gibt, aber keine unendlich langen Geraden, ist die Modulo-Arithmetik eigentlich viel natürlicher. Daher findet sich Modulo-Arithmetik mit ganzen Zahlen auch auf realen Rechenanlagen mit Speicherzellen endlicher Größe. Die Schul-Arithmetik kann auch als Arithmetik „modulo unendlich“ verstanden werden und ist so in unserer Welt mit realen Systemen (Speicherzellen) gar nicht durchführbar, da diese immer nur eine begrenzte Menge verschiedener Werte, also nur Zahlen bis zu einer bestimmten Größe, darstellen können.
Soll eine Zahl in einem bestimmten Zahlensystem dargestellt werden, so verwendet man ebenfalls die ganzzahlige Division und den Rest. So hat die Zahl 14 im Achtersystem die Darstellung "16", die man als Ergebnis der ganzzahligen Division durch 8 (erste Ziffer "1") und als Rest der Division durch 8 (zweite Ziffer "6") ermitteln kann. (Bei größeren Zahlen als 63 muß dieses Verfahren noch etwas erweitert werden.)
Auch bei der Berechnung von Pseudozufallszahlen spielt die Modulo-Arithmetik eine Rolle, die sich daraus ergibt, daß bei der Wiederholung bestimmter Rechnungen die letzte Ziffer einer Zahlendarstellung oft mehr oder weniger „zufällig“ zu sein scheint. Das ist vergleichbar mit einer Kugel beim Roulette, die eine zeitlang immer wieder um einen Zahlenkreis läuft. Würde man sie entlang einer geraden Strecke laufen lassen, wäre der ungefähre Endpunkt der Bewegung bei ungefähr gleicher Art des Wurfes eher vorhersehbar und erschiene weniger zufällig.
Um zu prüfen, ob eine Zahl richtig übermittelt wurde, kann man auch noch eine Prüfsumme aller Ziffern (Quersumme) übermitteln und mit der beim Empfänger errechneten Prüfsumme vergleichen. Will man eine Prüfziffer aus einer Zahl bilden, so kann man die Quersumme aber nicht mehr verwenden, wenn diese auch mehr als eine Ziffer haben könnte. Aus der Quersumme kann man aber durch eine Modulo-10-Operation eine als Prüfziffer geeignete einzelne Ziffer erhalten.
Werden Felder in einem rechteckigen Schema aus (waagerechten) Zeilen und (senkrechten) Spalten durchnumeriert, so ergibt sich die Zeile einer Zahl als Ergebnis der ganzzahligen Division durch die Zahl der Spalten und die Spalte der Zahl als Ergebnis der Operation „Zahl modulo der Spaltenanzahl“.
Ein rechteckiges Zahlenschema [Abbildung]
0, 1, 2, 3, 4, 5, 6 Spalte
0 0, 1, 2, 3, 4, 5, 6,
1 7, 8, 9, 10, 11, 12, 13,
2 14, 15, 16, 17, 18, 19, 20,
3 21, 22, 23, 24, 25, 26, 27,
4 28, 29, 30, 31, 32, 33, 43,
5 35, 36, 37, 38, 39, 40, 41,
6 42, 43, 44, 45, 46, 47, 48,
7 49, 50, 51, 52, 53, 54, 55,
8 56, 57, 58, 59, 60, 61, 62,
9 63, 64, 65, 66, 67, 68, 69,
Zeile u.s.w.
So kann man bei einem Zahlenschema mit 7 Spalten ausrechnen, daß sich der Wert 37 in Zeile 5 (37 div 7 = 5) und in Spalte 2 (37 mod 7 = 2) befindet. Das klappt allerdings nur dann gut, wenn man immer mit 0 zu zählen beginnt.
Das Auffüllen der siebenstelligen Zeilen des obigen Schemas mit Werten kann man auch mit dem Auffüllen von Packungen vergleichen: Wenn man beispielsweise Eierkartons mit Platz für jeweils 7 Eier hat, dann kann man das obige Schema verwenden, um zu ermitteln, wie viele Kartons man für eine bestimmte Zahl von Eiern braucht und wieviele Eier im letzten Karton sind, die Details des Ableseverfahrens sind dem Leser überlassen. Entsprechend kann man die ganzzahlige Division bzw. die Modulo-Operation für solche Berechnungen verwenden.
Wenn Zeichen mit Codes von 0 bis 255 verschlüsselt werden sollen, so könnte eine einfache (und nicht besonders sichere) Technik darin bestehen, zu jedem Code 37 zu addieren. Doch dadurch ergäben sich zunächst auch Werte über 255, die nicht mehr verwendet werden können, falls nur eine Zahl aus dem Bereich von 0 bis 255 als Codewert zulässig ist. Hier kann man dann statt dessen 37 modulo 256 addieren und erhält so wieder Werte aus dem Bereich von 0 bis 255. Die dadurch beschrieben Abbildung ist weiterhin umkehrbar, so daß zur Entschlüsselung einfach wieder 37 modulo 256 subtrahiert werden kann.
Ein Register (Wertspeicher) eines Prozessors kann nur endlich viele verschiedene Werte speichern. Wenn sich bei Rechenoperationen mit nichtnegativen ganzen Zahlen ein Wert ergibt, der zu groß ist, um noch dargestellt werden zu können, dann ist das Ergebnis der Rechnung oft modulo der Zahl der möglichen Werte zu verstehen. Wenn ein Wertspeicher beispielsweise ganzzahlige Werte von 0 bis 32767 aufnehmen kann, dann wird das Ergebnis von 20000 + 20000 darin manchmal als 7232 gespeichert (20000 + 20000 = 32768 + 7232). Natürlich ist dabei ein Teil der Information über das normale Ergebnis der Rechnung 40000 verloren gegangen.
Die möglichen Werte eines Registers lassen sich daher auch als Kreis darstellen, etwa für ein Register mit Werten von 0 bis 255.
Kreisdarstellung von Registerwerten
255_0_1 2
254.-' '-.3
.' '.4
/ \ u.s.w.
; ;
| |
; ;
\ /
'. .'
'-._____.-'
Auch für vorzeichenbehaftete 8-Bit-Werte mit Zweierkomplement ist eine Kreisdarstellung möglich.
Kreisdarstellung von Registerwerten mit Vorzeichen
-1__0_1 2
-2.-' '-.3
.' '.4
/ \ u.s.w.
; ;
| |
u.s.w.; ;
\ /
-125 '. .' 125
-126 '-._____.-' 126
-127 -128 127
Eine Addition einer positiven Zahl entspricht bei der Kreisdarstellung eine Drehung im Uhrzeigersinn, eine Addition einer negativen Zahl entspricht einer Drehung im Gegenuhrzeigersinne.
Übungen
- Rest
- Zwölf geteilt durch fünf ist … Rest …?
- Wertebereich
- Wie groß kann der Rest der Division durch sieben mindestens und höchstens sein?
- Teilbarkeit
- Welcher Rest bleibt bei der Division einer geraden Zahl durch zwei übrig? Welche Rest bleibt allgemein übrig, wenn eine durch i teilbare Zahl durch i geteilt wird? Durch welche Bedingung kann man also prüfen, ob eine Zahl durch eine andere Zahl i teilbar ist?
Durch die Grundrechenarten sowie div und mod kann ein Wert mit Hilfe anderer Werte als Term geschrieben werden. Beispielsweise ist der Wert w eines Registers mit Modulo-256-Arithmetik nach Berechnung von "100 * 100" gleich "( 100 · 100 )mod 256", also gilt dann die Gleichheit "w = ( 100 · 100 )mod 256". („Gleichheit“ bedeutet hier eine Aussage über die Gleichheit zweier Terme.)
In dieser und einigen folgenden Aufgaben sollen Gleichheiten in ähnlicher Weise notiert werden, es wird dann eine Schreibweise, wie "w = … 100 …" vorgegeben und der genaue Term auf der rechten Seite soll formuliert werden.
Wenn die Aufgabe beispielsweise lautet: Ein Rechteck hat die Breite "10" und die Höhe "20 ", geben Sie die Fläche "f " als "f = … 10 … 20 …" an, dann ist eine richtige Antwort "f = 10 · 20". Die Gleichheit sollte auch dann noch stimmen, wenn ein Zahlenwert sich ändert und entsprechend in der Gleichheit geändert wird. Ist die Höhe beispielsweise "30", dann ergibt sich die Gleichheit "f = 10 · 30" für die Fläche.
- Stunden
- Welche Uhrzeit u (im 24-Stunden-Darstellung) ist "1000" Stunden nach Mitternacht? Gesucht ist eine Gleichheit "u = … 1000 …" für "u ", auf deren rechter Seite ein Term mit dem Numeral "1000" vorkommt, in dem die Grundrechenarten, Klammern, der Operationen "div" und der Operator "mod" verwendet werden können.
- Fuhren
- Ein Taxi kann höchstens drei Touristen vom Hotel zum Aussichtsturm transportieren. Drücken Sie mit Hilfe der Grundrechenarten, Klammern, sowie div und mod die Zahl t der Taxis aus, die für 10 Touristen benötigt werden. Also, t = … 10 … .
- Tage
- Wenn der 22. Tag eines Jahres ein Mittwoch ist, was für ein Wochentag w ist dann der 193. Tag desselben Jahres? (Als Lösung reicht auch ein Term, der Grundrechenarten sowie div und mod verwenden kann, er muß nicht als Zahl ausgerechnet werden.) Der Wochentag w sollte als Zahl angegeben werden, so daß Mittwoch durch die Zahl 0 und Dienstag durch die Zahl 6 dargestellt wird, also w = … 193 … .
- trunc oder floor? *
- Die größte ganze Zahl kleinergleich x wird auch floor( x ) geschrieben (es handelt sich also um die ganze Zahl direkt „unter“ x ). Der ganzzahlige Anteil von x wird auch trunc( x ) geschrieben (es handelt sich hierbei um die Zahl, die man erhält, indem man alle Stellen nach dem Komma entfernt). ( x div y ) wird in manchen Programmiersprachen nach Knuth als floor( x / y ) und in anderen nach Wirth als trunc( x / y ) definiert (‘‘truncation toward zero ’’, z.B. in ISO Fortran, ISO/IEC 1539:1991 oder in ISO/IEC 9899:1999 (E) ). Mit Hilfe der oben verwendeten Gleichung q · n + r = z wird dadurch dann indirekt auch der Rest definiert. Finden Sie zwei Zahlen, für die sich die Werte der ganzzahligen Division nach den beiden Definitionen unterscheiden.