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)

was ist mit https://hal.archives-ouvertes.fr/hal-02070778/document (nicht signierter Beitrag von 80.108.8.42 (Diskussion) 13:49, 6. Apr. 2020 (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)

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)

Laufzeit

Zur Laufzeit steht ja wenig drin. Hier meine Überlegungen:

Rein mathemstisch gesehen ergibt die Die Laufzeit aus

$T(2^{r})=2*T(2^{r-1})+f(2^{r})$

Wobei T(2^n) gesucht ist. Das liegt daran das ja Das Ergebnis A_r aus zwei Ergebnissen A_{r-1} gebildet wird. Der Faktor f (2^r) beschreibt den Aufwand um das Ergebnis mit w^l zu multiplieren und die Ergebnisse zu addieren. Man Kann das auch wie folg ausdrücken:

$T(n)=2*T(n/2)+f(n)$

Laut Master_Theorem ist die Lauzzeit nach wie vor Quadratisch wenn f (n) = n^2 (dann braucht alleine schon der letzte Schritt n^2 Zeit. Die Addition geht in linearer Zeit. Die Multiplikation braucht nach Schulmethode jedoch n^2. Würde man die Multiplikation weider mit schneller Schnelle Fourier-Transformation machen hätte man folgende Laufzeit:

$T(n)=2*T(n/2)+T(n/2)+O(n)$

und man wäre bei Karatsuba-Algorithmus. Da die w aber Zweierpotenzen sind führen wir nur Shifts aus. Die sind sicherlich in der Länge der Zahlen ausführbar. In diesem Fall ist f (n) = O (n), und es ergibt sich eine Laufzeit von n*log (n) wie etwa bei Mergesort.

Etwas in der Form (natürlich sauberer) wäre hilfreich, denn nur wenn wir die Multiplikation durch einen Shift ersetzen können klappt die Sache, wenn ich mich nicht verrechnet habe.--ThiloHarich 16:02, 16. Jan. 2007 (CET)

Letzteres steht im Abschnitt zur „Superschnellen DFT“ ganz unten. Statt $T$ wie oben ist im Algorithmus die Notation $\psi$ benutzt; die Herleitung läuft so „en passant“ im länglichen Lauf der Algorithmusbeschreibung und ist wohl deshalb unverständlich. Sollte wohl in einen eigenen Abschnitt separiert werden, der nach der Algorithmus-Beschreibung angehängt wird.--JFKCom 20:29, 16. Jan. 2007 (CET)

Ich habe die Komplexitätsanalyse mal im Artikel Schnelle Fourier-Transformation#Komplexität eingebaut.--ThiloHarich 00:24, 17. Jan. 2007 (CET)

Habe das Psi gefunden, etwa in Computeralgebra. Kommt im Artikel natürlich etwas kurz. Wo kommt denn jetzt das log log her?--ThiloHarich 13:31, 18. Jan. 2007 (CET)

Im Rekursionsschritt $m=2n-1$ nach $n$ steht:

Diesen Schritt der Rückführung von $m=2n-1$ auf $n$ führen wir mit der Komplexität $O\left(2^{n}\psi (2^{n})+n\cdot 2^{2n}\right)$ durch.

Hier ist $N=2^{m}$. Wenn wir als rekursives Argument reinstecken, dass die „kleineren“ Multiplikationen (der Term $\psi (2^{n})$ steht für eine solche) in der Komplexität $O(*\cdot \log(*)\log \log(*))$ durchführbar sind, ist die Komplexität $O\left(2^{n}\psi (2^{n})+n\cdot 2^{2n}\right)=O(2^{2n}\log(2^{n})\log \log 2^{n}+n\cdot 2^{2n})=O(N\log {\sqrt {N}}\log \log {\sqrt {N}}+\log N\cdot N)=O(N\log N\log \log N)$. Hierbei wurden $\log(2)$-Terme rausgekürzt, da diese innerhalb des O-Termes als Konstanten irrelevant sind. Dieses Argument geht analog für den zweiten Rekursionsschritt (m gerade).

Bei Schönhage („Schnelle Multiplikation großer Zahlen“, S. 291) geht der Schluss auf die Gesamtkomplexität wie folgt, wenn er M(n) für die Komplexität der Multiplikation 2ⁿ-stelliger Zahlen notiert:

$M(2n-2)\leq 2^{n-1}M(n)+\gamma (n-1)2^{2n-1}$,

$M(2n-1)\leq 2^{n}M(n)+\gamma (n-1)2^{2n}$.

Hieraus folgt irgendwie, dass sich der log-log-Term einschleichen muss. Es muss wohl irgendwie damit zu tun haben, dass die Rekursion nicht sofort von 2n auf n runtergeht, sondern von 2n-2 auf n (oder anders formuliert: von 2n auf n+1). Genau habe ich diesen Schritt noch nicht verstanden.--JFKCom 17:27, 18. Jan. 2007 (CET)

Zum einen weiss ich nicht wo das 2ⁿ als Faktor her kommt. Was spricht gegen meine klassische Divie and Conquer Rekursionsgleichung? Zum Anderen Vorsicht mit solchen Argumentationen. Du setzt das was du beweisen willst schon ein (also das Rho). Beispiel :$T\left(N\right)=T\left(N/2\right)+f(N)$ wenn wir nun T(n/2) = $\psi (n)$ = O(n) annehmen und f(n) also die Addition ebenfalls linear annehmen, dann zeigen wir T (n) = O (n), was ja nicht stimmt. Wir müssen hier also schon genau rechnen. Ich habe mir auch noch mal deinen Rekursionsschritt angesehen. Irgendwie raff ich nicht worauf du damit raus willst. Wechseln wir wirklich den Zahlenkörper in dem wir rechnen? Ich habe gedacht, wir nehmen den neuen Körper, weil er dem entspricht wie die aktuellen Rechner rechnen?--ThiloHarich 18:16, 21. Jan. 2007 (CET)

Ich habe in meinem obigen Beitrag ein falschen n durch 2ⁿ ersetzt. Dies erklärt den Kofaktor 2^n-1 bzw. 2ⁿ, richtig? Zum zweiten Teil: Wir wechseln im Algorithmus tatsächlich immer wieder fröhlich die Zahlenringe (im allgemeine sind dies keine Körper); und genau dieser Part ist für die übliche von Hauptprozessoren bereitgestellte Arithmetik etwas sperrig umzusetzen, was ja gerade der Grund ist, dass allgemein ein großer Bogen um diesen Algorithmus gemacht wird, obwohl er für richtig große Zahlen der mit Abstand beste Algorithmus überhaupt ist.--JFKCom 20:33, 21. Jan. 2007 (CET)

Meine Grundproblem warum man die Multiplikation nicht einfach mit der stinknormalen Schnelle_Fourier-Transformation machen kann (die ja schneller ist, eben um den Faktor log log (n)) wird in folgendem Link http://numbers.computation.free.fr/Constants/Algorithms/fft.html angerissen. Das Resultat ist ungenau. Daher wird beim Schönhage Strassen Algorithmus im Restklassen Ring gerechnet. Das wäre als (weitere) Motivation vielleicht auch nicht schlecht.

Du Schreibst: Eine gewöhnliche (oben beschriebene) FFT wäre nicht schnell genug, um die zu erzielende Komplexitätsschranke zu erreichen. Das ist erst mal verwirrend, denn die Lauzeit der normalen FFT ist ja besser als die des Schönhage Strassen Algorithmus, und rein mathematisch gesehen kommt ja das Richtige raus (ohne die Überträge). Es scheint wohl wirklich an den Rechenungenauigkeiten zu liegen dass man den normalen FFT Algorithmus in der ursprünglichen Form nicht anwenden kann. In der Praxis setzt man ihn ja wohl doch ein. Muss noch Quellen dazu checken.--ThiloHarich 10:06, 23. Jan. 2007 (CET)

Moment, langsam. Die „normale FFT“ rechnet in $\mathbb {C}$ mit Einheitswurzeln, die auf dem Kreis liegen und (im Allgemeinen) gar keine Darstellung mit rationalen Koordinaten besitzen, deshalb ist hier exakte Arithmetik gar nicht möglich (allerdings gibt es eine Variante, die approximativ dieses Verfahren durchzieht, und zwar mit einer so hohen Genauigkeit, dass der Fehlerterm im Endergebnis nach Abschneiden der unerwünschten Stellen rauskorrigiert wird und das Endergebnis exakt rekonstruiert wird. Dieser Algorithmus wird aber nicht hier beschrieben, und jedenfalls ist er höchstens gleichschnell wie der hier beschriebene). Ich denke, Du bringst momentan die Komplexität in Anzahl von Rechenschritten (so was wie „flops“) mit der Bitkomplexität (Anzahl benötigter Bitoperationen; das ist im komplexitätstheoretischen Sinne gleichbedeutend mit „Anzahl elementarer arithmetischer Operationen auf Bytes“ oder ähnlichem) durcheinander. Eine FFT braucht immer $O(n\log n)$ elementare Rechenschritte (Additionen oder Multiplikationen im Zahlkörper oder Zahlenring), aber die Frage ist hier, mit wieviel Bitoperationen man bei N-stelligen ganzen Zahlen auskommt.--JFKCom 20:29, 23. Jan. 2007 (CET)

Ich stimme dir bei deinen Aussagen voll zu, sehe aber nicht dass diese im Wiederspruch zu dem stehen was ich geschrieben habe. Du kannst den Bereich auch wieder ändern. Ich wollte nur klar machen warum die normale schnelle Forurier Transformation hier (also in O (n* log (n)) nicht das richtige Ergebnis liefert. Das war mir nämlich bis gestern nicht so klar.--ThiloHarich 12:57, 24. Jan. 2007 (CET)

Ok, war wohl bloß kleines Missverständnis. Wir sind uns ja einig. Was meinst Du mit „Bereich auch wieder ändern“? Das habe ich nicht verstanden.--JFKCom 19:42, 24. Jan. 2007 (CET)

Ich habe den Artikel in dem Bereich "Eine gewöhnliche (oben beschriebene) FFT wäre nicht schnell genug, um die zu erzielende Komplexitätsschranke zu erreichen." umgearbeitet. Deine letzte Argumentation trifft den Kern teilweise besser als meine. --ThiloHarich 11:26, 25. Jan. 2007 (CET)

Noch mal ne generelle Frage. Wir rechnen ja exakt im Restklassenring. Als Ergebnis erhalten wir pro Stelle maximal log (N) Bits. D.h. wir müsste mit insgesamt N * log (N) bits rechnen. Wir erhalten folgende Laufzeit N * log (N) * log (log N * log log N) = N * log (N) * (log log N) + log log log N)) = O (N * log (N) * log log N)). Um im Ring mit zyklischer Arithmetik rechnen zu können, müssen wir leider mit log² (N) bits rechnen und würden die angestrebte Laufzeit verfehlen. In http://citeseer.ist.psu.edu/rd/0%2C592534%2C1%2C0.25%2CDownload/http://citeseer.ist.psu.edu/cache/papers/cs/29286/http:zSzzSzcs.nyu.eduzSzchenlizSzpaperszSzqmul.pdf/yap00quickmul.pdf oder http://ww3.algorithmdesign.net/sample/ch10-crypto.pdf wird mit einer endlichen Arithmetik gerechnet, die nur ein paar der 32 Bits verschnwendet. Man könnte diese Links einfügen, bzw. damit den Schönhage Strassen Algorithmus weiter motivieren, oder wird das dann zu lange? Wenn ich den/deinen rekursiven Schritt richtig verstanden habe, rechnen wir dort immern in einem Ring, der gerade der aktuellen Stellenlänge entspricht? Dann wird die Laufzeit vom letzen Schritt dominiert, und es könnte hinkommen (mit der Laufzeit).--ThiloHarich 15:36, 30. Jan. 2007 (CET)

