Arithmetik
Aus der Reihe The Art of Computer Programming
Donald E. Knuth
Springer-Verlag, Berlin, Heidelberg, New York, 538 Seiten, 2001, 538 Seiten, 52,95 €
ISBN 3-540-66745-8
Dies ist die deutsche Version von Kapitel IV des Standardwerkes "The Art of Computer Programming'' von Donald E. Knuth. Sie wurde von R. Loos in die deutsche Sprache übersetzt. Damit erhalten auch Studenten aus dem deutschsprachigen Raum, die mit der englischen Sprache Probleme haben, einen Zugang zu dieser wichtigen Lektüre.
Wie der Titel Arithmetik schon ausdrückt, behandelt das vorliegende Werk die vier Grundrechenoperationen für Zahlen, Polynome und - knapp gehalten - Potenzreihen. Das Werk beginnt mit einem Abschnitt über Stellenwertsysteme und deren geschichtliche Entwicklung. Es folgen Untersuchungen über Gleitkommaarithmetik und deren Genauigkeit bei einfacher und mehrfacher Präzision. Danach werden Algorithmen für Rechnungen mit beliebig großen ganzen Zahlen vorgestellt. Im weiteren wird generell die Arithmetik für ganze und rationale Zahlen detailliert abgehandelt. Knuth legt dabei unter anderem Wert auf die Berechnung des größten gemeinsamen Teilers zweier Zahlen und analysiert den Euklidischen Algorithmus. Danach wendet er sich Faktorisierungsmethoden und Primzahltests zu. Im anschließenden Abschnitt geht er auf Polynomarithmetik ein. Auch hier werden Faktorisierungsmethoden vorgestellt. Während das Verfahren von Berlekamp zur modularen Faktorisierung eingehend besprochen wird, werden die Anwendungen auf Faktorisierungen von Polynomen mit ganzen Koeffizienten eher stiefmütterlich behandelt. Insbesondere verzichtet er darauf, den berühmten LLL-Algorithmus einzuführen. Dafür gibt es einen Unterabschnitt über die Berechnung von Polynomwerten an vorgegebenen Stellen. Den Abschluss bildet ein kurzer Abschnitt über die Arithmetik von Potenzreihen.
Der Leser findet in diesem Buch wertvolle Hinweise für die Entwicklung von Algorithmen und deren Implementierung, soweit sie mit der Arithmetik der betrachteten Objekte zu tun haben. Einige Beachtung finden auch Implementierungsfragen auf unteren Ebenen, wo wenige Zeilen Assembler Code erhebliche Beschleunigung bringen können. Von Knuth wird hierfür ein fiktiver MIX-Rechner benutzt.
Hervorzuheben sind die reichhaltigen Literaturverweise (bis 1998) und die vielen interessanten und unterschiedlich schwierigen Übungsaufgaben, die von Standardstoff bis zu Forschungsprojekten reichen, wobei der Schwierigkeitsgrad stets recht exakt angegeben wird. Entsprechend viele Seiten des Buches gehen auf die Lösungen ein oder geben Anleitungen. Obwohl die ursprüngliche Fassung 25 Jahre alt ist, hat das Werk wenig von seinem Charme verloren, zumal es Literaturhinweise auf wichtige neuere Entwicklungen gibt. Dem Unterfangen des Übersetzers, dieses Werk deutschsprachiger Leserschaft näher zu bringen, wünsche ich viel Erfolg.
Rezension: Michael Pohst (Berlin) aus Computeralgebra-Rundbrief, Nr. 30 - März 2002