Als Python-Programmierer genießen wir einen ganz großen Vorteil, der Dir, wenn Du (noch) keine anderen Programmiersprachen kennst, vielleicht gar nicht bewusst ist. – Du kannst mit Python sehr große Ganzzahlen verarbeiten, ohne Dir Gedanken über die Anzahl der Bits zu machen, die diese im Binärcode belegen.
Ein handelsüblicher Prozessor, wie er in unseren PCs und Laptops verbaut ist, hat 64 Bit. Das heißt, er kann ganze Zahlen verarbeiten, deren Bitmuster aus 64 Bits bestehen.
Zur Motivation betrachten wir zwei gleichartige Programme, welche die Fakultäten der Zahlen von 0 bis einschließlich 30 berechnen sollen. Ich habe die Programme in Python und Free Pascal geschrieben. Statt Free Pascal hätte ich auch C, Java oder eine andere Programmiersprache, neben Python, verwenden können. Free Pascal hat jedoch den Vorteil, für Microsoft Windows, macOS und Gnu/Linux gleichermaßen frei verfügbar und leicht installierbar zu sein. So kannst Du die Beispiele einfach am eigenen Computer nachvollziehen.
Hier der Python-Code:
#!/usr/bin/env python3
# -*- coding: utf-8 -*-
def fact(x: int) -> int:
f = 1
for i in range(1, x + 1):
f = f * i
return f
# Funktionstest
if __name__ == '__main__':
for n in range(31):
print(f"{n:2d}: {fact(n)}")
Und das Gleiche in Grün, nur eben in Free Pascal:
program PasFakultaet;
function fact(x: integer): int64;
var
i: integer;
f: int64;
begin
f := 1;
for i:= 1 to x do
f := f * i;
fact := f
end;
var
i, n: integer;
begin
n := 30;
for i:= 0 to n do
writeln(i:2, ': ', fact(i));
end.
Auch ohne Pascal-Kenntnisse, wird Dirdie Übereinstimmung der Anweisungen auffallen. In der Tat sind die beiden Programme inhaltlich auch gleich. Ein wesentlicher Unterschied besteht allerdings darin, dass Variablen in Pascal mit einem Datentyp vereinbart werden müssen, bevor sie genutzt werden können. integer steht dabei für eine Vorzeichen behaftete Ganzzahl mit 32 Bit. int64 ist ebenso eine solche Ganzzahl, besitzt aber 64 Bit. Das heißt, in Bezug auf einen 64-Bit-Prozessor, dass dieser ausgenutzt wird.
Lassen wir diese Programme laufen und betrachten die jeweiligen Ausgaben. Ich habe sie hier, um einen direkten Vergleich zu ermöglichen, nebeneinander gestellt.
PyFakultaet.py PasFakultatet.pas -------------- ----------------- 0: 1 0: 1 1: 1 1: 1 2: 2 2: 2 3: 6 3: 6 4: 24 4: 24 5: 120 5: 120 6: 720 6: 720 7: 5040 7: 5040 8: 40320 8: 40320 9: 362880 9: 362880 10: 3628800 10: 3628800 11: 39916800 11: 39916800 12: 479001600 12: 479001600 13: 6227020800 13: 6227020800 14: 87178291200 14: 87178291200 15: 1307674368000 15: 1307674368000 16: 20922789888000 16: 20922789888000 17: 355687428096000 17: 355687428096000 18: 6402373705728000 18: 6402373705728000 19: 121645100408832000 19: 121645100408832000 20: 2432902008176640000 20: 2432902008176640000 21: 51090942171709440000 21: -4249290049419214848 22: 1124000727777607680000 22: -1250660718674968576 23: 25852016738884976640000 23: 8128291617894825984 24: 620448401733239439360000 24: -7835185981329244160 25: 15511210043330985984000000 25: 7034535277573963776 26: 403291461126605635584000000 26: -1569523520172457984 27: 10888869450418352160768000000 27: -5483646897237262336 28: 304888344611713860501504000000 28: -5968160532966932480 29: 8841761993739701954543616000000 29: -7055958792655077376 30: 265252859812191058636308480000000 30: -8764578968847253504
Viele Menschen vertrauen blind auf die Rechenfähigkeiten unserer Computer – dafür wurden/werden sie schließlich gebaut. Dennoch sollte jedem auf den ersten Blick klar sein, dass das Pascal-Programm falsche Ergebnisse ausgibt. Bis 20! stimmen Python und Pascal überein. Bei 21! wirft Pascal jedoch ein negatives Ergebnis aus. Das kann nicht sein. Eine Fakultät ist immer positiv.
Die vordergründige Ursache für den bei Pascal beobachteten Fehler ist einfach. Ganze Zahlen, die Vorzeichen besitzen, haben bei 64 verfügbaren Bits einen Wertebereich von -9.223.372.036.854.775.808 bis 9.223.372.036.854.775.807. – Zwecks leichterer Lesbarkeit habe ich Tausenderpunkte eingefügt. 20! ist offensichtlich noch kleiner als der zulässige Wertebereich:
Wert Kommentar ---- --------- 2.432.902.008.176.640.000 (20!) 9.223.372.036.854.775.807 (max. Wert von 64 Bit mit Vorzeichen) 51.090.942.171.709.440.000 (21!)
Dem interessierten Betrachter drängen sich sofort drei Fragen auf:
- Warum meldet Pascal keinen Fehler?
- Wie falsch sind die Ergebnisse von Pascal?
- Warum rechnet Python richtig?
Hinweis: Pascal ist übrigens keine schlechte Programmiersprache. Du würdest, je nach Datentypvereinbarung, in C, Java, oder eben auch den meisten anderen Programmiersprachen, ähnliche Ergebnisse erhalten.
Modulare Arithmetik
Um die folgenden Ausführungen übersichtlich zu halten, stellen wir uns vor, unser Prozessor hätte lediglich 8 statt 64 Bit. Das bedeutet dann, 256 Ganzzahlen im Wertebereich von -128 (10000000) bis 127 (01111111) verarbeiten zu können. Beachte: 2er-Komplement für die Darstellung negativer Zahlen.
Dezimalzahl Bitmuster ----------- --------- 127 01111111 126 01111110 125 01111101 ... 3 00000011 2 00000010 1 00000001 0 00000000 -1 11111111 -2 11111110 ... -64 11000000 ... -124 10000100 -125 10000011 -126 10000010 -127 10000001 -128 10000000
Wir betrachten die folgende Berechnung auf Ebene der Bitmuster, die die jeweiligen Zahlen haben.
dezimal Bitmuster ------- --------- 70 01000110 + 42 00101010 = 112 01110000
Ok! – Operanden und Ergebnis sind mit 8 verfügbaren Bits darstellbar. Was passiert jedoch jetzt?
dezimal Bitmuster ------- --------- 108 01101100 + 84 01010100 = 192 (-64) 11000000
Wir haben das Problem, dass das Ergebnis, obgleich die Operanden mit 8 Bits darstellbar sind, nicht mehr als positive Zahl mit 8 Bits darstellbar ist. Dafür stehen nur 7 Bits zur Verfügung. Das Setzen des Vorzeichen-Bits hat zur Folge, dass wir mit unserem 8-Bit-Prozessor, unter Berücksichtigung des Vorzeichens, ein negatives Ergebnis erhalten. – Wir haben eine Arithmetic Overflow produziert. Das ist das, weshalb das obige Pascal-Programm falsch rechnet, eine Überschreitung des zulässigen Wertebereichs.
Wenn Dich das Vorzeichen verwirrt, lass uns eine weitere Vereinfachung annehmen. Wir betrachten nur ganze Zahlen, die nicht negativ sind. Dann erhalten wir einen Wertebereich von 0 (00000000) bis 255 (11111111). Wir produzieren wiederum einen Overflow.
dezimal Bitmuster ------- --------- 208 11010000 + 84 01010100 = 292 (36) 100100100
Statt 292 würde unser 8-Bit-Prozessor jetzt 36 ausgeben. Weil das Ergebnis 9 Bits benötigt, wird das vordere und höchstwertige Bit nicht beachtet. Der Rest der verbleibenden Bits ergibt den dezimalen Wert 36.
Was Du hier beobachtest, hat Carl Friedrich Gauß bereits vor mehr als 200 Jahren entwickelt. Es nennt sich modulare Arithmetik. Damals gab es freilich noch keine Computer. Die modulare Arithmetik spielt jedoch auch heute noch eine große Rolle in der Zahlentheorie, eine Disziplin der Mathematik, oder der modernen Kryptologie. Sie ist definitiv nicht auf die Erläuterung von (vermeintlichen) Rechenfehlern begrenzt. Warum ich „vermeintlich“ in Klammern gesetzt habe? – Nun, im Sinne der modularen Arithmetik ist das Ergebnis korrekt.
Modulare Arithmetik im Alltag – die Uhr
Stell Dir das Zifferblatt einer analogen Uhr vor. Ein Freund besucht Dich um 11:00 Uhr am Vormittag. Er bleibt 2 Stunden. Er verlässt dich also um 13:00 Uhr. Dazu sagen wir in der Alltagssprache: „Er ging um 01:00 Uhr nachmittags“.
Ganz unbewusst haben wir eine Umrechnung vorgenommen. Wir haben 13 ganzzahlig durch 12 geteilt. Der Rest 1 ist die Uhrzeit, die wir verkünden, wenn wir sagen: „Er ging um 01:00 Uhr nachmittags“.
Unser 8-Bit-Prozessor ist quasi ein Zifferblatt mit 256 Einteilungen. Addieren wir 208 und 84, so wäre das erwartete Ergebnis 292. Dabei „überdrehen“ wir jedoch. Teilen wir dieses ganzzahlig durch 256 und bilden den Rest, so erhalten wir 36. – So ganz falsch ist es also nicht, was uns unser 8-Bit-Prozessor ausspuckt, wenn wir nur nicht-negative Ganzzahlen betrachten.
Auch unter Berücksichtigung von Vorzeichen haben wir 256 Einteilungen. Die Addition von 108 und 84, die erwartet 192 ergeben sollte, ist ganz analog. Wir „überdrehen“ in diesem Fall zwar nicht das Zifferblatt, überschreiten jedoch die obere Grenze der positiven Ganzzahlen. Das Bitmuster der (positiven) 192 entspricht -64, wenn wir das Vorzeichen berücksichtigen. Das „Zifferblatt“ ist anders beschriftet.
Kongruente Zahlen
Kommen wir nochmals auf das Uhrenbeispiel zurück. Wir behandeln die 13 wie die 1, die 15 wie die 3, die 19 wie die 7 usw. Mathematisch sagt man: „19 ist kongruent zu 7 modulo 12“. – Für die anderen Zahlen gilt das freilich ganz analog.
Wir können das Spiel auch auf die negativen Zahlen ausdehnen. Betrachten wir hierzu als Beispiel die Zahlen, die kongruent 2 modulo 5 sind und visualisieren sie uns auf einem Zahlenstrahl. Ich habe hier nur einige Zahlen eingezeichnet. Du kannst die Reihe im Positiven, wie auch im Negativen, unendlich fortsetzen.
Der Abstand der Zahlen, die jeweils konguruent zu modulo 5 sind, ist jeweils 5. Du kannst das natürlich auch mit anderen Zahlen als der 2 durchspielen. Zu 4 kongruent modulo 5 sind die 9, die 14 usw.
Restklassenringe
Die Modulo-Rechnung zu einer ganzen Zahl n ergibt immer einen Wert aus der Menge der Zahlen von 0 bis n-1. Solch eine Menge, zusammen mit der jeweils spezifischen Form der Addition (und der Multiplikation), nennt man in der Mathematik einen Restklassenring.
Zurück zum Anfang
Die Fragestellung die ich oben formuliert hatte, waren die Folgenden:
- Warum meldet Pascal keinen Fehler?
- Wie falsch sind die Ergebnisse von Pascal?
- Warum rechnet Python richtig?
Pascal, wie übrigens die meisten anderen Programmiersprachen auch, ignoriert einen Überlauf. – Unsere Prozessoren zeigen ihn an. Es ist jedoch performanter ihn zu ignorieren. Haben wir einen hinreichend großen Datentypen gewählt, so gehen die Entwickler der Programmiersprachen davon aus, überwiegen die Anwendungsfälle, in denen kein Überlauf stattfindet. Sie nehmen also bewusst falsche Ergebnisse in Kauf. Es obliegt daher den Programmierern Sorge dafür zu tragen, solche Sachverhalte zu erkennen und entsprechend zu reagieren. Das Stichwort hierzu lautet Langzahlarithmetik. – Vielleicht schreibe ich hierzu auch noch einen Beitrag.
Im Sinne der besprochenen Modulo-Arithmetik rechnen Pascal, C, Java & Co. gar nicht falsch. Du kannst Dir sogar den Spaß machen, das zu überprüfen. Selbst das fortgesetzte Rechnen mit (nach „normaler“ Arithmetik) falschen Werten, bleibt in der Modulo-Arithmetik korrekt. Die folgende Python-Funktion überprüft, ob zwei ganze Zahlen zu einem gegebenen Modulo-Wert kongruent sind.
def kongruent_modulo(a: int, b:int, n: int) -> bool:
"""
Prüfung, ob a und b modulo n kongruent sind.
:param a: erste Zahl
:param b: zweite Zahl
:param n: Modulo-Wert
:return: True, wenn kongruent, ansonsten False
"""
return a % n == b % n
Probieren wir es anhand der obigen Resultate unserer zwei Fakultätsfunktionen aus. Der Modulo-Wert ist hier natürlich nicht 256 sondern 2 hoch 64.
print(kongruent_modulo(51090942171709440000, -4249290049419214848, 2**64)) print(kongruent_modulo(1124000727777607680000, -1250660718674968576, 2**64)) print(kongruent_modulo(265252859812191058636308480000000 , -8764578968847253504, 2**64))
Wir erhalten jeweils True als Ergebnis.
Für Python-Entwickler ist das alles insoweit uninteressant, als Python uns davon befreit, darüber nachzudenken. Python implementiert nämlich, für den Fall, das Zahlen größer sind als die Grenzen, die uns unser Prozessor setzt, Langzahlarithmetik. – Toll, oder?
Implikationen
Wenn Du als Python-Entwickler davon befreit bist, Dir Gedanken über den Wertebereich ganzer Zahlen zu machen, warum schreibe ich dann einen Beitrag zu modularer Arithmetik? – Die Frage ist berechtigt.
In der Regel kommt kein professioneller Entwickler mit nur einer Programmiersprache aus. Orientieren wir uns an den populärsten Programmiersprachen, die in der kommerziellen Praxis Anwendung finden, so kommst Du an C und Java nicht vorbei. Diese nutzen, wie Pascal, Modulo-Arithmetik. Insofern kann deren Kenntnis nicht schaden! – Natürlich können aber auch diese Programmiersprachen mit großen Zahlen umgehen. Du musst die Langzahlarithemtik auch nicht selbst implementieren. Dafür gibt es Bibliotheken. Du solltest jetzt aber, nach meinen Ausführungen, einschätzen können, wann es Sinn macht oder gar notwendig ist, diese zu verwenden.
Die Betrachtungen zur Modulo-Arithmetik liefert uns aber auch ein besseres Verständnis, wie Modulo-Berechnungen in Python funktionieren. Rechnest Du in Java -8 % 5, so erhältst Du -3. Die gleiche Operation in Python ausgeführt, liefert 2. Beide Ergebnisse sind in Bezug auf Modulo 5 kongruent. Das Ergebnis von Python entspricht jedoch der mathematischen Konvention zur ganzzahligen Division und deren Restwertbestimmung, weshalb wissenschaftliche Berechnungen in Python einfacher zu implementieren sind als dies in den meisten anderen Programmiersprachen der Fall ist.
Die Restwertdivision ist, wenn Du so möchtest, eine Geschmacksfrage.
8 mod 5 = 1 Rest 3 8 mod 5 = 2 Rest -2
oder
-8 mod 5 = -1 Rest -3 -8 mod 5 = -2 Rest 2
Weitere Ergebnisse sind denkbar. Mathematiker lieben jedoch eindeutige Resultate. Deshalb wird in der Mathematik eine Normierung vorgenommen. Die Vorzeichen der Reste werden aus dem Teiler zu bezogen:
-8 mod -5 = 1 Rest -3 -8 mod 5 = -2 Rest 2 8 mod -5 = -2 Rest -2 8 mod 5 = 1 Rest 3
Die Zugehörigkeit einer Zahl zu einer Restklasse (siehe oben) kann dadurch direkt am Rest abgelesen werden.
Während Python der mathematischen Konvention folgt, orientieren sich Programmiersprachen wie C oder Java an der „symmetrischen Variante“. Bei Portierungen ist das entsprechend zu berücksichtigen. Es gilt dann:
a mod b = ((a % b) + b) % b
Hier bezeichnet mod die mathematische Variante (in Python als % zu schreiben) und % die symmetrische Variante, wie sie in Java o.ä. verwendet und auch so geschrieben wird – Sorry für die Verwirrung. Du kannst das leicht prüfen.
# Java -8 % -5 -> -3 -8 % 5 -> -3 8 % -5 -> 3 8 % 5 -> 3 # Python -8 % -5 = -3 -8 % 5 = 2 8 % -5 = -2 8 % 5 = 3 # Prüfung # Python = Java (mathematisch) -8 % -5 = (-3 + (-5)) % (-5) = -3 -8 % 5 = (-3 + ( 5)) % ( 5) = 2 8 % -5 = ( 3 + (-5)) % (-5) = -2 8 % 5 = ( 3 + ( 5)) % ( 5) = 3
Jetzt verstehst Du auch, weshalb ich im Abschnitt des Tutorials „Integrierte Datentypen – Zahlen“ sage: „Die Restwertdivision beziehungsweise Restwertbildung folgt in Python der mathematischen Konvention!“.