6 LaTeX edit edit approved Mar 12 '16 at 16:50 wythagoras 31033 silver badges1515 bronze badges 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))$$$$O(N \cdot \lg(N))$$ except for the recursion step which ends up costing $$O(N\cdot lg(N) \cdot lg(lg(N)))$$$$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))$$$$O(N\cdot \lg(N))$$. Assume that, for all $$X < N$$, the time $$F(X)$$ is less than $$c \cdot X \cdot lg(X)$$$$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)$$$$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)$$$$\frac{c}{2} N \cdot \lg(N)$$ left to do the rest. Easy: everything else is $$O(N \cdot lg(N))$$$$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))$$$$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))$$$$\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))$$$$O(\lg(N))$$, meaning we have $$O(N/lg(N))$$$$O(N/\lg(N))$$ items of size $$O(lg(N))$$$$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))))$$$$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)$$$$N \cdot \lg(N)$$ limit, it worked even though I used the larger $$N\cdot lg(N)\cdot lg(lg(N))$$$$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)$$$$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})$$$$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) + \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}})$$$$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}})$$$$\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)$$$$\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}})$$$$\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}$$$$\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}$$$$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)$$$$N \cdot \lg(N)$$ Not sure where the $$lg(lg(N))$$$$\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$$$$\lg$$ creating that exponentially decreasing term, or they end up not multiplied by $$N$$ and are asymptotically insignificant. 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. 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. Tweeted twitter.com/#!/StackCompSci/status/490604292186066944 occurred Jul 19 '14 at 21:09 5 edited tags | link edited Jul 15 '14 at 5:05 Raphael♦ 59k2525 gold badges144144 silver badges327327 bronze badges 4 added 1764 characters in body edited Jul 14 '14 at 0:52 Craig Gidney 4,6121313 silver badges4242 bronze badges 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. 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. 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. 3 added 327 characters in body edited Jul 13 '14 at 7:33 Craig Gidney 4,6121313 silver badges4242 bronze badges 2 edited body edited Jul 13 '14 at 6:40 Craig Gidney 4,6121313 silver badges4242 bronze badges 1 asked Jul 13 '14 at 6:34 Craig Gidney 4,6121313 silver badges4242 bronze badges