"a problem is easier than we thought it was" Statements of this sort have always irritated me, because they indicate the lack of diversity of thought and conception. Such lack of diversity exists because much of our educational system is designed to drive out diversity of thought. *Trees* have always been "divide-and-conquer" in both their root systems to exploit access to water and their branch-and-leaf system to exploit access to sunlight. It isn't my fault that Fortran I and Cobol didn't allow recursion, so I'm not about to buy into these languages' silly, constrained view of the world. The lambda calculus (based on trees and recursion) was quite well developed in the 1920's and 1930's, so Turing's one-dimensional tapes and exclusive reliance on iteration was a major step backwards. The Roman army was always a fractal: each (approximate) power of ten provided the next unit of command. And I suspect that (like everything else the Romans did) they stole this idea from someone else (Greeks? Babylonians? Egyptians?). At 07:54 AM 7/12/2016, Cris Moore wrote:
To be fair, Karatsuba's algorithm is one of the most common examples we use when teaching divide and conquer in undergraduate CS classes.
More broadly, it's a nice example of where a problem is easier than we thought it was, since one's first intuition is that the grade school method is optimal.