Diskussion:Schönhage-Strassen-Algorithmus

Komplexitätsschranke

Meines Wissens gilt die Schranke O(nlogn loglogn) für Turingmaschinen. Auf einer RAM gilt die Schranke O(nlogn). (Vgl. auch: Knuth, The Art of Computer Programming, Vol. 2)

Die Formulierung zu Turingmaschinen ist mittlerweile drin.--JFKCom 21:00, 14. Aug 2006 (CEST)

Intro zur Effizienz

Im Artikel steht oben, der Algorithmus waere "einer der bisher effizientesten" zur Multiplikation n-stelliger Zahlen, weiter unten steht "Bis heute konnte kein effizienterer Algorithmus gefunden werden."

Ist mittlerweile behoben.--JFKCom 21:00, 14. Aug 2006 (CEST)

Toter Weblink

Bei mehreren automatisierten Botläufen wurde der folgende Weblink als nicht verfügbar erkannt. Bitte überprüfe, ob der Link tatsächlich down ist, und korrigiere oder entferne ihn in diesem Fall!

• http://www.informatik.uni-bonn.de/~schoe/publi39.dvi%7Caccessdate=17.10.2006
  • In Schönhage-Strassen-Algorithmus on Thu Nov 9 12:48:37 2006, 404 Not Found
  • In Schönhage-Strassen-Algorithmus on Mon Nov 27 14:42:39 2006, 404 Not Found

--Zwobot 14:43, 27. Nov. 2006 (CET)

Ist da und wird geladen. Man braucht allerdings ein .dvi-Anzeigeprogramm.--LutzL 08:52, 28. Nov. 2006 (CET)

Grundidee

Hallo mir fehlt etwas die Grundidee. Wie funktioniert das überhaupt? Bin etwas draussen, aber ich denke man sollte sowas wie das folgende erwähnen bzw. voranschicken:

${\hat {a}}_{k}=\sum _{i=0}^{2^{n}-1}a_{i}\cdot w^{i\cdot k}$ für $k=0,\ldots ,2^{n}-1$.

${\hat {b}}_{k}=\sum _{j=0}^{2^{n}-1}b_{j}\cdot w^{j\cdot k}$ für $k=0,\ldots ,2^{n}-1$.

${\hat {c}}_{l}=1/2^{n+1}\sum _{k=0}^{2^{n}-1}{\hat {a}}_{k}\cdot {\hat {b}}_{k}\cdot w^{-l\cdot k}$ für $k=0,\ldots ,2^{n+1}-1$.

${\hat {c}}_{l}=1/2^{n+1}\sum _{i,j,k=0}^{2^{n}-1}a_{i}b_{j}\cdot w^{i\cdot k+j\cdot k-l\cdot k}$ für $k=0,\ldots ,2^{n+1}-1$.

${\hat {c}}_{l}=1/2^{n+1}\sum _{i,j,k=0}^{2^{n}-1}a_{i}b_{j}\cdot w^{(i+j-l)\cdot k}$ für $k=0,\ldots ,2^{n+1}-1$.

Da w 2ⁿ-te Einheitswurzel ist, ist sie Lösung der Gleichung $w^{\,{2^{n}}}-1=0$. Diese genügt folgender Identität geometrischer Summen von Einheitswurzeln:

$\displaystyle \sum _{k=0}^{{2^{n}}-1}q^{lk}={2^{n}}\delta _{l,0}$ für $l=0,...,2^{n}-1$,

denn

$\displaystyle \sum _{k=0}^{{2^{n}}-1}x^{k}={\frac {x^{2^{n}}-1}{x-1}}$ für $x\neq 1$.

Somit gilt:

${\hat {c}}_{l}=1/2^{n+1}\sum _{i+j=l}a_{i}b_{j}\cdot 2^{n+1}$ für $k=0,\ldots ,2^{n+1}-1$.

Da fehlen natürlich Carry bits und viele andere Details, aber ohne diese Idee bringt das doch alles nichts, oder? --ThiloHarich 22:11, 10. Jan. 2007 (CET)

