Weltrekord-Rechenmethode kommt zu späten Ehren
Vor mehr als 30 Jahren erfand Professor Dr. Arnold Schönhage zusammen mit dem Mathematiker Professor Dr. Volker Strassen eine Rechenvorschrift zur schnellen Multiplikation großer Zahlen. Kürzlich feierte der Emeritus der Universität Bonn seinen 70. Geburtstag; derweil hält der "Schönhage-Strassen-Algorithmus" noch immer den Geschwindigkeits-Weltrekord. Ursprünglich eher ein theoretisches Kuriosum, kommt der Algorithmus inzwischen auch bei der Lösung praktischer mathematischer Probleme zum Einsatz.
Professor Dr. Arnold Schönhage
(c) Frank Luerweg / Uni Bonn
Vielleicht wäre die Welt ein wenig gerechter, wenn der Logarithmus die Gebührenordnung von Anwälten bestimmen würde: Da habe doch letztens ein Rechtsanwalt über zwei Millionen Euro Honorar verlangt, weil sein Klient plötzlich durch einen Tippfehler dem Finanzamt rund 230 Millionen Euro an Steuern schuldete. Dabei sei die Sache mit ein paar Briefen bereinigt gewesen, erzählt Professor Schönhage. "Die Anwälte sind aber leider noch lange nicht so weit, dass sie ihre Gebühren am Logarithmus des Streitwerts orientieren. Dabei wächst ihr Arbeitsaufwand ganz gewiss nicht proportional zur Summe, um die es geht." Er kneift die Augen gegen die schräg in sein Büro fallende Nachmittagssonne zusammen und sieht für einen Moment aus wie ein listiger alter Fuchs, der sich über irgendetwas blendend amüsiert.
Der Logarithmus ist ein effektiver Verkleinerer großer Zahlen - der Zehnerlogarithmus 10 ist 1, der von 230 Millionen ist 8,36; bei einem Streitwert von 230 Millionen würde der Rechtsanwalt aus Schönhages Beispiel bei logarithmischer Entlohnung daher nur gut achtmal soviel verdienen, als wenn es um zehn Euro ginge. Im Schönhage-Strassen-Algorithmus fließt der Logarithmus in die so genannte "Zeitkomplexität" mit ein. Damit ist die Rechenvorschrift bei großen Zahlen deutlich schneller als alle anderen heute bekannten Verfahren.
Ein Beispiel: "In der Schule lernen wir, mehrstellige Zahlen schriftlich zu multiplizieren, indem wir die einzelnen Ziffern miteinander malnehmen und die Zwischenergebnisse addieren", so Schönhage. Die Aufgabe "34·67" erfordert daher vier Multiplikationsschritte, für "345·678" bemühen wir das kleine Einmaleins schon neunmal. Oder allgemeiner ausgedrückt: Um zwei k-stellige Zahlen miteinander malzunehmen, benötigen wir k^2 Multiplikationsschritte; der Zeitaufwand steigt quadratisch mit der Stellenzahl.
Beim Schönhage-Strassen-Algorithmus wächst der Rechenaufwand erheblich langsamer - genauer gesagt: proportional zu k·log(k)·log(log(k)). "Um zwei Zahlen mit jeweils einer Million Ziffern zu multiplizieren, benötigt mein Pentium II mit unserer Rechenvorschrift etwa dreieinhalb Sekunden", erklärt Professor Schönhage. "Nun lassen Sie mich mal rechnen..." Er kramt auf seinem Schreibtisch. "Ach, ich finde gerade keinen Taschenrechner; dann mach ich's halt im Kopf." Er kritzelt ein paar Zahlen auf's Papier und verkündet: "Mit der Methode, die wir in der Schule lernen, wäre der Computer rund 200mal so lange beschäftigt, also fast 12 Minuten."
Als Schönhage und Strassen ihren Algorithmus 1971 publizierten, erregten sie damit in Mathematikerkreisen weltweit Aufsehen. Dennoch galt ihre Entdeckung jahrelang als Kuriosität ohne große praktische Relevanz, da sie ihre Stärken erst bei extrem großen Zahlen ausspielt. "Bis zu einigen tausend Dezimalstellen gibt es andere Methoden, die schneller funktionieren", gibt der Bonner Informatiker zu. Dennoch kommt die Rechenvorschrift inzwischen zunehmend bei bestimmten Spezialproblemen zum Einsatz.
Der Grundalgorithmus wurde in den letzten Jahrzehnten zwar vielfach abgewandelt. "Der Geschwindigkeitsrekord jedoch bleibt bis heute unangetastet", betont Schönhages Kollege Professor Dr. Michael Clausen. "Manche glauben sogar, mit dem Schönhage-Strassen-Algorithmus sei bei der Multiplikation großer Zahlen das Ende der Fahnenstange erreicht."
Kontakt:
Professor Dr. Arnold Schönhage
Institut für Informatik III der Universität Bonn
Telefon: 0228/73-4535 (Uni) oder 02225/14065 (privat)
E-Mail: schoe@informatik.uni-bonn.de
