While we're on the subject of computer arithmetic, fast lookahead carry is also a good example of divide-and-conquer, but with a slight twist: We add the top half and bottom half independently (and recurse), but we do the top half twice -- once with no carry in, and once with a carry in, and then choose which one to use after the result of the bottom half is done. This gets the depth (and therefore the delay) of the circuit from n to log_2 n. Victor On Tue, Jul 12, 2016 at 1:53 PM, Joerg Arndt <arndt@jjj.de> wrote:

* Cris Moore <moore@santafe.edu> [Jul 12. 2016 19:41]:

...

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.

I do use Karatsuba's multiplication method as an example of divide and conquer myself. What bugs me is the statement that every single divide and conquer algorithm should be looked at as coming from Karatsuba's method (I am sure Karatsuba himself would laugh at the idea) ...and the fact that it is apparently enough just to be persistent and one can spread lies even in Wikipedia.

On the bright side, the Smarandache name and nonsense seems to have disappeared from the English Wikipedia.

Thanks for the answers and best regards, jj

...

Another good example of divide and conquer is mergesort (or quicksort).

...

Sorting is kind of boring,

Don't let Knuth hear this!

...

but in this case we can show that mergesort is almost optimal, in the sense that we need log n! ~ n log n comparisons to sort n things.

We often mention the FFT as well, but sadly a lot of CS undergrads don’t understand Fourier analysis well enough to really appreciate it...

I dare say that the FFT is not quite the most simple example for divide and conquer. But a beautiful (class of) algorithm(s) it is!

...

Cris

...

On Jul 12, 2016, at 8:08 AM, Joerg Arndt <arndt@jjj.de> wrote:

More (and worse) Wiki-weirdness:

The equivalent of https://en.wikipedia.org/wiki/Karatsuba_algorithm in German is https://de.wikipedia.org/wiki/Karazuba-Algorithmus

which states that "Die Methode von Karazuba wurde zum Vorbild für das Teile-und-herrsche-Prinzip in der Informatik."

which (roughly) translates as "Karatsuba's [multiplication] method became the prototype for the divide and conquer principle in computer science."

...and that is _exactly_ what his daughter wants the world to believe.

Can anybody refute that statement?

Thanks and best regards, jj

_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun

_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun

_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun

"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.

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.