Hm, die geometrische Summenformel verwendet eine Division, die im Zahlenring im Allgemeinen nicht erlaubt ist; das müßte man etwas akkurater betrachten (es ist also darauf zu achten, dass x-1 ein invertierbares Element im Ring ist). Auf die Schnelle sehe ich noch nicht, ob Deine Herleitung die Kernidee des Algorithmus trifft. Im Algorithmus werden ja $a,b$ tatsächlich erst FFT-transformiert; ein Rückgriff auf die originalen $a_{k},b_{k}$ wird ja aus Effizienzgründen zur Erreichung der schnellen Komplexitätsschranke gerade vermieden, wenn ich es noch recht sehe, oder?--JFKCom 01:02, 11. Jan. 2007 (CET)

Ich konnte beim (schnellen) durchlesen des Artikels nicht finden warum man am Ende die

$c_{l}=\sum _{i+j=l}a_{i}b_{j}$

herauskommen. Ich denke dass nicht jeder der den Artikel liest die Fourier Transformation so genau kennt, dass er gleich sieht das am Ende das Produkt herauskommt. Mit fehlt etws die Grundidee. Und die ist ja mal ganz lapidar: Mit der FFT kann man im Exponenten additiv rechnen also genau die a_i und b_j filtern bei denen i+j = l. Oder liege ich da falsch? Mir ging es nicht darum ob das ganze nun in jedem Zahlenkörper funktioniert, sodern um die Idee. Das Problem ist doch die Effizienz. Wenn man mit der (von mir vermuteten) Idee multipliziert hat man Laufzeit O(n^2). Durch die superschnelle FFT bekommt man doch (durch die gleichzeitige Berechnung der c_l) erst die Laufzeit O(n*log(n)*log log (n)). Aber die Idee ist doch die von mir geschilderte, oder? --ThiloHarich 10:07, 11. Jan. 2007 (CET)

Du hast voll recht, dass im Artikel der halbverdauliche Einstieg und Überblick noch fehlt. Vielleicht schaffen wir das noch gemeinsam. Ich habe jetzt zunächst mal in einem der beiden Rekursionsschritte eine fehlende Nebenrechnung ergänzt. Hast Du die Stelle gemeint oder eine weiter hinten, wo tatsächlich die DFT durchgeführt wird?--JFKCom 15:49, 11. Jan. 2007 (CET)

Ja im Rekursionschritt ist die Idee als Einzeiler (verschleiert) drin. Bei dem Rekursionsschritt verwendest du ${\sqrt {D}}^{i}$ was etwas unschön ist. Korrekter wäre ${\sqrt[{2i}]{D}}$ ich würde aber einfach $D^{i/2}$ schrieben.Ich würde dir gerne helfen den Artikel zu verbessern. Ich könnte die Grundidee ergänzen, dass man einen Einstieg findet. Ich habe den Artikel noch nicht komplett durchgelesen. Einen anderen kleinen Tippfehler habe ich mal beseitigt.--ThiloHarich 18:54, 11. Jan. 2007 (CET)

Das mit ${\sqrt[{2i}]{D}}$ habe ich jetzt nicht verstanden. Natürlich könnten wir in der Notation das Wurzelzeichen vermeiden (geht es Dir darum?), indem wir, wenn $D=2^{2^{n}}$ ist, einfach $W:=2^{2^{n-1}}$ setzen. Dann wären die ganzen Formeln wurzelfrei. Ich finde Dein Angebot super, was zur Grundidee zu schreiben. Pflüg' doch einfach mal im Artikel rum, mit vereinten Kräften wird schon was Vernünftiges dabei rauskommen.--JFKCom 23:36, 11. Jan. 2007 (CET)

Ich werde mal an der Einführung arbeiten. Hast du irgendwelche guten Quellen? Mein Skript von damals habe ich leider nicht mehr. Eine Wurzel die pozenziert wird sieht halt blöd aus. Das mit dem $W:=2^{2^{n-1}}$ hört sich ganz gut an, während ${\sqrt[{2i}]{D}}$ natürlich vollkommener Quatsch ist. Ich meinte ${\sqrt[{2/i}]{D}}$, was aber noch irreführender ist. Habe den Artikel leider noch nicht vollständig analysiert, bin aber dabei.--ThiloHarich 10:04, 12. Jan. 2007 (CET)

