Mathematik Das ganz große Einmaleins
Die Multiplikation zweier Zahlen ist eine elementare Rechenoperation. Aber auch sie lässt sich noch verbessern
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.
Der nächste Schritt kam 1971, als die beiden deutschen Mathematiker Arnold Schönhage und Volker Strassen gleich zwei neue Verfahren vorstellten. Anders als Karatsuba mussten sie schon eine Menge höhere Mathematik aufwenden, um das Malnehmen noch einmal zu beschleunigen. Ab einer Länge von etwa 10.000 Ziffern war ihre Multiplikation wirklich schneller als alle bis dahin existierenden.
Seitdem schlummerte das Problem vor sich hin. Die Informatiker verwandten ihre Energie vor allem darauf, die existierenden Algorithmen möglichst optimal zu programmieren, teilweise werden zum Malnehmen auch spezielle Chips eingesetzt. Der Stand der Technik heute: Die Multiplikation von zwei Zahlen mit je einer Milliarde Stellen dauert auf einem schnellen Rechner nach der Schulbuchmethode 42 Tage, mit Karatsubas Verfahren knapp drei Stunden, mit der Methode von Schönhage und Strassen liegt das Ergebnis in weniger als zwei Minuten vor.
Aber geht es vielleicht theoretisch noch schneller? Gibt es eine untere Grenze für die Zahl der Rechenschritte, die von keinem Verfahren zu unterbieten ist? Letzteres ist weiterhin unbeantwortet, die Mathematiker glauben, dass kein Algorithmus schneller sein kann als die Größenordnung n · log n (log n ist der Logarithmus von n ). Aber im vergangenen Jahr stellte Martin Fürer, ein Schweizer, der an der amerikanischen Pennsylvania State University lehrt, auf einer großen Informatik-Konferenz tatsächlich eine Methode vor, mit der man zumindest in der Theorie große Zahlen noch schneller multiplizieren kann.
Fürers Verfahren lässt sich hier nicht erklären, er selbst beschreibt es als eine Methode, die die Vorteile der beiden Schönhage-Strassen-Algorithmen kombiniert (und ihre Nachteile vermeidet). In der Fachwelt sorgte sein Vortrag für Aufsehen – es kommt in der schnelllebigen Computerwissenschaft nicht oft vor, dass nach über 35 Jahren noch einmal ein neuer Durchbruch erzielt wird, noch dazu bei einem scheinbar so simplen Problem. Die Veröffentlichung von Fürers Entdeckung in einer Fachzeitschrift ist in Vorbereitung.
Wenn man Fürer nach dem Alltagsnutzen seines Rechenverfahrens fragt, dann antwortet er bescheiden: »Praktisch bedeutet es vorläufig nichts.« Seine Erkenntnis ist eine rein theoretische, es gibt noch gar kein konkretes Rechenprogramm, das damit arbeitet. Und wenn es eines gäbe, dann würde der Vorteil erst bei »astronomisch großen Zahlen« offenbar, wie Fürer in seiner Arbeit schreibt. Im Gespräch konkretisiert er das auf Zahlen mit »vielen Millionen oder Milliarden von Stellen«.
Martin Grötschel, der Chef des Berliner Konrad-Zuse-Zentrums für Informationstechnik, hält Fürers Entdeckung für bahnbrechend. »Wir stoßen zunehmend auf Probleme, bei denen wir solche großen Zahlen exakt multiplizieren müssen, etwa wenn wir die Korrektheit von Chips überprüfen oder bei Verschlüsselungsverfahren.« Wie gut Fürers Rechenmethode tatsächlich sei, werde sich empirisch herausstellen, wenn sie erst einmal auf einem Computer implementiert sei. »Darauf werden sich jetzt einige Leute stürzen, und dann werden wir den konkreten Nutzen sehen.«
Anzeige
- Datum 27.11.2008 - 07:00 Uhr
- Quelle DIE ZEIT, 27.11.2008 Nr. 49
- Kommentare 11
- Versenden E-Mail verschicken
- Empfehlen Facebook, Twitter, Google+
- Artikel Drucken Druckversion | PDF
-
Artikel-Tools präsentiert von:
aber wie wird so jemand bezahlt? patentiert er sein rechenverfahren?
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.
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.
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.
Haetten Sie mal bis zum Ende gelesen ...
Haetten Sie mal bis zum Ende gelesen ...
Haetten Sie mal bis zum Ende gelesen ...
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.
"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.
Die mathematische Exaktheit des Artikels lässt heftig zu wünschen übrig, ich stimme mit Ihnen überein. Dass beim Karatsuba-Algorithmus weniger einzelne Multiplikationen durchgeführt werden müssen, habe ich verstanden, aber was soll das heißen, dass es nur noch "n 1,6" sind? n mal 1,6? Dann sollte man das Malzeichen ruhig setzen oder schreiben 1,6n. Wahrscheinlich ist aber n hoch 1,6 gemeint, das gibt eine handelsübliche Tastatur nicht her(anders als das n²), der arme Herr Drösser. Und Logarithmen scheint er nur vom Hörensagen zu kennen: "log n ist der Logarithmus von n." Und welcher? Es könnte der natürliche Logarithmus sein, wahrscheinlich eher der dekadische, vielleicht auch der binäre, schließlich bewegen sich Computer gern im Dualsystem...
Der Artikel scheint mir komplett unentschieden zwischen Allgemeinverständlichkeit und mathematischem Anspruch hin und her zu schwanken, und er verfehlt letztlich beides. Ein mathematisch unbedarfter Mensch ebenso wie ein Freund der Mathematik kriegen beide das Grauen, wenn sie lesen: "n .log n" Letztlich haben dann beide den Artikel gelesen, ohne den geringsten Gewinn daraus gezogen zu haben, nicht einmal einen Link zur Wikipedia, wo man vielleicht genauere Angaben erlesen könnte, gönnt er uns.
"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.
Die mathematische Exaktheit des Artikels lässt heftig zu wünschen übrig, ich stimme mit Ihnen überein. Dass beim Karatsuba-Algorithmus weniger einzelne Multiplikationen durchgeführt werden müssen, habe ich verstanden, aber was soll das heißen, dass es nur noch "n 1,6" sind? n mal 1,6? Dann sollte man das Malzeichen ruhig setzen oder schreiben 1,6n. Wahrscheinlich ist aber n hoch 1,6 gemeint, das gibt eine handelsübliche Tastatur nicht her(anders als das n²), der arme Herr Drösser. Und Logarithmen scheint er nur vom Hörensagen zu kennen: "log n ist der Logarithmus von n." Und welcher? Es könnte der natürliche Logarithmus sein, wahrscheinlich eher der dekadische, vielleicht auch der binäre, schließlich bewegen sich Computer gern im Dualsystem...
Der Artikel scheint mir komplett unentschieden zwischen Allgemeinverständlichkeit und mathematischem Anspruch hin und her zu schwanken, und er verfehlt letztlich beides. Ein mathematisch unbedarfter Mensch ebenso wie ein Freund der Mathematik kriegen beide das Grauen, wenn sie lesen: "n .log n" Letztlich haben dann beide den Artikel gelesen, ohne den geringsten Gewinn daraus gezogen zu haben, nicht einmal einen Link zur Wikipedia, wo man vielleicht genauere Angaben erlesen könnte, gönnt er uns.
"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.
Doch, der Karatsuba Algorithmus funkioniert auch bei Faktoren mit unterschiedlicher Længe und auch bei Faktoren mit ungerader Anzahl Ziffern.
Na das habe ich ja gerade nicht bestritten, nur funktioniert die bibabunte Methode des Zeit-Artikels nicht mehr. Und sie zitieren meinen Hinweis auf WIKI mit dem Hinweis auf WIKI. Absurd, denn mein Hinweis auf WIKI war ja eben in ihrem Sinne. Manchmal fragt man sich echt...
Doch, der Karatsuba Algorithmus funkioniert auch bei Faktoren mit unterschiedlicher Længe und auch bei Faktoren mit ungerader Anzahl Ziffern.
Na das habe ich ja gerade nicht bestritten, nur funktioniert die bibabunte Methode des Zeit-Artikels nicht mehr. Und sie zitieren meinen Hinweis auf WIKI mit dem Hinweis auf WIKI. Absurd, denn mein Hinweis auf WIKI war ja eben in ihrem Sinne. Manchmal fragt man sich echt...
Die mathematische Exaktheit des Artikels lässt heftig zu wünschen übrig, ich stimme mit Ihnen überein. Dass beim Karatsuba-Algorithmus weniger einzelne Multiplikationen durchgeführt werden müssen, habe ich verstanden, aber was soll das heißen, dass es nur noch "n 1,6" sind? n mal 1,6? Dann sollte man das Malzeichen ruhig setzen oder schreiben 1,6n. Wahrscheinlich ist aber n hoch 1,6 gemeint, das gibt eine handelsübliche Tastatur nicht her(anders als das n²), der arme Herr Drösser. Und Logarithmen scheint er nur vom Hörensagen zu kennen: "log n ist der Logarithmus von n." Und welcher? Es könnte der natürliche Logarithmus sein, wahrscheinlich eher der dekadische, vielleicht auch der binäre, schließlich bewegen sich Computer gern im Dualsystem...
Der Artikel scheint mir komplett unentschieden zwischen Allgemeinverständlichkeit und mathematischem Anspruch hin und her zu schwanken, und er verfehlt letztlich beides. Ein mathematisch unbedarfter Mensch ebenso wie ein Freund der Mathematik kriegen beide das Grauen, wenn sie lesen: "n .log n" Letztlich haben dann beide den Artikel gelesen, ohne den geringsten Gewinn daraus gezogen zu haben, nicht einmal einen Link zur Wikipedia, wo man vielleicht genauere Angaben erlesen könnte, gönnt er uns.
habe ich verstanden, aber was soll das heißen, dass es nur noch "n 1,6" sind? n mal 1,6? Dann sollte man das Malzeichen ruhig setzen oder schreiben 1,6n. Wahrscheinlich ist aber n hoch 1,6 gemeint, das gibt eine handelsübliche Tastatur nicht her(anders als das n²), der arme Herr Drösser.
Vermutlich konvergiert der zeitliche Rechenaufwand, sprich Laufzeitkomplexizität, für unendlich große Zahlen gegen den Faktor 1,6 x n. Das bedeutet einen linearen Anstieg der Rechenzeit mit der Stellenzahl der Operanden gegenüber einem quadratischen bei der Schulbuchmethode. So wird der Karatsuba-Algorithmus immer effektiver, je größer die Zahlen werden, aber nähert sich einer effektiven Grenze. Leider wurde der dem Laien der nicht gängige Begriff "Laufzeit" auch nicht im Artikel spezifisch erklärt. "Laufzeit" ist darüber hinaus ein überhaus mehrdeutiger Begriff.
http://de.wikipedia.org/w...
http://de.wikipedia.org/wiki/Laufzeit_(Informatik)
Hallo
zur Ehrenrettung des Autors sei erwähnt, daß "log n" , "n", "n*log n" etc. für Informatiker lediglich Größenordnungen von Laufzeiten bezeichnen. Man unterscheidet dabei lediglich, ob ein Algorithmus in "linearer Zeit", "polynomieller Zeit", "exponentieller Zeit" - oder eben - wenn's sehr gut läuft - in "logarithmischer Zeit" fertig ist. Ist nur ne grobe Kategorisierung - obwohl soetwas einem Mathematiker wahrscheinlich weh tut?! Für Laufzeitabschätzungen reicht's aber aus. Dann läßt sich jeder Algorithmus nach seiner Laufzeit kategorisieren. Allerdings hätte der Autor einführend darauf hinweisen können...
"Log" ist der Zehnerlogarithmus, der natürliche Logarithmus wäre "ln" in der informatischen Welt. Wahrscheinlich ist der Autor aber selbst kein Informatiker - doch es gibt doch schlimmeres!? :)
Das eigentliche Thema ist aber auch für uns praktisch spannend - nicht nur für astronomische Zahlen. Es gibt eine aus Indien stammende Zahlenarithmetik - oft als "vedische Mathematik" bezeichnet, die hierzulande leider nicht sehr bekannt zu sein scheint. Damit lassen sich große Zahlen - mit etwas Übung auch im Kopf - effizient verrechnen...
Aus dem Glaubensstreit - ob wirklich "vedisch" oder nicht - möchte ich mich als Nicht-Inder lieber heraushalten - aber die Methoden sind einfach genial! Soetwas sollte man unseren Kindern in der Schule - besser noch davor! ;-) - beibringen! Liebe Kinder - und liebe Eltern! - liebe Lehrer/Innen! gebt fein acht... Leider scheinen sich nur die Inder bisher dieser einfach genialen Arithmetik zu bedienen, also ist leider alles auf Englisch:
Hier ist zunächst ein lustiges Video mit einem Multiplikationsbeispiel:
http://www.metacafe.com/w...
Und hier ein Tutorial, welches eine gute Einführung bietet:
http://www.vedicmaths.org...
und noch ein paar lustige Videos aus Indien:
http://www.metacafe.com/w...
http://www.metacafe.com/w...
http://www.metacafe.com/w...
http://www.metacafe.com/w...
Viel Spaß beim Rechnen! ;-)
Herzliche Grüße,
RudraChakrin
__________________________________________________________
Und außerdem meine ich, daß Deutschland sich bei China um die Freilassung des rechtmäßigen Panchen Lama, Gedün Choekyi Nyima, der 1995 verschleppt wurde, bemühen sollte - so dieser noch lebt!?
>Die mathematische Exaktheit des Artikels lässt heftig zu wünschen übrig ...
Stimmt, es ist auch gar kein mathematischer Artikel, sondern ein journalistischer, und da lässt die mathematische Exaktheit notwendigerweise zu wünschen übrig.
>aber was soll das heißen, dass es nur noch "n 1,6" sind?
Die Artikel werden bei uns automatisch fürs Netz konvertiert, und da gehen solche Formatierungen wie Hochzahlen, Sonderzeichen etc. verloren. Sorry, und wir reparieren das per Hand!
>"log n ist der Logarithmus von n." Und welcher?
Das ist für Laufzeitberechnungen dieser Art belanglos, man kann den Logarithmus zu irgendeiner Basis nehmen, da die sich nur um einen konstanten Faktor unterscheiden. Und das ist den Informatikern egal - sie betrachten zwei Algorithmen, die sich in der Laufzeit um den Faktor 1000 unterscheiden, als prinzipiell gleich. Es geht um Größenordnungen auf lange Sicht!
habe ich verstanden, aber was soll das heißen, dass es nur noch "n 1,6" sind? n mal 1,6? Dann sollte man das Malzeichen ruhig setzen oder schreiben 1,6n. Wahrscheinlich ist aber n hoch 1,6 gemeint, das gibt eine handelsübliche Tastatur nicht her(anders als das n²), der arme Herr Drösser.
Vermutlich konvergiert der zeitliche Rechenaufwand, sprich Laufzeitkomplexizität, für unendlich große Zahlen gegen den Faktor 1,6 x n. Das bedeutet einen linearen Anstieg der Rechenzeit mit der Stellenzahl der Operanden gegenüber einem quadratischen bei der Schulbuchmethode. So wird der Karatsuba-Algorithmus immer effektiver, je größer die Zahlen werden, aber nähert sich einer effektiven Grenze. Leider wurde der dem Laien der nicht gängige Begriff "Laufzeit" auch nicht im Artikel spezifisch erklärt. "Laufzeit" ist darüber hinaus ein überhaus mehrdeutiger Begriff.
http://de.wikipedia.org/w...
http://de.wikipedia.org/wiki/Laufzeit_(Informatik)
Hallo
zur Ehrenrettung des Autors sei erwähnt, daß "log n" , "n", "n*log n" etc. für Informatiker lediglich Größenordnungen von Laufzeiten bezeichnen. Man unterscheidet dabei lediglich, ob ein Algorithmus in "linearer Zeit", "polynomieller Zeit", "exponentieller Zeit" - oder eben - wenn's sehr gut läuft - in "logarithmischer Zeit" fertig ist. Ist nur ne grobe Kategorisierung - obwohl soetwas einem Mathematiker wahrscheinlich weh tut?! Für Laufzeitabschätzungen reicht's aber aus. Dann läßt sich jeder Algorithmus nach seiner Laufzeit kategorisieren. Allerdings hätte der Autor einführend darauf hinweisen können...
"Log" ist der Zehnerlogarithmus, der natürliche Logarithmus wäre "ln" in der informatischen Welt. Wahrscheinlich ist der Autor aber selbst kein Informatiker - doch es gibt doch schlimmeres!? :)
Das eigentliche Thema ist aber auch für uns praktisch spannend - nicht nur für astronomische Zahlen. Es gibt eine aus Indien stammende Zahlenarithmetik - oft als "vedische Mathematik" bezeichnet, die hierzulande leider nicht sehr bekannt zu sein scheint. Damit lassen sich große Zahlen - mit etwas Übung auch im Kopf - effizient verrechnen...
Aus dem Glaubensstreit - ob wirklich "vedisch" oder nicht - möchte ich mich als Nicht-Inder lieber heraushalten - aber die Methoden sind einfach genial! Soetwas sollte man unseren Kindern in der Schule - besser noch davor! ;-) - beibringen! Liebe Kinder - und liebe Eltern! - liebe Lehrer/Innen! gebt fein acht... Leider scheinen sich nur die Inder bisher dieser einfach genialen Arithmetik zu bedienen, also ist leider alles auf Englisch:
Hier ist zunächst ein lustiges Video mit einem Multiplikationsbeispiel:
http://www.metacafe.com/w...
Und hier ein Tutorial, welches eine gute Einführung bietet:
http://www.vedicmaths.org...
und noch ein paar lustige Videos aus Indien:
http://www.metacafe.com/w...
http://www.metacafe.com/w...
http://www.metacafe.com/w...
http://www.metacafe.com/w...
Viel Spaß beim Rechnen! ;-)
Herzliche Grüße,
RudraChakrin
__________________________________________________________
Und außerdem meine ich, daß Deutschland sich bei China um die Freilassung des rechtmäßigen Panchen Lama, Gedün Choekyi Nyima, der 1995 verschleppt wurde, bemühen sollte - so dieser noch lebt!?
>Die mathematische Exaktheit des Artikels lässt heftig zu wünschen übrig ...
Stimmt, es ist auch gar kein mathematischer Artikel, sondern ein journalistischer, und da lässt die mathematische Exaktheit notwendigerweise zu wünschen übrig.
>aber was soll das heißen, dass es nur noch "n 1,6" sind?
Die Artikel werden bei uns automatisch fürs Netz konvertiert, und da gehen solche Formatierungen wie Hochzahlen, Sonderzeichen etc. verloren. Sorry, und wir reparieren das per Hand!
>"log n ist der Logarithmus von n." Und welcher?
Das ist für Laufzeitberechnungen dieser Art belanglos, man kann den Logarithmus zu irgendeiner Basis nehmen, da die sich nur um einen konstanten Faktor unterscheiden. Und das ist den Informatikern egal - sie betrachten zwei Algorithmen, die sich in der Laufzeit um den Faktor 1000 unterscheiden, als prinzipiell gleich. Es geht um Größenordnungen auf lange Sicht!
Doch, der Karatsuba Algorithmus funkioniert auch bei Faktoren mit unterschiedlicher Længe und auch bei Faktoren mit ungerader Anzahl Ziffern.
Na das habe ich ja gerade nicht bestritten, nur funktioniert die bibabunte Methode des Zeit-Artikels nicht mehr. Und sie zitieren meinen Hinweis auf WIKI mit dem Hinweis auf WIKI. Absurd, denn mein Hinweis auf WIKI war ja eben in ihrem Sinne. Manchmal fragt man sich echt...
Bitte melden Sie sich an, um zu kommentieren