6
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ I think the error in the recursive expansion might be the assumption that the values at each stage are whole. They have to be rounded up, and there could be accumulating loses at each level. $\endgroup$ – Craig Gidney Jul 15 '14 at 3:42
5
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Wait, I see the problem now. If you use an expansion factor of 2 it does reduce to $n lg(n)$, but if you use something even slightly higher then the $1/2$ you gain from the $log(\sqrt{n})$ is overpowered and the bound fails. And the recursion is not just $2 \sqrt{n}$, because we square AND sum. The summing might need $lg(n)$ extra bits, and that every so slightly blows the bound. $\endgroup$ – Craig Gidney Jul 15 '14 at 3:20
  • $\begingroup$ Ah, actually it fails at 2 as well because of the additional n log(n). But not for < 2 I don't think. $\endgroup$ – Craig Gidney Jul 15 '14 at 3:28
3
$\begingroup$

The issue is that the expansion factor inside the recursive term is not less than 2, and that causes the bound to fail. Define:

$T_c(n) = n \log n + \sqrt n T(c \sqrt n)$

I claim that $T_{2-\epsilon}$ is $O(n \log n)$, but $T_{2}$ isn't. This is probably most obvious when trying to prove the $n \log n$ bound by induction. Assume that $T_c(n_0) \leq 100 n_0 \log n_0$ for all $n_0 < n$. Then:

$T_c(n)$

$= n \log n + \sqrt n T(c \sqrt n)$

$\leq n \log n + \sqrt n (100 c \sqrt n \log {(c \sqrt n)})$

$= n \log n + 100 c n (\log c + \frac{\log n}{2})$

$= (50 c + 1) n \log n + 100 c n \log c$

$= (50 c + 1 + 100 c \frac{\log c}{\log n}) n \log n$

${\LARGE ⊜} (50 c + 1 + \epsilon) n \log n$

Clearly this proof is only going to work if $50c + 1 < 100$, which is only true when $c < 2 - \frac{1}{50}$. We can move that threshold closer to 2 by increasing the arbitrary constant of 100, but we can't ever get the threshold to reach 2.

The algorithm needs at least a factor of 2 blowup because otherwise we lose information about the intermediate squared values (because the field is too small). So it must increase faster than $n \log n$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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