Gdzie jest błąd w tym najwyraźniej O (n lg n) algorytmie mnożenia?

Niedawny post na łamigłówce dotyczący znalezienia trzech równomiernie rozłożonych prowadzi mnie do pytania o przepełnienie stosu z najlepszą odpowiedzią, która twierdzi, że zrobię to w czasie O (n lg n). Interesujące jest to, że rozwiązanie polega na podniesieniu kwadratu do wielomianu, odnosząc się do artykułu opisującego, jak to zrobić w czasie O (n lg n) .

Teraz mnożenie wielomianów jest praktycznie takie samo jak mnożenie liczb. Jedyną prawdziwą różnicą jest brak przenoszenia. Ale ... przeniesienia można również wykonać w czasie O (n lg n). Na przykład:

    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

Moje pytanie brzmi: gdzie jest błąd? Mnożenie liczb w O (n lg n) to gigantyczny otwarty problem w informatyce i naprawdę naprawdę wątpię, by odpowiedź była taka prosta.

• Czy noszenie jest złe, czy nie O (n lg n)? Doszedłem do wniosku, że lg n + 1 bitów na wartość wystarcza do śledzenia przeniesień, a algorytm jest tak prosty, że byłbym zaskoczony, gdyby się pomylił. Należy zauważyć, że chociaż pojedynczy przyrost może zająć czas O (lg n), łączny koszt dla przyrostów x wynosi O (x).
• Czy algorytm mnożenia wielomianowego z papieru jest nieprawidłowy, czy występują warunki, które naruszam? W pracy zastosowano szybką transformatę Fouriera zamiast transformacji teoretycznej, co może stanowić problem.
• Czy wielu inteligentnych ludzi przegapiło oczywisty wariant algorytmu Schönhage – Strassen przez 40 lat? Wydaje się to zdecydowanie najmniej prawdopodobne.

Właściwie napisałem kod, aby to zaimplementować, z wyjątkiem wydajnego mnożenia wielomianowego (jeszcze nie rozumiem wystarczająco teoretycznej transformacji liczbowej). Testy losowe wydają się potwierdzać poprawność algorytmu, więc problem prawdopodobnie występuje w analizie złożoności czasowej.

$O(\log n)$

„Błąd” polega na tym, że transformata Fouriera może być obliczona w krokach O (n log n) dodawania lub mnożenia liczb do transformacji, ale gdy n naprawdę rośnie, liczby, które są transformowane, również stają się większe, co dodaje inny czynnik log dziennika n.

W praktyce sądzę, że użycie zmiennoprzecinkowego kwadratu precyzji (128-bitowy zmiennoprzecinkowy przy użyciu dwóch podwójnych wartości) lub 128-bitowy stały punkt w FFT wystarczyłby dla każdego produktu, który jest wystarczająco mały, aby w ogóle zostać obliczony.