1

最近一篇关于找到三个均匀间隔的谜题的博文将我引向了一个stackoverflow 问题，其中一个最佳答案声称可以在 O(n lg n) 时间内完成。有趣的部分是该解决方案涉及对多项式进行平方，参考描述如何在 O(n lg n) 时间内完成它的论文。

现在，多项式相乘实际上与数字相乘相同。唯一真正的区别是缺少进位。但是...进位也可以在 O(n lg n) 时间内完成。例如：

    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

所以我的问题是：这里的错误在哪里？O(n lg n) 中的数字相乘是计算机科学中一个巨大的开放性问题，我真的很怀疑答案会这么简单。

  • 携带错误，还是不是 O(n lg n)？我已经计算出每个值 lg n + 1 位足以跟踪进位，并且算法非常简单，如果它是错误的，我会感到惊讶。请注意，虽然单个增量可能需要 O(lg n) 时间，但 x 个增量的总成本是 O(x)。
  • 论文中的多项式乘法算法是错误的，还是有我违反的条件？该论文使用快速傅立叶变换而不是数论变换，这可能是一个问题。
  • 40 年来，有很多聪明人错过了Schönhage-Strassen 算法的一个明显变体吗？这似乎是最不可能的。

我实际上已经编写了代码来实现这一点，除了有效的多项式乘法（我还不太了解数论变换）。随机测试似乎可以确认算法是正确的，因此问题很可能在时间复杂度分析中。

4

1 回答 1

3

问题是SquarePolynomialUsingFFT如果 n 是 word-RAM 或 bit-RAM 模型下的位数，则该步骤实际上不能在 O(n log(n)) 时间内完成。在 word-RAM 模型中（即对 log(n) 位字的常见操作具有单位成本），您刚刚将您的 n 个字变成了 n log(n) 个字，然后您进行了一个需要 O(n log) 的 FFT 2 (n)) 时间。在 bit-RAM 模型中（位操作有单位成本），FFT 中的每个操作都需要 O(log n) 时间，因此整个 FFT 需要 O(n log 2 (n)) 时间。

Schoenhage-Strassen 的神奇之处在于巧妙地递归选择环，在该环上进行 FFT，这样您就不会得到进一步的 log(n) 爆炸，而只会得到 log(log(n)) 的爆炸。如果你有 k 个 m 字环元素（因此 k*m = n），你只需要 O(m*k log(k)) 时间在那个环中做 m 个 FFT。如果你这样做，你必须计算 k^2 相关的 m-word 卷积，但这很酷；我们可以批量 FFT（使用较小的环）所有 k 个 m 字环元素，进行乘法，然后逆 FFT 返回。

于 2013-01-19T05:22:50.863 回答