Wo ist der Fehler in diesem scheinbar-O (n lg n) Multiplikationsalgorithmus?

Ein kürzlich veröffentlichter Puzzle-Blog-Beitrag über das Finden von drei gleichmäßig verteilten führte mich zu einer Stapelüberlauf-Frage mit einer Top-Antwort, die angibt , dies in O (n lg n) Zeit zu tun. Der interessante Teil besteht darin, dass die Lösung darin besteht, ein Polynom zu quadrieren und auf ein Dokument zu verweisen , das beschreibt, wie dies in O (n lg n) -Zeit getan wird .

Das Multiplizieren von Polynomen ist praktisch dasselbe wie das Multiplizieren von Zahlen. Der einzige wirkliche Unterschied ist das Fehlen von Übertragungen. Aber ... die Übertragungen können auch in O (n lg n) Zeit ausgeführt werden. Beispielsweise:

    var value = 100; // = 0b1100100

    var inputBitCount = value.BitCount(); // 7 (because 2^7 > 100 >= 2^6)
    var n = inputBitCount * 2; // 14
    var lgn = n.BitCount(); // 4 (because 2^4 > 14 => 2^3)
    var c = lgn + 1; //5; enough space for 2n carries without overflowing

    // do apparently O(n log n) polynomial multiplication
    var p = ToPolynomialWhereBitsAreCoefficients(value); // x^6 + x^5 + x^2
    var p2 = SquarePolynomialInNLogNUsingFFT(p); // x^12 + 2x^11 + 2x^10 + x^8 + 2x^7 + x^4
    var s = CoefficientsOfPolynomial(p2); // [0,0,0,0,1,0,0,2,1,0,2,2,1]
    // note: s takes O(n lg n) space to store (each value requires at most c-1 bits)

    // propagate carries in O(n c) = O(n lg n) time
    for (var i = 0; i < n; i++)
        for (var j = 1; j < c; j++)
            if (s[i].Bit(j))
                s[i + j].IncrementInPlace();

    // extract bits of result (in little endian order)
    var r = new bool[n];
    for (var i = 0; i < n; i++)
        r[i] = s[i].Bit(0);

    // r encodes 0b10011100010000 = 10000

Meine Frage lautet also: Wo ist hier der Fehler? Die Multiplikation von Zahlen in O (n lg n) ist ein gigantisches offenes Problem in der Informatik, und ich bezweifle wirklich, dass die Antwort so einfach wäre.

• Ist das Tragen falsch oder nicht O (n lg n)? Ich habe herausgefunden, dass lg n + 1 Bits pro Wert ausreichen, um die Überträge zu verfolgen, und der Algorithmus ist so einfach, dass ich mich wundern würde, wenn er falsch wäre. Beachten Sie, dass, obwohl ein einzelnes Inkrement O (lg n) Zeit in Anspruch nehmen kann, die Gesamtkosten für x Inkremente O (x) sind.
• Ist der Polynom-Multiplikationsalgorithmus aus dem Papier falsch oder habe ich Bedingungen, gegen die ich verstoße? Das Papier verwendet eine schnelle Fouriertransformation anstelle einer zahlentheoretischen Transformation, was ein Problem sein könnte.
• Haben viele kluge Köpfe 40 Jahre lang eine offensichtliche Variante des Schönhage-Strassen-Algorithmus verpasst ? Dies scheint bei weitem am unwahrscheinlichsten zu sein.

Ich habe tatsächlich Code geschrieben, um dies zu implementieren, mit Ausnahme der effizienten Polynom-Multiplikation (ich verstehe die zahlentheoretische Transformation noch nicht gut genug). Zufällige Tests scheinen zu bestätigen, dass der Algorithmus korrekt ist, sodass das Problem bei der Analyse der Zeitkomplexität wahrscheinlich ist.

$O(\log n)$

Der "Fehler" hier ist, dass eine Fourier-Transformation in O (n log n) Schritten des Addierens oder Multiplizierens der zu transformierenden Zahlen berechnet werden kann, aber wenn n wirklich groß wird, werden auch die transformierten Zahlen größer, was sich addiert ein weiterer Faktor log log n.

In der Praxis würde ich denken, dass die Verwendung eines Gleitkommas mit vierfacher Genauigkeit (128-Bit-Gleitkomma mit zwei Doppelwerten) oder eines festen 128-Bit-Punkts in der FFT für jedes Produkt ausreichen würde, das klein genug ist, um überhaupt berechnet zu werden.