The Stack Overflow podcast is back! Listen to an interview with our new CEO.
4 of 6 added 1764 characters in body

Where does the lg(lg(N)) factor come from in Schönhage–Strassen's run time?

According to page 53 of Modern Computer Arithmetic (pdf), all of the steps in the Schönhage–Strassen Algorithm cost $O(N \cdot lg(N))$ except for the recursion step which ends up costing $O(N\cdot lg(N) \cdot lg(lg(N)))$.

I don't understand why the same inductive argument used to show the cost of the recursive step doesn't work for $O(N\cdot lg(N))$.

  • Assume that, for all $X < N$, the time $F(X)$ is less than $c \cdot X \cdot lg(X)$ for some $c$.
  • So the recursive step costs $d \cdot \sqrt{N} F(\sqrt{N})$, and we know this is less than $d \cdot \sqrt{N} c \cdot \sqrt{N} lg(\sqrt{N}) = \frac{c \cdot d}{2} \cdot N \cdot lg(N)$ by the inductive hypothesis.
  • If we can show that $d < 2$, then we're done because we've satisfied the inductive step.
  • I'm pretty sure recursion overhead is negligible, so $d \approx 1$ and we have $\frac{c}{2} N \cdot lg(N)$ left to do the rest. Easy: everything else is $O(N \cdot lg(N))$ so we can pick a $c$ big enough for it to fit in our remaining time.

Basically, without digging into the details that will contradict this somehow, it looks like things would work out if we assumed the algorithm costs $O(N \cdot log(N))$. The same thing seems to happen if I expand the recursive invocations then sum it all up... so where is the penalty coming from?

My best guess is that it has to do with the $lg(lg(N))$ levels of recursion, since that's how many times you must apply a square root to get to a constant size. But how do we know each recursive pass is not getting cheaper, like in quickselect?

For example, if we group our $N$ initial items into words of size $O(lg(N))$, meaning we have $O(N/lg(N))$ items of size $O(lg(N))$ to multiply when recursing, shouldn't that only take $O(N/lg(N) \cdot lg(N) \cdot lg(lg(N)) \cdot lg(lg(lg(N)))) = O(N \cdot lg(lg(N)) \cdot lg(lg(lg(N))))$ time to do. Not only is that well within the $N \cdot lg(N)$ limit, it worked even though I used the larger $N\cdot lg(N)\cdot lg(lg(N))$ cost for the recursive steps (for "I probably made a mistake" values of "worked").

My second guess is that there's some blowup at each level that I'm not accounting for. There are constraints on the sizes of things that might work together to slow down how quickly things get smaller, or to multiply how many multiplications have to be done.

Here's the recursive expansion.

Assume we get $N$ bits and split them into $\sqrt{N}$ groups of size $\sqrt{N}$. Everything except the recursion costs $O(N lg N)$. The recursive multiplications can be done with $3 \cdot \sqrt{N}$ bits. So we get the relationship:

$M(N) = N \cdot lg(N) + \sqrt{N} \cdot M(3 \cdot \sqrt{N})$

Expanding once:

$M(N) = N \cdot lg(N) + \sqrt{N} \cdot (3 \cdot \sqrt{N} \cdot lg(3 \cdot \sqrt{N}) + \sqrt{3 \cdot \sqrt{N}} \cdot M(3 \cdot \sqrt{3 \cdot \sqrt{N}})$


$M(N) = N \cdot lg(N) + 3 \cdot N \cdot lg(3 \cdot \sqrt{N}) + \cdot \sqrt{3} \cdot N^{2-\frac{1}{2}} \cdot M(3^{2-\frac{1}{2}} \cdot \sqrt{\sqrt{N}})$

See the pattern? Each term will end up in the form $3^{2-2^{-i}} \cdot N \cdot lg(N^{2^{-i}} 3^{2-2^{-i}})$. So the overall sum is:

$\sum_{i=0}^{lg(lg(N))} 3^{2-2^{-i}} \cdot N \cdot lg(N^{2^{-i}} 3^{2-2^{-i}})$

We can upper bound this by increasing the powers of 3 to just 3^2, since that can only increase the value in both cases:

$\sum_{i=0}^{lg(lg(N))} 9 \cdot N \cdot lg(N^{2^{-i}} 9)$

Which is asymptotically the same as:

$\sum_{i=0}^{lg(lg(N))} N \cdot lg(N^{2^{-i}})$

Moving the power out of the logarithm:

$\sum_{i=0}^{lg(lg(N))} N \cdot lg(N) \cdot 2^{-i}$

Moving variables not dependent on $i$ out:

$N \cdot lg(N) \sum_{i=0}^{lg(lg(N))} 2^{-i}$

The series is upper bounded by 2, so we're upper bounded by:

$N \cdot lg(N)$

Not sure where the $lg(lg(N))$ went. All the twiddly factors and offsets (because many recurrence relations "solutions" are broken by those) I throw in seem to get killed off by the $lg$ creating that exponentially decreasing term, or they end up not multiplied by $N$ and are asymptotically insignificant.