Bei Teilen deiner Ausführungen steig' ich momentan nicht durch. Im Algorithmus ist die Stückelungsgröße gerade so, dass die Aufgabe der Multiplikation von Zahlen mit $2^{2n-1}$ bzw. $2^{2n-2}$ Binärziffern auf FFT-Rechnen mit $2^{n}$ Binärziffern zurückgeführt wird. Ist beispielsweise n=6, so wird Multiplikation 2048-stelliger Zahlen auf die 64-stelliger Zahlen zurückgeführt. Deine Rechnungen mit $\log N$ verstehe ich im Moment gerade nicht, bin allerdings auch gerade nicht sehr „fit drauf“.--JFKCom 18:35, 30. Jan. 2007 (CET)

Vergiss das mit dem log (N) ist ein Denkfehler von mir. Werde die Links aber mal anhängen.--ThiloHarich 11:27, 31. Jan. 2007 (CET)

Probleme bei einer echten Implemenmtation

Hallo,

ich probiere gerade seit Wochen mit Hilfe dieser Seite den SchönStrAlg auf meinem Computer umzusetzen, aber bisher gelingt mir das nicht. Einige der Probleme, auf die ich gekommen bin, möchte ich hier einfügen. Ich beziehe mich auf den Abschnitt Durchführung:

