Benutzer:Bobbl/Division mit Rest

Die Division mit Rest oder der Divisionsalgorithmus ist ein mathematischer Satz aus der Algebra und der Zahlentheorie. Er besagt, dass es zu zwei Zahlen $n$ und $m\neq 0$ eindeutig bestimmte Zahlen $a$ und $b$ gibt, für die

n=a\cdot m+b\,,\quad 0\leq b<m

gilt. Die Zahlen $a$ und $b$ lassen sich durch die schriftliche Division ermitteln.

Die Division mit Rest ist auch für Polynome definiert. Die allgemeinste mathematische Struktur, in der es eine Division mit Rest gibt, ist der euklidische Ring.

Natürliche Zahlen

Wenn zwei natürliche Zahlen, der Dividend a und der Divisor b (ungleich 0), mit Rest dividiert werden sollen, also wenn

a:b\,

berechnet werden soll, so wird gefragt, wie man die Zahl a als Vielfaches von b und einem „kleinen Rest“ darstellen kann:

a=b\cdot c+r

Hier ist c der so genannte Ganzzahlquotient und r der Rest. Entscheidende Nebenbedingung ist, dass r eine Zahl in $\{0,\dots ,b-1\}$ ist. Hierdurch wird r eindeutig bestimmt.

Der Rest ist also die Differenz zwischen dem Dividenden und dem größten Vielfachen des Divisors, das höchstens so groß ist wie der Dividend. Ein Rest ungleich 0 ergibt sich folglich genau dann, wenn der Dividend kein Vielfaches des Divisors ist. Man sagt auch: Der Dividend ist nicht durch den Divisor teilbar, weshalb ein Rest übrigbleibt.

Beispiel

7:3 = 2, Rest 1, da 7 = 3×2 + 1 („drei passt zweimal in 7 und es bleibt eins übrig“ – der Rest ist also eins)
2:3 = 0, Rest 2, da 2 = 3×0 + 2
3:3 = 1, Rest 0, da 3 = 3×1 + 0

Bestimmung des Restes für spezielle Teiler

Häufig kann man den Rest an der Dezimaldarstellung ablesen:

bei Division durch 2: der Rest ist 1, wenn die letzte Ziffer ungerade ist, und 0, wenn die letzte Ziffer gerade ist
bei Division durch 3: der Rest ist gleich dem Rest, den die iterierte Quersumme bei Division durch 3 lässt
bei Division durch 5: der Rest ist gleich dem Rest, den die letzte Ziffer bei Division durch 5 lässt
bei Division durch 9 (auch Neunerrest genannt): der Rest ist die iterierte Quersumme oder 0, falls diese 9 ist
bei Division durch 10: der Rest ist die letzte Ziffer

Ähnliche, wenn auch etwas kompliziertere Regeln existieren für etliche weitere Teiler.

Modulo

Da bei der ganzzahlige Divison mit Rest immer zwei Ergebnisse geliefert werden, kann man sie auch in zwei Funktionen aufteilen. Die Funktion div liefert den Ganzzahlquotienten und die Funktion mod liefert den Rest. Letztere nennt man „Modulo“ [ˈmoːduloː] (lat. Modulus, Kasus Ablativ: „durch Maß“ oder auch „mit Maß“, somit Mehrzahl modulis).

Es gibt unterschiedliche Definitionen (siehe folgender Abschnitt) für die ganzzahlige Division

\operatorname {div} \colon \mathbb {Z} \times (\mathbb {Z} \setminus \{0\})\to \mathbb {Z} \ .

die Modulo-Funktion ist durch sie jedoch eindeutig definiert:

{\bmod {\colon }}\mathbb {Z} \times (\mathbb {Z} \setminus \{0\})\to \mathbb {Z} \ ,\quad (a,b)\mapsto a\;{\bmod {\;}}m:=a-(a\operatorname {div} b)\cdot b\ .

Ganze Zahlen

Erweitert man die natürlichen Zahlen um negative Zahlen, so ist die Definition der ganzzahligen Division nicht mehr eindeutig und man unterscheidet zwischen verschiedenen Definitionen. Unangetastet bleibt jedoch die Definition des Restes durch $r:=a-b\cdot c$ .

