Où est l'erreur dans cet algorithme de multiplication apparemment-O (n lg n)?

Un récent blog de puzzle sur la recherche de trois réponses régulièrement espacées m'a conduit à une question de stackoverflow avec une réponse de haut niveau qui prétend le faire en temps O (n lg n). La partie intéressante est que la solution implique la quadrature d'un polynôme, référençant un article qui décrit comment le faire en temps O (n lg n) .

Maintenant, la multiplication des polynômes est pratiquement la même que la multiplication des nombres. La seule vraie différence est le manque de portées. Mais ... les portées peuvent aussi se faire en temps O (n lg n). Par exemple:

    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

Ma question est donc la suivante: où est l'erreur, ici? La multiplication des nombres en O (n lg n) est un gigantesque problème ouvert en informatique, et je doute vraiment que la réponse soit aussi simple.

• Le portage est-il faux, ou pas O (n lg n)? J'ai réalisé que lg n + 1 bits par valeur est suffisant pour suivre les portées, et l'algorithme est si simple que je serais surpris s'il était faux. Notez que, bien qu'un incrément individuel puisse prendre du temps O (lg n), le coût global pour x incréments est O (x).
• Est-ce que l'algorithme de multiplication polynomiale du papier est incorrect ou a-t-il des conditions que je viole? L'article utilise une transformée de Fourier rapide au lieu d'une transformation théorique des nombres, ce qui pourrait être un problème.
• Beaucoup de gens intelligents ont-ils manqué une variante évidente de l' algorithme Schönhage – Strassen pendant 40 ans? Cela semble de loin le moins probable.

J'ai en fait écrit du code pour l'implémenter, à l'exception de la multiplication polynomiale efficace (je ne comprends pas encore assez bien la transformation théorique des nombres). Des tests aléatoires semblent confirmer que l'algorithme est correct, donc le problème est probable dans l'analyse de la complexité temporelle.

$O(\log n)$

L'erreur ici est qu'une transformée de Fourier peut être calculée en O (n log n) étapes d'ajout ou de multiplication des nombres à transformer, mais à mesure que n devient très grand, les nombres transformés deviennent également plus gros, ce qui ajoute un autre journal de facteur log n.

En pratique, je pense que l'utilisation de virgule flottante à précision quadruple (virgule flottante 128 bits utilisant deux valeurs doubles) ou de virgule fixe 128 bits dans la FFT serait suffisante pour tout produit suffisamment petit pour être calculé.