Other/ancient methods of multiplication?

May 10, 2005 7:55 AM

MathFilter: I'm looking for integer multiplication algorithms.

The only ones I can find are Fast Fourier Transform, Karatsuba and the Russian Peasant's algorithm and of course, the "usual" one. I've googled and looked through Mathworld, to no avail. I'm looking for ancient/obscure methods or even names of books that would contain discussion of ancient/obscure algorithms. Thanks!

posted by null terminated to Technology (4 answers total)

Best answer: I don't know if it has a name, but x * y = e^{ln(x) + ln(y)}.
And then there's the barrel shifter version in binary, which is equivalent to the traditional, but in base 2.
posted by plinth at 8:02 AM on May 10, 2005

http://en.wikibooks.org/wiki/Computer_Science:Algorithms:Chapter_3#Integer_Multiplication
posted by PenDevil at 8:15 AM on May 10, 2005

If you tell us why, it would help get you a better answer.
posted by grouse at 8:30 AM on May 10, 2005

Best answer: Not sure if this is what you mean, but Jakow Trachtenberg developed a whole bunch of handy algorithms for doing multiplication (and other arithmetic - scroll down) very quickly by adding and halving the digits of the multiplicand. Pretty amazing, especially given that he did so while in a Nazi concentration camp.

For example, to multiply an integer by 11, add each digit of the multiplicand to its neighbour from right to left, writing down the results from right to left. So, to multiply 4,867,453 * 11:

Write down 3
5+3, write down 8
4+5, write down 9
7+4, write down 1, carry a dot
6+7+a dot, write down 4, carry a dot
8+6+a dot, write down 5, carry a dot
4+8+a dot, write down 3, carry a dot,
4+a dot, write down 5

giving you 53,541,983. It looks cumbersome when you write it out like that, but once you get used to it it's more like "3, 8, 9, 1 carry, 4 carry, 5 carry, 3 carry, 5, done." Great for impressing kids ;).
posted by obiwanwasabi at 4:30 PM on May 10, 2005