Symmetrisch

Intuitiv erwartet man, dass sich durch das Ändern der Vorzeichen die Beträge der Zahlen nicht ändern, nur die Vorzeichen. Außerdem erwartet man bei einem negativen Divident auch einen negativen Ganzzahlquotient, z.B.

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

Da die Definition für den Rest weiterhin gelten soll, muss bei einen negative Divisor folgendes gelten:

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

Bei der Berechnung von Ganzzahlquotient und Rest wird also zunächst so getan, als gäbe es keine Vorzeichen, die Vorzeichen werden werden erst am Schluss hinzugefügt. Wie bei der normalen Division ist das Vorzeichen des Ganzzahlquotienten ist positiv, wenn die Vorzeichen von Dividend und Divisor übereinstimmen und negativ, falls sie sich unterscheiden. Das Vorzeichen des Rests entspricht dem Vorzeichen des Dividenden.

Bei der Division werden die Stellen nach dem Komma einfach abgeschnitten, man spricht von einer „Rundung zur Null hin“:

a\,\operatorname {div} _{s}\,b:=\operatorname {sgn}(a)\operatorname {sgn}(b)\left\lfloor {\frac {|a|}{|b|}}\right\rfloor

Dabei bezeichnet $\operatorname {sgn}(\cdot )$ die Vorzeichenfunktion und $\lfloor \cdot \rfloor$ die Gaußklammer (die größte ganze Zahl, die kleiner oder gleich der Zahl in der Gaußklammer ist).

Diese Definition ist symmetrisch, d.h. es gilt

(-a)\operatorname {div} _{s}b=a\operatorname {div} _{s}(-b)=-(a\operatorname {div} _{s}b)

(-a)\;{\bmod {}}_{s}\;m=-(a\;{\bmod {}}_{s}\;m)

Die meisten Prozessoren berechnen die ganzzahlige Divison auf diese Weise.

Mathematisch

Die symmetrische Definition hat den Nachteil, dass im Allgemeinen die Gleichung

(a+kb)\;{\bmod {\;}}b=a\;{\bmod {\;}}b

nicht gilt, z.B.

(1-3)\;{\bmod {}}_{s}3=(-2)\;{\bmod {}}_{s}\;3=-2\neq 1=1\;{\bmod {}}_{s}\;3

.

Um die Bedingung zu erfüllen, schlug Donald E. Knuth vor, bei der Divison „nach minus unendlich“ zu runden:

a\,\operatorname {div} _{m}\,b:=\left\lfloor {\frac {a}{b}}\right\rfloor

Bei positivem Quotienten macht das keinen Unterschied, bei einem negativem ist das Resultat jedoch meist um eins niedriger:

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

Eine weitere Eigenschaft dieser Definition ist es, dass der Rest immer das gleiche Vorzeichen wie der Divisor hat.

Euklidisch

Eine eindeutige Definition wird auch dadurch erreicht, dass der Rest immer positiv und kleiner als der Betrag des Divisors sein soll, also

0\leq a\,{\bmod {}}_{e}\,b<b

Beispiel:

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

Raymond Boute ^[1], der diese Definition 1992 erstmals publizierte, argumentiert dass diese Definition die besten mathematischen Eigenschaften hat, z.B.

a\,\operatorname {div} _{e}\,(-b)=-(a\,\operatorname {div} _{e}\,b)

a\,{\bmod {}}_{e}\,(-b)=a\,{\bmod {}}_{e}\,b

Implementierung in Computersystemen

In Programmiersprachen ist die implementierte Variante nicht einheitlich. So verwenden Ruby, Perl und Python die mathematische Variante, wohingegen Java, JavaScript und PHP die symmetrische einsetzen, was besonders wichtig bei Portierungen ist. In C war die Implementierung bis C99 nicht festgelegt, um eine effektive Ausnutzung der Hardware zu garantieren. Teilweise bieten bestimmte Programmiersprachen auch beide Varianten an. In Ada liefert rem beispielsweise das symmetrische Ergebnis, mod hingegen das mathematische.

