Hacker News Reader

Comment by ccleve | Hacker News Reader

Once the longer number starts repeating digits, then it's not n^2 anymore. Multiplies get replaced with lookups. And we're only counting the multiplies. That's all they counted in the article. Not the adds, not the shifts.

View on HN

They don't count the additions or shifts because they're both linear time operations, and thus provably at least as fast as multiplication (both in an asymptotic and exact sense). In any case where multiplication is super-linear, this means that addition and shifting are are not the temporal bottleneck at any stage in the algorithm where you have a constant number of those operations surrounding at least one multiplicative recursive call (on numbers of similar magnitudes).

If additions were truly free, an even easier optimal algorithm would just be repeated addition involving zero multiplications.

The complexity of Karatsuba's algorithm, because it's a recursive one that gets "wider" at every level, is dominated by the width of that recursion. The top level always has a small number of operations, so we don't explicitly count them there, but the bottom has the truly huge number of operations that contribute to the algorithm's complexity, because each level of recursion dramatically increases the number of operations. Some number of those operations (most of them, in fact) will be single-digit additions.

Memoizing number-by-digit multiplication doesn't make multiplication O(1) because one must still do an N-digit addition (which is O(N)) for each digit.

The slowest multiplications are always when the two numbers are about the same size... That is to say, the case you're talking about doesn't happen.

Reply on news.ycombinator.com