• 1) a,b mit N<=$2^{n}$ Binärziffern => $a,b<=2^{2^{n}}-1$, aber $a,b\in \mathbb {Z} _{F_{m}}$ => $a,b<=2^{2^{n}}$

Das beisst sich. In den Summen darunter läuft der Index dann von 0 bis n, so das man $2^{n}+1$ Stücke mit je $2^{n-1}$ Bits hätte, das ist ein Stück zuviel, wenn man bedenkt, das a,b eben nicht gleich $E=2^{2^{n}}$ sein darf.

• 2) Dann müssen Nullen eingefügt werden, aber mir ist nicht klar geworden wie.

Beispiel: ich möchte die Hexadezimalzahlen $E7 und $DC multiplizieren. In Binärdarstellung lautet das:

%1110.0111 * %1101.1100

Fasse ich nach dem Einfügen der Nullen diese Aufgabe als

%0000.0000.1110.0111 * %0000.0000.1101.1100 oder als

%0011.0010.0001.0011 * %0011.0001.0011.0000 auf?

Ich denke, es soll die 2. Art sein, dann aber werden doch die Stücke $a_{i},b_{j}$ umindiziert...

• 2a) Halbierte Stellenzahl von D geht nicht: D ist eine reine Zweierpotenz, also binär eine 1 mit $2^{n}$ Nullen, hat also ungerade Stellenzahl (ausser im Trivialfall n=0). Es soll wohl etwa so heissen: halbierte Anzahl der Nullen von D in Binärdarstellung

