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

Problem Detail: 

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}})$

Simplifying:

$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.

Asked By : Craig Gidney

Answered By : Yuval Filmus

The sticking point is the size of the integers in the recursive step, which is not quite $\sqrt{n}$, but rather twice as large, since the product of two $t$-bit integers has size $2t$. Assuming that we break the original $n$-bit integer into $\sqrt{n}$ parts of length $\sqrt{n}$, the running time recursion is $$ T(n) = n\log n + \sqrt{n}T(2\sqrt{n}), $$ and by expanding it, we get $$ \begin{align*} T(n) &= n\log n + \sqrt{n}T(2\sqrt{n}) \\ &= n\log n + 2n\log (2\sqrt{n}) + 2^{1/2} n^{3/4} T(2^{3/2}n^{1/4}) \\ &= n\log n + 2n\log (2\sqrt{n}) + 4n\log (2^{3/2} n^{1/4}) + 2^{5/4} n^{7/8} T(2^{7/4} n^{1/8}) \\ &= n\log n + 2n\log (2\sqrt{n}) + 4n\log (2^{3/2} n^{1/4}) + 2^3 n \log (2^{7/4} n^{1/8}) + \cdots, \end{align*} $$ so each level of the recursion takes time proportional to $n\log n$. Since there are $\log\log n$ levels, we get the quoted running time. For more information, check out these lecture notes.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/28379