Cris: My irritation isn't with you, personally, but with the way math is mostly taught. Mathematicians are some of the most clever & devious people, who have managed to tease out the most amazing facts from a simple well-ordered set. In times past, mathematicians wanted the student/reader to fully appreciate the beauty of his/her result, so the obscuring scaffolding needed to achieve that result was removed. During certain periods -- e.g., the Renaissance -- it became fashionable to destroy the scaffolding for another purpose -- to pull up the drawbridge so that no one else could cross -- e.g., solutions of the cubic & quartic; Brunelleschi's standing egg. Unfortunately, this tradition of destroying the scaffolding continues to this day. Math professors are so intent on demonstrating their (and other mathematicians') cleverness, that they forget the primary goal of their teaching: to enable the next generation to understand and eventually exceed their own capabilities. But this requires that the students understand scaffolding, and learn to develop and build their own scaffolding so that they can eventually build higher structures than their teachers. So *scaffolding* -- for the student -- is far more important than the final result. In the particular case of computational complexity, there are two important considerations: *total work* (i.e., the amount of work for a single processor), and *depth* (i.e., the amount of time given infinite parallelism). (Actually, there is a third consideration: non-deterministic v. deterministic, but we currently assume that that consideration doesn't enter into the case of a single multiplication task.) Sometimes the shortest distance isn't a straight line. For example, achieving minimum depth for parallelism may provide insights which can reduce total work. Thus, one approach to parallelizing multiplication may eventually lead to Karatsuba multiplication. The idea of allocating work for parallelism isn't new: the ancient Egyptians understood this very, very well. Indeed, every successful human civilization for the past several hundred thousand years has understood parallelism. Given the prodigious amount of astronomic computation performed by the ancient Babylonians, it wouldn't surprise me in the least to find that they may have developed certain shortcuts analogous to Karatsuba. As another example, the horsemen on the steppes of Russia would encircle an area whose radius may have been as large as 50 miles, and proceed to tighten that circle in order to capture any beasts so enclosed. If this process reminds one of a famous theorem in mathematics, then that theorem wouldn't surprise these horsemen so much as it might a modern-day student whose idea of hunting for food is limited to installing a pizza app on his/her iphone. So what is "surprising" is highly dependent upon one's breadth of experience. At 12:34 AM 7/13/2016, Cris Moore wrote:
um... ok, but all I mean is thaat when one first looks at the problem of multiplying two n-digit numbers, it seems as if you have to compute all n^2 cross-terms.
so to me the fact you can do better is a surprise.
the best algorithm isn't really treelike: it uses the fact that we can think of multiplying two long integers as convolving two functions (if we ignore carrying) and we can do that in the Fourier basis.