• 3) Weiter kommt dann folgende Formel:

$c_{k}=\sum _{i,j=0 \atop i+j\equiv k\mod 2^{n+1}}^{2^{n+1}-1}a_{i}\cdot b_{j}=\sum _{i=0}^{2^{n+1}-1}a_{i}\cdot b_{k-i}+a_{i}\cdot b_{2^{n+1}+k-i}+a_{2^{n+1}+i}\cdot b_{k-i}+a_{2^{n+1}+i}\cdot b_{2^{n+1}+k-i}$

Ist diese Umformung richtig? Ansonsten kann ich mir nichts darunter vorstellen. Was danach kommt, soweit bin ich noch nicht.

• 4) Aber auch $\alpha _{j}=a_{j}\mod 2^{n+2}$ gibt irgendwie keinen Sinn für mich, die $a_{i}$ sind bei mir nach wie vor Stücke mit n-1 Bits, die soll ich jetzt auf n+2 Bits 'kürzen'?

Wie gesagt, beim Rest blicke ich im Moment noch gar nicht durch, obwohl die Module zu einer reinen Zweierpotenz und zu Fermatzahlen sehr einfach zu bilden sind. Aber inzwischen fehlt mir jeglicher Überblick, welche Stücke wo sind, und wie sie indiziert sind. Dass der SchönStrAlg bei einfachen Multiplikationen wesentlich komplizierter wird als die Schulmethode bzw. Karatsuba ist mir klar, aber ohne ein durchgerechnetes Beispiel kann man meiner Meinung nach diesen Algorithmus nicht mehr nachvollziehen.

• 5) Noch ein Verständnisproblem: In dem Beispiel $E7*$DC werden 2 Zahlen mit m=3, also $2^{3}=8$ Bit multipliziert.

Das müsste ich auf Multiplikationen mit n=2, also $2^{2}=4$ , also 4 Bits zurückführen können. Ich sehe aber ausschlieslich Multiplikationen mit 2 Bit Stücken...

mfg

Matthias Wurtinger am 18. Apr. 2007, 20:24 (5 mal ~ ergibt einen Zeitstempel)

Ich habe mir mal erlaubt, eine Abschnittsüberschrift einzufügen und den Text etwas zu strukturieren, auf dass man auf die einzelnen Punkte besser antworten kann.--LutzL 12:00, 19. Apr. 2007 (CEST)

zu 1.) Das soll wohl heißen, dass $a,b\in \mathbb {Z} _{F_{m}}$ eindeutig identifizierbar sind, wenn man die Zahlen $0,1,\dots ,2^{2^{n}}$ als Repräsentanten der Restklassen wählt.

zu 2.) Aus den Zahlen werden, dem Verständnis nach, nicht im Computer, Polynome $E*X+$7 und $D*X+$C erzeugt. Diese sind mod $X^{4}+1$ zu multiplizieren, die dabei auftretenden Summen können die Größe 2*16*16 nicht überschreiten, also müssen die Koeffizienten in mindestens 9, also 16 Bits dargestellt werden. Als Polynome 3. Grades mit 2-Bit-Koeffizienten ergeben sich Zwischensummen der Größe 4*2*2=16, diese Reduktion ergibt wirklich einen Abstieg in der Bitzahl von 8 auf 4.