Meine Hauptquelle war eben der Originalartikel von 1970/71. Darüber hinaus habe ich nichts verwertbares; insbesondere fehlt mir der Schmöker vom Knuth (Seminumerical Algorithms) im Regal.--JFKCom 14:28, 12. Jan. 2007 (CET)

Ich fange mal ne neue Einrückung an :). Ich habe mal folgende Quellen gesichtet: http://www.inf.fh-flensburg.de/lang/algorithmen/fft/polyausw.htm und http://www.cs.princeton.edu/~wayne/kleinberg-tardos/05multiply.pdf, weil ich nix anderes gefunden habe. Wenn man polynome multipliziert ist es ganz einfach. Ist ja (ohne die Überträge) eigentlich fast das gleiche. Man könnte es darüber motivieren. Deine Ausführungen sind im Vergleich dazu ziemlich kompliziert. Der eigentliche Unterschied sind doch die Überträge, oder übersehe ich da was?--ThiloHarich 17:48, 12. Jan. 2007 (CET) Noch ein Link http://www.ecs.umass.edu/ece/labs/vlsicad/ece665/slides/FFT.ppt. Nebenbei wofür braucht du den Rekursionsschritt für ungerade N?

Hi, die Links führen aber zur "normalen" Floating-point-FFT. Zu effizienten Varianten wird sehr viel sinnvolles in der en-Wiki geschrieben. Hier wird aber eine exakte "algebraische" FFT verwendet. Multiplikation mit Einheitswurzeln erfolgt durch rotierenden Shift und Addition. Details liefert das im Artikel verlinkte Schönhage-Paper (1982). Die Schönhage-Philosophie ist übrigens umgekehrt zu Deinen Intentionen: Er führt die Polynommultiplikation auf eine Langzahl-Multiplikation zurück. Und die DFT auf eine Polynommultiplikation. Per en:Bluestein's FFT algorithm. en:Bruun's FFT algorithm ist auch interessant.--LutzL 19:01, 12. Jan. 2007 (CET)(Bearb-Konflikt: reinschieb, passt inhaltlich besser)

Die Polynommultiplikation entspricht der reinrassigen Faltung. Witzigerweise ist allerdings der schnellste bekannte Algorithmus zur Polynommultiplikation in ${\mathbb {Z}}[X]$ gerade der, bei dem man unter Inkaufnahme von redundanten eingeschobenen Blöcken mit binären Nullen jedes der beiden Polynome in eine große ganze Zahl überführt (wo also jeder Koeffizient mit „Sicherheitsabstand“ binär abgelegt ist) und dann mit eben diesem Algorithmus hier die beiden Zahlen multipliziert. Allein an dieser Tatsache sieht man, dass der Schönhage-Strassen-Algorithmus definitiv mehr als ein „schneller Faltungsalgorithmus“ ist. Die Unterscheidung der beiden Rekursionsschritte ist deshalb nötig, weil beim Übergang von $2n-1$ auf $n$ ein anderer Unteralgorithmus benötigt wird als beim Übergang von $2n$ auf $n$. Steigt man rekursiv weiter herab, so kann das neue $n$ (das man wieder in etwa halbieren möchte) eben gerade oder ungerade sein.--JFKCom 18:53, 12. Jan. 2007 (CET)

Ok ihr habt recht, die allgemeine algebraische FFT ist natürlich effizienter. Habe die (deutschen Wikipedia) Artikel dazu mal gelesen, meine Erinnerungen sind doch etwas verblasst. Vielleicht sollte man sozusagen als einführenden Artikel die Polynommultiplikation anführen?--ThiloHarich 22:37, 12. Jan. 2007 (CET)

Habe mal eine Motivation in den Artikel eingebaut.--ThiloHarich 23:54, 14. Jan. 2007 (CET)

Super Anfang, das entwickelt sich in die richtige Richtung!--JFKCom 17:11, 15. Jan. 2007 (CET)