Di mana kesalahan dalam algoritma multiplikasi yang tampaknya-O (n lg n) ini?

Sebuah posting blog teka - teki baru - baru ini tentang menemukan tiga yang berjarak sama rata membawa saya ke pertanyaan stackoverflow dengan jawaban teratas yang mengklaim melakukannya dalam waktu O (n lg n). Bagian yang menarik adalah solusinya melibatkan mengkuadratkan polinomial, mereferensikan makalah yang menjelaskan bagaimana melakukannya dalam waktu O (n lg n) .

Sekarang, mengalikan polinomial bisa dibilang sama dengan mengalikan angka. Satu-satunya perbedaan nyata adalah kurangnya membawa. Tapi ... membawa juga dapat dilakukan dalam waktu O (n lg n). Sebagai contoh:

    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

Jadi pertanyaan saya adalah ini: di mana kesalahannya, di sini? Mengalikan angka dalam O (n lg n) adalah masalah terbuka raksasa dalam ilmu komputer, dan saya benar-benar ragu jawabannya akan sesederhana ini.

• Apakah membawa salah, atau tidak O (n lg n)? Saya telah bekerja bahwa lg n +1 bit per nilai sudah cukup untuk melacak membawa, dan algoritma ini sangat sederhana saya akan terkejut jika itu salah. Perhatikan bahwa, meskipun kenaikan individual dapat memakan waktu O (lg n), biaya agregat untuk x peningkatan adalah O (x).
• Apakah algoritma multiplikasi polinomial dari kertas salah, atau memiliki kondisi yang saya langgar? Makalah ini menggunakan transformasi fourier cepat alih-alih transformasi angka teoretis, yang bisa menjadi masalah.
• Sudahkah banyak orang pintar melewatkan varian yang jelas dari algoritma Schönhage-Strassen selama 40 tahun? Ini tampaknya paling tidak mungkin.

Saya sebenarnya sudah menulis kode untuk mengimplementasikan ini, kecuali untuk perkalian polinomial yang efisien (saya belum mengerti angka yang bertransformasi teoretis dengan cukup baik). Pengujian acak muncul untuk mengkonfirmasi algoritma yang benar, sehingga masalah ini kemungkinan dalam analisis kompleksitas waktu.

$O(\log n)$

"Kesalahan" di sini adalah bahwa transformasi Fourier dapat dihitung dalam langkah-langkah O (n log n) untuk menambah atau mengalikan angka-angka yang akan diubah, tetapi ketika n tumbuh sangat besar, angka-angka yang ditransformasikan menjadi semakin besar juga, yang menambahkan log faktor lain n.

Dalam prakteknya, saya akan berpikir bahwa menggunakan floating point presisi quad (floating point 128 bit menggunakan dua nilai ganda) atau titik tetap 128 bit dalam FFT akan cukup untuk setiap produk yang cukup kecil untuk dihitung sama sekali.