zu 3.) Verstehe ich auch nicht auf die Schnelle. Muss was mit dem Übergang zur Fourier-Transformation zu tun haben.

zu 4.) Man will ja am Ende Zahlen haben, keine Restklassen. Dies besagt einfach, dass der kleinste positive Representant der Restklasse auch wirklich die gesuchte Zahl ist.

zu 5.) siehe 2., die Reduktion auf 4Bit-Stücke ist nicht wirklich sinnvoll.

--LutzL 12:25, 19. Apr. 2007 (CEST)

Ich versuche auch mal, zu 1) bis 3) zusätzlich Hilfestellung zu geben.

Zu 1) Im Rekursionsschritt wird die Ausgangs-Multiplikationsaufgabe mit Zahlen aus $\mathbb {Z} _{F_{m}}$ auf kleinere Multiplikationsaufgaben mit Zahlen aus $\mathbb {Z} _{F_{n}}$ zurückgeführt, wobei $m=2n-1$ oder $m=2n-2$ ist. Beim Start der Rekursion mit der Ursprungsaufgabe sind allerdings üblicherweise nicht $a,b\in \mathbb {Z} _{F_{m}}$ vorgegeben, sondern ganze Zahlen, deren Bitlänge vorgegeben ist; zur maximalen Länge dieser beiden Eingabezahlen $a,b\in \mathbb {N}$ sucht man sich also anfangs das passende $m$, so dass für die Ausgangszahlen eben $a,b\in \mathbb {Z} _{F_{m}}$ gilt. Dabei wird die Ausgangs-Bitstellenanzahl der beiden Inputzahlen eventuell vergrößert; dies ist ein Overhead, der bei diesem Algorithmus zumindest in seiner hier dargestellten Urform definitiv vorliegt.

Zu 2) Du hast recht, die Formulierung ist unpräzise; man geht von der Stellenanzahl $2^{n}+1$ runter auf $2^{n-1}+1$ Stellen (z. B. von 33 auf 17, von 17 auf 9 usw.), also wäre die Formulierung „in etwa halbierte Stellenzahl“ treffender.

Zu 3) Es ist komplizierter. Die Formel $c_{k}=\sum _{i,j=0 \atop i+j\equiv k\mod 2^{n+1}}^{2^{n+1}-1}a_{i}\cdot b_{j}$ bedeutet, dass über alle Indizes $i,j\in \{0,\ldots ,2^{n+1}-1\}$ summiert wird, deren Summe $i+j=k$ oder $i+j=k+2^{n+1}$ ergibt. Zu jedem $i$ gibt es zwar höchstens ein passendes $j$, aber da dies auch von $k$ abhängt, lässt sich die Summationsformel nicht bedeutend einfacher als in dieser Form hinschreiben. Man könnte höchstens sagen: Zu jedem $i$ nehme aus den Werten $k-i$ und $k+2^{n+1}-i$ denjenigen für $j$, der im zulässigen Indexzahlenbereich $\{0,\ldots ,2^{n+1}-1\}$ zu liegen kommt.--JFKCom 20:20, 19. Apr. 2007 (CEST)

Zu 5) Falls Du den eigentlichen Rekursionsschritt meinst, der geht schneller runter: Er halbiert (in etwa) pro Schritt nicht die Stellenzahl, sondern den binären Logarithmus der Stellenzahl.--JFKCom

Vielen Dank an LutzL für die Strukturierung, so sieht das in der Tat gleich viel übersichtlicher aus. Ich habe nur noch in meinem obigen Beitrag einen kleinen Punkt 2a) separiert, er ist für mich eine eigene Sache. Ich muss zugeben, das ich mir nicht mehr sicher bin, ob ich hier weitermachen soll oder evtl. eine eigene Seite einmal erstellen sollte. Denn meine Probleme kommen, wie gesagt, daher, das ich versuche diesen Algorithmus tatsächlich auf dem Computer zu programmieren (in Pascal/Assembler). Viele deiner Aussagen sind mir vom 'abstrakt' mathematischen her ziemlich klar, sie nützen mir aber wenig um herauszufinden wie ich welche Stücke wann (d.h. in welcher Reihenfolge) zu manipulieren habe (im Computer...). Insofern interessiert mich (im Moment) nicht der mathematische Beweis dieses Algorithmus'. Eine Seite, evtl. im Informatik-Bereich, wäre wahrscheinlich nützlicher für mich.

