Schönhage-Strassen Algorithmus
-
Hallo,
Ich versuche gerade den Schönhage-Strassen Algorithmus soweit zu verstehen, dass ich ihn anwenden kann.
Ich beziehe mich auf das englische Wikipedia (http://en.wikipedia.org/wiki/Schönhage-Strassen), unter Overview.Schritt 1: Soweit ich das verstanden hat, hat man die Zahlen x und y, und es wird xy mod 2N + 1 ausgerechnet. Um das xy zu bekommen muss man also N entsprechend groß wählen. Wenn xl die Ziffernanzahl in der Binärschreibweise von x ist und yl das selbe für y, so dachte ich mir, kann man einfach N=xl+yl wählen. Dann ist 2N + 1 sicher größer als xy.
Schritt 2: Dann soll man 2k so wählen, dass es N teilt. Als Beispiel ist angegeben: "e.g. 12345678 -> (12, 34, 56, 78)". Dieses Beispiel verstehe ich nicht. Ist das Beispiel richtig? Bei 12345678/12 kommt 1028806.5 raus. 2^12 ist 4096 und auch 4096 teilt 12345678 nicht? 12345678/4096=3014.0815 . Deshalb verstehe ich dieses Beispiel nicht. Man müsste dan einfach zu dem N von Schritt 1 noch entsprechend etwas dazu tun, so dass es teilt.
Schritt 3: Unter 2. steht "In order to make progress, it's necessary to use a smaller N for recursive multiplications. For this purpose choose n as the smallest integer at least 2n/2k + k and divisible by 2k.". Im zweiten Satz taucht auf einmal ein kleines n auf. Meinen die Autoren damit noch immer N oder etwas anderes? Und n soll dann mindestens 2n/2k + k sein und sich dann durch 2^k teilen lassen. Muss man dann von k aus gehen?
Schritt 4: Vielleicht so?: Man nimmt k irgenetwas, z.B. 4. Dann n>2n/16+1. Man nimmt n = 16*u ()so ist das mit dem teilen ok). n>2*16*u/16+1 --> n>2u+1 u=n/16, also ist n>n/8+1 und man nimmt nun u=1 und schon klappt das eigentlich, oder?Naja, bis hierhin erstmal. Es wäre sehr nett wenn ihr mir sagen könntet, was bis hierhin alles falsch und nicht gut verstanden ist.
Vielen Dank schonmal im voraus,
etlam
-
zu 2: Jetzt verstehe ich das Beispiel, wie dumm von mir: k ist 2 und deswegen wurde 12345678 in 4 Stücke zerlegt.
zu 3: Ich glaube, es wird ein neues n benutzt (welches dann später noch benutzt wird).Ist 4. denn richtig? Ist es schlimm für den Schönhage-Strassen Algorithmus, wenn nicht das kleinste n herausgefunden wurde?
Vielen Dank schonmal im voraus,
etlam