Schoenhage-Strassen-Algorithmus - wie auffuellen?



  • Im Wikipedia Artikel zum Schoenhage-Strassen-Algorithmus steht unter Durchfuehrung -> Rekursionsschritt fuer ein ungerades m steht, die Stückfolgen muessen "zur nächsten Zweierpotenzlänge mit Nullen aufgefüllt werden", danach kommt eine Formel.
    Ich verstehe jetzt nicht, ob die Nullen einfach alle vorne drankommen, oder ob sie jeweils eingeschoben werden (also wenn die Stueckellaenge 4 ist, dann werden immer 2 Bit genommen und die anderen beiden werden dann mit 0 aufgefuellt).
    In der Diskussion hat jemand schon einmal so eine Frage gestellt (bei Probleme bei einer echten Implemenmtation unter 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?

    darauf wird geantwortet:

    Aus den Zahlen werden, dem Verständnis nach, nicht im Computer, Polynome $E*X+$7 und D\*X+C erzeugt. Diese sind mod X4 + 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.

    Diese Antwort verstehe ich allerdings nicht wirklich. 😕

    Vielen Dank schonmal im voraus,
    etlam



  • Weiß niemand weiter? 😞

    Vielen Dank schonmal im voraus,
    etlam


Anmelden zum Antworten