zu 1.) Mir ist klar, was du mathematisch hier sagst. Aber ein Programmierer dieses Algo's kommt irgendwann darauf, das $Z_{F_{m}}$ ein Element mehr enthält, als durch a (oder b) darstellbar ist. Irgendwie reden wir hier aneinander vorbei.

zu 2.) Wenn du hier geschrieben hättest:

'Aus den Zahlen werden, dem Verständnis nach, nicht im Computer, Polynome $\$E*X^{2}+\$7$ und $\$D*X^{2}+\$C$ erzeugt.'

würde ich jetzt einen Luftsprung machen und 'Heureka' brüllen, so verwirrt mich das eher. Dafür brauche ich ein paar Tage... (warum nur lineare Terme?)

zu 3.) ich dachte eigentlich, diese Summenumformung wäre das einfachste, wo ist hier was von FFT?

zu 4.) Wir reden hier einfach eineinander vorbei. Natürlich möchte ich Zahlen haben und keine Restklassen.... wobei im Computer *alle* Zahlen nur Elemente aus Restklassen sind. Ich muss aber Bits und Bytes verschieben, umordnen, sonstwie manipulieren. Aus meiner Sicht steht da einfach folgendes: $a_{i}$ ist ein Stück aus n-1 Bits und $\alpha _{i}=a_{i}$, wobei ich mir vorne 3 Nullen vorangestellt denke, also $\alpha _{i}$ als (n+2)-Bit Zahl auffasse, aber ich bin mir halt nicht sicher

zu 5.) Das dieses Beispiel der Multiplikation zweier 8-Bit Zahlen mit Hilfe des SchönStrAlg nicht wirklich sinnvoll ist, denke ich erwähnt zu haben. Immerhin gibt es inzwischen 64-Bit Prozessoren...Darum geht es mir, wie jetzt schon öfters erwähnt, auch nicht. Der Begriff 'Durchführung' impliziert für mich geradzu die Realisation des Algorithmus auf einem Computer. Wie du sagtest, er ist nicht sinnvoll für kleine Zahlen mit nur wenigen Bits. Also muss er auf Zahlen mit vielen Bits angewendet werden. Also muss er auf dem Computer 'realisiert' oder 'durchgeführt' werden. Kein Mensch würde Zahlen mit tausenden von Bits per Hand multiplizieren. Und wenn doch einmal, würde er selbst dann nicht den SchönStrAlg verwenden. Das Lebensalter eines Menschen dürfte nicht ausreichen, um den SchönStrAlg auf 2 Zahlen mit sovielen Bits per Hand anzuwenden, das er 'sinnvoll' (d.h. schneller als mit anderen Verfahren) würde. Aber selbst ein 'sinnloses' Beispiel könnte Klarheit über einige Fragen geben, die bei der rein theoretischen Betrachtung einfach wegfallen. Der Mathematiker muss Zahlen halt nicht als Gruppierung von (heutzutage) 32- oder 64-Bit Blöcken ansehen, der Programmierer bei der Realisation schon.

Ich suche quasi einen Ablaufplan für folgenden Vorgang: Es liegen 3 Speicherbereiche A, B und C vor. A und B enthalten (natürlich in Binärdarstellung mit je $2^{m}$ Bit) die Zahlen a und b, C (mit $2^{m+1}$ Bit) ist mit Nullen gefüllt. Wie muss ich nun die Bits und Bytes der Speicherblöcke manipulieren um in C das Produkt c der Zahlen a und b zu erhalten. Ich denke, wie gesagt, für diese Aufgabe bräuchte man eine Seite der Wiki bei den Informatikern. Ich selber habe aber noch nie eine solche Seite erstellt und weiss nicht, wie es geht oder was ich da machen müsste. Evtl. ist die Frage auch gar nichts für die Wikipedia.

mfg

Matthias Wurtinger

(Anmerkung: habe ich noch ohne Durchsicht der letzten Änderung von JFKCom abgespeichert)

So, heute dann vielen Dank an JFKCom. Du sprichst oft eine Sprache, die ich sehr viel besser während des Versuches der Realisation des Algo's verstehe, sie liegt für mich näher an der praktischen Seite.

zu 1.) Das wären exakt ein paar Formulierungen, die mir folgendes klarmachen: a und b sind meine Ausgangszahlen mit je $2^{m}$ Bits (wobei ich evtl. die Zahlen mit der entsprechenden Anzahl an Nullen 'vorne' aufgefüllt habe). Dies sind Zahlen aus $\mathbb {Z} _{E}$ mit $E=2^{2^{m}}$. Diese (unveränderte) Bitfolge fasse ich nun als Zahl zu einer anderen Basis $F_{m}=E+1=2^{2^{m}}+1$ auf. Dadurch 'schleicht' sich ein 'kleiner Fehler' bei der nun folgenden Berechnung ein, der aber *exakt* durch die darauf folgende Korrekturrechnung über die Module wieder ausgeglichen wird.

