Malnehmen ist ein Kinderspiel. Wir lernen das schriftliche Multiplizieren in der Schule. Um das Produkt aus zwei beliebig großen Zahlen zu bilden, muss man nur das kleine Einmaleins von 1 bis 9 beherrschen, der Rest ergibt sich, indem man die einzelnen Ergebnisse aufaddiert.
Das Rechenverfahren ist uns so in Fleisch und Blut übergegangen, dass die Mathematiker lange dachten, dies sei die effektivste Form der Multiplikation, auch für Computer. Seit den sechziger Jahren weiß man: Es geht tatsächlich schneller, viel schneller – und soeben hat ein Schweizer Mathematiker ein neues Verfahren entdeckt, das zumindest theoretisch die schnellste Multiplikationsmethode der Welt ist.
Wenn man auf die klassische Weise zwei Zahlen mit jeweils n Ziffern malnimmt, dann muss man jede Ziffer der einen mit jeder Ziffer der anderen multiplizieren, das sind zusammen n 2 elementare Multiplikationen (und noch ein paar Additionen). Moderne Computer erledigen das gewöhnlich in Bruchteilen von Sekunden.
Zum Problem wird das Verfahren erst, wenn mit wirklich großen Zahlen gerechnet wird – Zahlen, die Tausende, Millionen oder gar Milliarden von Stellen haben. Bestehen zwei Zahlen aus je einer Million Ziffern, dann sind für die Berechnung des Produkts eine Billion Elementarmultiplikationen nötig – und selbst wenn ein Computer in jeder Sekunde Millionen davon löst, braucht er für die Aufgabe einige Tage.
Mit solchen Monsterzahlen wird in einigen Gebieten der Mathematik tatsächlich gerechnet. Etwa bei der Suche nach immer größeren Primzahlen. Auch die Riemannsche Vermutung, eines der großen ungelösten Probleme der Mathematik, kann man mit solchen Rechnungen zwar nicht beweisen, aber zumindest immer besser bestätigen.
Im Jahr 1960 entdeckte der Russe Anatolij Alexejewitsch Karatsuba, dass es mit erstaunlich einfachen Mitteln auch schneller geht: In dem nach ihm benannten Verfahren, auch die "Teile und herrsche"-Methode genannt, spaltet man die zu multiplizierenden Zahlen jeweils in zwei Hälften. Aus diesen Bruchstücken werden drei neue, kürzere Zahlen A, B und C gebildet, aus denen sich das Produkt der ursprünglichen Zahlen durch Additionen berechnen lässt. Wendet man auch auf die kürzeren Zahlen den Karatsuba-Algorithmus an, so ergibt sich letztlich eine Laufzeit, die nicht mehr in der Größenordnung von n 2 liegt, sondern bei n 1,6 . Für kleine Zahlen bringt das nicht viel, aber bei den wirklich großen merkt man den Unterschied.
Kommentare
hammer
aber wie wird so jemand bezahlt? patentiert er sein rechenverfahren?
Von seiner Uni
Der Mann ist Professor fuer Computerwissenschaften an der Pensylvania State University (aber gerade als Gast in Zuerich): http://www.cse.psu.edu/~f...
Wirklich faszinierend, der Artikel.
In dem nach ihm benannten Verfahren, auch die »Teile und herrsche«-Methode genannt, spaltet man die zu multiplizierenden Zahlen jeweils in zwei Hälften. Aus diesen Bruchstücken werden drei neue, kürzere Zahlen A, B und C gebildet, aus denen sich das Produkt der ursprünglichen Zahlen durch Additionen berechnen lässt.
------
Hier habe ich aufgehört zu lesen, denn wenn man jeweils 2 Zahlen teilt erhält man nicht 3 Zahlen, sondern 4.
Tja
Haetten Sie mal bis zum Ende gelesen ...
Danke für den Hinweis. Und
Danke für den Hinweis.
Und wenn man bibabunte Bildchen anzeigen aktiviert, kann man es auch lesen. Hätte man ja gleich im Text richtig erklärt vorne anbringen können. Stattdessen liest man vorne was von "n .log n" Was ist denn das? Das schreibt doch niemand so. Das der Punkt ein Malzeichen symbolisieren soll ahnt nur der, der eh weiß worum es geht.
Für Zahlen mit ungeraden Stellen funktioniert die im biababunten Bildchen demonstrierte Methode nicht mehr. Was wirklich dahintersteckt wird auf einer WIKI-Seite besser erklärt.
Es kommt mir sowieso vor, als ob der ZEIT-Artikel von dort nur schlecht abgeschrieben wurde.
Die Methode funktioniert auch dann
"Für Zahlen mit ungeraden Stellen funktioniert die im biababunten Bildchen demonstrierte Methode nicht mehr. Was wirklich dahintersteckt wird auf einer WIKI-Seite besser erklärt."
Doch, der Karatsuba Algorithmus funkioniert auch bei Faktoren mit unterschiedlicher Længe und auch bei Faktoren mit ungerader Anzahl Ziffern. Dann werden den Zahlen Nullen vorgestellt, bis sie gleichlang sind und eine grade Anzahl Ziffern haben. Siehe z.B. bei Wikipedia: http://de.wikipedia.org/w...
Ich finde den Algorithmus in dem "bibabunten"(?) Bild sehr anschaulich erklært.