vendredi 11 septembre 2009

Dase's algorithm

I just saw a TED talk about Mathemagics by Arthur Benjamin, and googled a few related things. With the notable exception of Alexander Aitken, it seems that very few calculator prodigies are able to explain how they actually calculate so quickly. The fuzziness of the explanations suggests some less-rational procedure that seems closer to intuition than to any algorithm.

One such calculator prodigy was Zacharias Dase (1824-2861). He is shortly mentioned in Hofstadter’s book, Gödel-Escher-Bach. His calculation skills were such that Gauss himself was impressed and he had him hired by the Hamburg Academy of Sciences to compile some mathematical tables. Dase had other amazing abilities, like counting sheep in a flock in a single glance.

In the MacTutor History of Mathematics archive, you can read the following sentence about Dase: "He multiplied two 20 digit numbers in 6 minutes; two 40 digit numbers in 40 minutes; two 100 digit numbers in 8 hours 45 minutes."

When you put these figures on a logarithmic plot it seems that Dase’s unknown algorithm was slightly slower than quadratic (solid line). It is likely that he was using the same algorithm as anyone of us: multiplying each digit of the first number by the second number, and taking the sum. He was very good at it, and he obviously had some tricks, but that was probably all of it.

Had Zacharias Dase lived lived today, he might have tried to use the FFT-like algorithm by Schönhage and Strassen (dotted line), which is faster for multiplying large numbers.

http://www.ted.com/talks/lang/eng/arthur_benjamin_does_mathemagic.html.