zu 3.) Diese Antwort schockiert mich... was habe ich den da falsch gemacht? An sich kommt mir es so vor, das meine Summenumformung exakt das macht, was du mir zu erklären versuchst, ich finde keinen Unterschied. Ich summiere über ein Indexpaar das von k abhängt, ich habe einfach die Abhängigkeit von k aufgelöst bezüglich des Moduls und innerhalb der inneren Summe ist das k doch konstant...wie lautet den eine 'verständlichere' Umformung, wenn es schon keine 'einfachere' gibt?

zu 2. und 5.) Vorsicht, diese beiden Sachen haben nichts miteinander zu tun. Die erste Frage lautet:

• 1) Wie stückele ich die Zahlen a und b mit je $2^{m}$ Bits?

Meine momentane Antwort: a ist eine Zahl mit $2^{m}$ Bits. Je nachdem ob m ungerade oder gerade ist wird folgende Stückelung vorgenommen:

m ungerade, $m=2n-1$. a hat $2^{2n-1}$ Bits, ich bilde $2^{n}$ Blöcke mit jeweils $2^{n-1}$ Bits (meinetwegen auch Bits pro Block, rein physikalisch). Produkt Blöcke*(Bits pro Block) stimmt exakt. Das rechnen mit Zahlen mit $2^{2n-1}$ Bits wird auf das rechnen mit Zahlen mit $2^{n-1}$ Bits reduziert, daraus 2 korrekte Aussagen für den ungeraden Fall:

Der binäre Logarithmus der Stellenzahl von a wird *mehr* als halbiert (wegen 2(n-1)<2n-1 )

Die Stellenzahl von a wird *mehr* als 'gewurzelt' (wegen $2^{2(n-1)}<2^{2n-1}$)

m gerade, $m=2n-2$. a hat $2^{2n-2}$ Bits, ich bilde $2^{n-1}$ Blöcke mit jeweils $2^{n-1}$ Bits (meinetwegen auch Bits pro Block, rein physikalisch). Produkt Blöcke*(Bits pro Block) stimmt wiederum exakt. Das rechnen mit Zahlen mit $2^{2n-2}$ Bits wird auf das rechnen mit Zahlen mit $2^{n-1}$ Bits reduziert, daraus 2 korrekte Aussagen für den geraden Fall:

Der binäre Logarithmus der Stellenzahl von a wird *exakt* halbiert (wegen 2(n-1)=2n-2 )

Die Stellenzahl von a wird *exakt* 'gewurzelt' (wegen $2^{2(n-1)}=2^{2n-2}$)

hieran kann man irgendwie erkennen, warum Prozessoren besser oder 'lieber' mit einem ungeraden m gebaut wird, man kann einfach die Stellenzahl stärker reduzieren.

bei einem 'geraden' Rekursionsschritt habe ich soviele Blöcke wie (Bits pro Block), bei einem 'ungeraden' Rekursionsschritt habe ich doppelt soviele Blöcke wie (Bits pro Block), man 'spart' quasi die Hälfte der Bits (pro Block)...

Diese, für mich fast 'geometrisch' offensichtliche Logik, gilt aber nur, solange auf ein n reduziert wird, das grösser als 2 ist. Sobald man zu einem der beiden 'letztmöglichen' Rekursionsschritte kommt (also für ungerade m von m=3 auf n=2, bzw. für gerade m von m=2 auf n=2) dreht sich die oben angegebene Logik irgendwie um.

Bei Reduktion von m=3 auf n=2 gilt:

Der binäre Logarithmus der Stellenzahl wird *fast* halbiert

Die Stellenzahl wird *fast* gewurzelt

Bei Reduktion von m=2 auf n=2 (wobei hier 'Reduktion' rein mathematisch aufgefasst wird ;) ) gilt:

Der binäre Logarithmus der Stellenzahl wird *gar nicht* halbiert

Die Stellenzahl wird *gar nicht* gewurzelt

daran erkennt man, das das von mir gewählte Beispiel der Multiplikation zweier Zahlen mit je 8 Bit tatsächlich 'sinnlos' ist, denn es 'verschleiert' eher wesentliche Eigenschaften des SchönStrAlg als das es diese zu erklären vermag.

