On Jul 12, 2016, at 6:07 PM, Henry Baker <hbaker1@pipeline.com> wrote:
"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.
um… ok, but all I mean is that 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. Cris