Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

A recent puzzle blog post about finding three evenly spaced ones lead me to a stackoverflow question with a top answer that claims to do it in O(n lg n) time. The interesting part is that the solution involves squaring a polynomial, referencing a paper that describes how to do it in O(n lg n) time.

Now, multiplying polynomials is practically the same as multiplying numbers. The only real difference is the lack of carries. But... the carries can also be done in O(n lg n) time. For example:

    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

So my question is this: where's the mistake, here? Multiplying numbers in O(n lg n) is a gigantic open problem in computer science, and I really really doubt the answer would be this simple.

  • Is the carrying wrong, or not O(n lg n)? I've worked out that lg n + 1 bits per value is enough to track the carries, and the algorithm is so simple I'd be surprised if it was wrong. Note that, although an individual increment can take O(lg n) time, the aggregate cost for x increments is O(x).
  • Is the polynomial multiplication algorithm from the paper wrong, or have conditions that I'm violating? The paper uses a fast fourier transform instead of a number theoretic transform, which could be an issue.
  • Have a lot of smart people missed an obvious variant of the Schönhage–Strassen algorithm for 40 years? This seems by far the least likely.

I've actually written code to implement this, except for the efficient polynomial multiplication (I don't understand the number theoretic transform well enough yet). Random testing appears to confirm the algorithm being correct, so the issue is likely in the time complexity analysis.

share|improve this question
    
Shouldn't the square include x^10 + 2x^8 ? x^10 only once (x^5 * x^5), and x^8 twice (x^6 * x^2 + x^2 * x^6) –  Sjoerd Jan 19 '13 at 17:00
    
I did the example by hand. I made an arithmetic mistake. Sorry. I did actually implement the algorithm and test it and get correct results, though. –  Strilanc Jan 19 '13 at 19:34
add comment

1 Answer

up vote 11 down vote accepted

Your algorithm is very similar to Schönhage–Strassen. In the FFT step, there are large numbers involved - as you mention, their size can be up to $O(\log n)$. Arithmetic on them doesn't come for free. You need to apply the construction recursively, and you'll lose something.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.