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. Another good example of divide and conquer is mergesort (or quicksort). Sorting is kind of boring, 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... 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