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 und eindeutig bestimmte Zahlen und gibt, für die
gilt. Die Zahlen und 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
[Bearbeiten | Quelltext bearbeiten]Wenn zwei natürliche Zahlen, der Dividend a und der Divisor b (ungleich 0), mit Rest dividiert werden sollen, also wenn
berechnet werden soll, so wird gefragt, wie man die Zahl a als Vielfaches von b und einem „kleinen Rest“ darstellen kann:
Hier ist c der so genannte Ganzzahlquotient und r der Rest. Entscheidende Nebenbedingung ist, dass r eine Zahl in 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
[Bearbeiten | Quelltext bearbeiten]- 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
[Bearbeiten | Quelltext bearbeiten]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
[Bearbeiten | Quelltext bearbeiten]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“ [
] (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
die Modulo-Funktion ist durch sie jedoch eindeutig definiert:
Ganze Zahlen
[Bearbeiten | Quelltext bearbeiten]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 .
Symmetrisch
[Bearbeiten | Quelltext bearbeiten]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“:
Dabei bezeichnet die Vorzeichenfunktion und 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
Die meisten Prozessoren berechnen die ganzzahlige Divison auf diese Weise.
Mathematisch
[Bearbeiten | Quelltext bearbeiten]Die symmetrische Definition hat den Nachteil, dass im Allgemeinen die Gleichung
nicht gilt, z.B.
- .
Um die Bedingung zu erfüllen, schlug Donald E. Knuth vor, bei der Divison „nach minus unendlich“ zu runden:
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
[Bearbeiten | Quelltext bearbeiten]Eine eindeutige Definition wird auch dadurch erreicht, dass der Rest immer positiv und kleiner als der Betrag des Divisors sein soll, also
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.
Implementierung in Computersystemen
[Bearbeiten | Quelltext bearbeiten]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
[Bearbeiten | Quelltext bearbeiten]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:
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.
Das Ersetzen der Modulo-Funktion durch eine bitweise UND-Maske
funktioniert ebenfalls nur bei einem positiven Dividend oder der euklidischen Definition.
Grundrechenarten modulo einer natürlichen Zahl
[Bearbeiten | Quelltext bearbeiten]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
[Bearbeiten | Quelltext bearbeiten]- Restklasse modulo 3:
- Restklasse modulo 5:
Verallgemeinerung: Reelle Zahlen
[Bearbeiten | Quelltext bearbeiten]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
[Bearbeiten | Quelltext bearbeiten]Bei der Division mit Rest für Polynome muss das als Divisor auftretende Polynom aus dem Polynomring eine Voraussetzung erfüllen: Der Leitkoeffizient von muss eine Einheit von sein (insb. ist nicht das Nullpolynom). Unter dieser Bedingung gibt es zu jedem eindeutig bestimmte Polynome mit
Ein Beispiel ist das folgende Polynom
Die Polynome und lassen sich durch Polynomdivision bestimmen.
Anwendung
[Bearbeiten | Quelltext bearbeiten]Programmierung
[Bearbeiten | Quelltext bearbeiten]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
[Bearbeiten | Quelltext bearbeiten]- 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
[Bearbeiten | Quelltext bearbeiten]- Kongruenz (Zahlentheorie)
- Hashfunktion und die dort genannten Verfahren
- Kleiner fermatscher Satz
- Satz von Euler
- Endlicher Körper
Literatur
[Bearbeiten | Quelltext bearbeiten]- 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
[Bearbeiten | Quelltext bearbeiten]- 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
[Bearbeiten | Quelltext bearbeiten]- ↑ 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