Obwohl die symmetrische Definition die schlechtesten mathematischen Eigenschaften hat ^[1], wird sie in den meisten Prozessoren eingesetzt. Es ist jedoch relativ einfach, die einzelnen Definitionen ineinander umzurechnen^[2].

Bit-Shift-Optimierung

Eine oft verwendete Optimierung in Compilern ersetzt ganzzahlige Divisionen durch logische Bitverschiebungen nach rechts (engl. logical shift right, lsr), sofern der Divisior eine Zweierpotenz ist:

a\operatorname {div} (2^{n})=a\operatorname {lsr} n

Strenggenommen ist dies aber nur bei einem positiven Dividend möglich. Es gibt zwar meist einen Befehl zur arithmetischen Rechtsverschiebung (engl. arithmetic shift right, asr), dessen Ergebnis stimmt aber nur dann überein, wenn die mathematische oder euklidische Definition angewendet wird. Im symmetrischen Fall gilt stattdessen z.B.

-3\operatorname {div} _{s}2=-1\quad \neq \quad -2=-3\operatorname {asr} 1

Das Ersetzen der Modulo-Funktion durch eine bitweise UND-Maske

a\,{\bmod {\,}}(2^{n})=a\,\operatorname {and} \,(2^{n}-1)

funktioniert ebenfalls nur bei einem positiven Dividend oder der euklidischen Definition.

Grundrechenarten modulo einer natürlichen Zahl

Ist der Divisor eine Primzahl, so kann man die aus den reellen Zahlen gewohnten Grundrechenarten mit anschließender Modulo-Berechnung anwenden und erhält einen sogenannten endlichen Körper.

Beispiele

Restklasse modulo 3: $(2\;{\bmod {\;}}3)+(2\;{\bmod {\;}}3)\;{\bmod {\;}}3=4\;{\bmod {\;}}3=1\;{\bmod {\;}}3$
Restklasse modulo 5: $(3\;{\bmod {\;}}5)\cdot (3\;{\bmod {\;}}5)\;{\bmod {\;}}5=9\;{\bmod {\;}}5=4\;{\bmod {\;}}5$

Verallgemeinerung: Reelle Zahlen

Sind a und b reelle Zahlen, b ungleich 0, dann kann man eine Division mit Rest folgendermaßen definieren: Der ganzzahlige Quotient c und Rest r im halboffenen Intervall [0, |b|) sind diejenigen (eindeutig bestimmten) Zahlen, die die Gleichung a = b · c + r erfüllen.

Auch hier gibt es die Alternativen, dem Rest dasselbe Vorzeichen wie b zu geben oder den betragskleinsten Rest zu wählen. Letztere Alternative entspricht der Rundung: Die Division mit Rest von a durch 1 liefert eine ganze Zahl c und eine reelle Zahl r mit Betrag kleiner oder gleich 0,5, die die Gleichung a = c + r erfüllen. Die Zahl c ist der auf ganze Zahlen gerundete Wert von a.

Es ist zu beachten, dass hierbei der Quotient nicht aus derselben Menge (der reellen Zahlen) genommen wird wie Divisor und Dividend.

Polynome

Bei der Division mit Rest für Polynome muss das als Divisor auftretende Polynom $f(x)$ aus dem Polynomring $R[x]$ eine Voraussetzung erfüllen: Der Leitkoeffizient von $f(x)$ muss eine Einheit von $R$ sein (insb. ist $f(x)$ nicht das Nullpolynom). Unter dieser Bedingung gibt es zu jedem $g(x)\in R[x]$ eindeutig bestimmte Polynome $q(x),r(x)\in R[x]$ mit

g(x)=q(x)f(x)+r(x)\quad {\text{und}}\quad \operatorname {grad} (r)<\operatorname {grad} (f)

Ein Beispiel ist das folgende Polynom

2x^{2}+4x+5=(2x+2)(x+1)+3\in \mathbb {R} [x]

Die Polynome $q(x)$ und $r(x)$ lassen sich durch Polynomdivision bestimmen.