Allerdings habe ich unter 5) den binären Logarithmus der Stellenzahl m=3 korrekt auf n=2 *fast* halbiert, dabei entstand durch die *fast* 'wurzelung' der Stellenzahl $2^{m}=2^{3}=8$ auf $2^{n}=2^{2}=4$ Bits 'zufällig' eine exakte Halbierung eben der Stellenzahl :D omg...

Ein wesentlicher Unterschied zwischen dem Karatsuba-Algo und dem SchönStrAlg für mich zum Verständnis ist folgendes: Der K-Algo zerlegt eine Zahl in 2 Blöcke der halben Stellenzahl, beim SchönStrAlg werden entweder $2^{n}$ oder $2^{n-1}$ Blöcke mit je $2^{n-1}$ Stellen (oder Bits) gebildet.

• 2) Wie verfahre ich mit den Blöcken mit je $2^{n-1}$ Bits weiter?

(hier kommt nachher noch was, ich muss erst mal pause machen)

(ich füge hier einmal eine Passage ein, die später wieder gelöscht wird. Aber ich kann nicht weitermachen, solange ich nicht weiß, ob im obigen Punkt 1 ein Logikverhaspler ist oder nicht. Wenn nämlich *vor* dem stückeln der Zahlen a und b diese nicht nur auf die Bitanzahl $2^{m}$ des 'nächstmöglichen' m mit Nullen aufgefüllt wird, sondern dieser Speicherbereich noch einmal verdoppelt wird (also quasi schon auf Ergebnisgröße C) mit $2^{m+1}$ Bits, dann dreht sich in obiger Logik das Verhalten bezüglich geradem/ungeradem m irgendwie noch einmal um. Falls noch einer mitkommt, ich bitte um Hilfe und Denkanstoß... :D

mfg

Matthias

Fehler in Einleitung

Welche Basis hat der Logarithmus in der Einleitung? --mik81 15:56, 20. Nov. 2007 (CET)

Keine spezifizierte, und zwar mit Absicht. Siehe Computer-Algebra#Effiziente exakte Arithmetik mit ganzen Zahlen.--JFKCom 22:32, 20. Nov. 2007 (CET)

Summation über Indexgrenzen hinaus unter "Grundidee/Terminologie"

Die betrachteten Polynome A und B sind definiert als $A=\sum _{i=0}^{2^{n}-1}a_{i}\cdot X^{i}$ und $B=\sum _{i=0}^{2^{n}-1}b_{i}\cdot X^{i}$. Die Formel für C, $C=\sum _{l=0}^{2^{n+1}-1}\sum _{i=0}^{l}a_{i}b_{l-i}\cdot X^{l}$ ist meines Erachtens nach falsch, da sie unmögliche Indizes i aus dem Interval $[2^{n},2^{n+1}-1]$ für a und b benutzt, i > $2^{n}-1$.

Eine korrekte Formel für $C=A\cdot B$ wäre

$C=\sum _{i=0}^{2^{n}-1}\sum _{k=0}^{i}a_{k}b_{i-k}\cdot X^{i}+\sum _{i=1}^{2^{n}-1}\sum _{k=i}^{2^{n}-1}a_{2^{n}-1-k}b_{k}\cdot X^{2^{n}-1+i}$ und damit für $C=\sum _{i}^{2m}c_{i}\cdot X^{i},m=2^{n}-1$: $c_{i}={\begin{cases}\sum _{k=0}^{i}a_{k}b_{i-k}&{\mbox{für }}i\leq m\\\sum _{k=i}^{m}a_{m-k}b_{k}&{\mbox{für }}i>m\end{cases}}$.

-- 92.193.172.105 19:27, 27. Jul. 2010 (CEST)

Fürer

Martin Fürer per IP mit Selbst-Quelle. Gibt es dazu dritte Quellen? --Logo 01:30, 16. Mär. 2013 (CET)

Triviale Lineare Laufzeit

Wieso soll es linear gehen? Ich denke die Vermutung ist, dass es nicht besser als n log n geht! Eine Erklärung wäre nicht schlecht (nicht signierter Beitrag von 85.180.130.178 (Diskussion) 17:25, 5. Apr. 2013 (CEST))

Bitte stelle vollständige Fragen. Dann wäre aufgefallen, dass es um eine untere Schranke der Laufzeit geht. Und die ist trivial, da in das Ergebnis alle Koeffizienten eingehen, d.h. jeder von diesen wenigstens einmal gelesen werden muss.--LutzL (Diskussion) 18:13, 5. Apr. 2013 (CEST)