Anwendung

Programmierung

Die Division mit Rest (Modulo) wird in der Programmierung relativ häufig verwendet. Die Syntax ist dabei die eines Operators. Mit mod kann geprüft werden, ob eine Zahl gerade ist: if ( (x mod 2) == 0), dann ist x gerade. Modulo kann man auch nutzen, wenn man in einer Schleife lediglich bei jedem x-ten Schleifendurchlauf einen speziellen Programmcode ausführen will. Auch bei vielen Berechnungen und Algorithmen ist er sinnvoll einsetzbar. Allgemein kann man mit mod prüfen, ob eine Zahl durch eine andere genau teilbar ist: nur dann ist der Modulo gleich Null. Des Weiteren muss man in der Programmierung oft auf ganze Vielfache einer Zahl ergänzen (z. B. 4 Bytes) und bekommt durch den Modulo heraus, wie viele „Pad-Bytes“ noch fehlen. Durch die Funktion divmod werden Ganzzahlquotient und Rest ausgewertet.

Beispiel: Man programmiert eine Uhr und hat die Zeit als Sekundenwert seit 0 Uhr gegeben. Dann kann man den Sekundenwert Mod 3600 berechnen. Ist dieser gleich 0, so weiß man, dass eine volle Stunde angefangen hat. Diese Information kann man nutzen, um z. B. ein akustisches Signal (Gong zur vollen Stunde) auszulösen. Mit der Berechnung Sekundenwert Mod 60 erhält man die Sekunde der aktuellen Minute, die oftmals von Digitaluhren als letzte zwei Stellen angezeigt werden.

Weitere Anwendungen

Berechnung der Prüfziffer der Internationalen Standardbuchnummer
Prüfsummen-Formel Luhn-Algorithmus zur Bestätigung von Identifikationsnummern wie Kreditkartennummern und kanadische Sozialversicherungsnummern
Kalenderberechnung (die relativ komplizierte Berechnung des Osterdatums)
Bei der International Bank Account Number (IBAN)
In der Kryptografie, beim Diffie-Hellman-Schlüsselaustausch oder beim RSA-Kryptosystem

Siehe auch

Kongruenz (Zahlentheorie)
Hashfunktion und die dort genannten Verfahren
Kleiner fermatscher Satz
Satz von Euler
Endlicher Körper

Literatur

Kristina Reiss, Gerald Schmieder: Basiswissen Zahlentheorie. Eine Einführung in Zahlen und Zahlenbereiche. Springer-Verlag, Berlin u. a. 2005, ISBN 3-540-21248-5.
Peter Hartmann: Mathematik für Informatiker. Ein praxisbezogenes Lehrbuch. 4. überarbeitete Auflage. Vieweg, Wiesbaden 2006, ISBN 3-8348-0096-1, S. 62, (online).
Albrecht Beutelspacher, Marc-Alexander Zschiegner: Diskrete Mathematik für Einsteiger. Mit Anwendungen in Technik und Informatik. Vieweg, Wiesbaden 2007, ISBN 978-3-8348-0094-7, S. 65, (online).

Weblinks

Modulo online berechnen
Java ist auch eine Insel: Der Restwert-Operator %
Ganzzahlige Division und der Rest
ETH Zürich:Ganzzahlige Division und Modulo-Funktion (PDF-Datei; 83 kB)
Division mit Rest - der heimliche Hauptsatz der Algebra (PDF-Datei; 86 kB)

Einzelnachweise

↑ ^a ^b Boute, Raymond T. The Euclidean definition of the functions div and mod. ACM Transactions on Programming Languages and Systems (TOPLAS), 1992, 14. Jg., Nr. 2, S. 127-144.
↑ Leijen, Daan: Division and Modulus for Computer Scientists

[Boute1992-1] Boute, Raymond T. The Euclidean definition of the functions div and mod. ACM Transactions on Programming Languages and Systems (TOPLAS), 1992, 14. Jg., Nr. 2, S. 127-144.

[2] Leijen, Daan: Division and Modulus for Computer Scientists

[1]

[2]