Ethiopian Multiplication

http://threesixty360.wordpress.com/2009/06/09/ethiopian-multiplication/

by azarias • 14 years ago

65 21 14 years ago

threesixty360.wordpress.com

lmkg• 14 years ago

I've heard this referred to as the "Peasant's algorithm," though I don't know why. Interesting fact: In binary, the peasant and traditional multiplication algorithms are actually step-for-step identical.

SeanLuke• 14 years ago

Since dividing by two (ignoring remainders) is just a left shift, and multiplying by two is just a right shift, this means you can do multiplication with just <<, >>>, and +.

Of course, here's another, er, related algorithm. Take your two numbers A and B. Make a variable called C, initially set to 0. Iteratively decrease A by 1, and increase C by B. Do this until A = 0. Then C is your answer. Everyone knows this technique, it's obvious. But it means that you can do multiplication with just + and --.

I wonder what other ways you can do multiplication with a limited set of mathematical operators.

ANTSANTS• 14 years ago

The other interesting property to the first algorithm is that you don't need to calculate a conditional for each bit in one of those factors. You can just AND each bit in one factor by all the bits in the other factor (ANDing is equivalent to multiplying in binary), before the shifts and the adds. Because ANDs, shifts, and adders are extremely simple to implement in hardware, most (all?) binary multiplication circuits are based off of the peasant multiplication algorithm, with modifications that trade off expense of manufacturing (more gates) for quicker computation (less gate delay due to exploiting parallelism in the algorithm).

marginalboy2• 14 years ago

I don't know; I feel like this would get complicated far more quickly than the FOIL method...

marginalboy2• 14 years ago

As soon as I walked away for some more water, I realized I had missed the point ;-)

nikatwork• 14 years ago

Made me think of the Trachtenberg Speed System: http://mathforum.org/dr.math/faq/faq.trachten.html

aaronbrethorst• 14 years ago

To multiply 14 and 12 in my head, I break it down like this:

    14 * 12 = (14 * 10) + (14 * 2) = 168

Anyone else do that?

barking• 14 years ago

Sometimes. Or to multiply by 25, multiply by 100 and divide by 4. I always meant to study the trachtenberg method but never got around to it

ljd• 14 years ago

Yes, I process everything in 10% as well. 15% tip on $34? 10% = $3.4 so half of 3.4 is 1.7, combine them for $5.10.

Someone• 14 years ago

Not for 14 times 12, as that is (13+1) times (13-1). 'everybody' knows 1^2 = 1 and 13^2 = 169, so 14 times 12 = 169 - 1 = 168.

jcr• 14 years ago

Similar here, but based on memorization. Since I know twelve squared ((12 * 12) = 144) by rote, the rest is easy.

  14 * 12 = (12^2) + (12*2) = 168

drharris• 14 years ago

I tend to use the tens as well, but in this case I would have used the 12*12 + 24 trick. I also use some of the others listed here, so it makes me happy to know there are people like me out there.

ajuc• 14 years ago

I do this sometimes.

Sometimes I refactor at first:

    14*12=28*6=56*3=56*2+56=112+56=168

    14*12=7*8*3=21*8=160+8

lotharbot• 14 years ago

My dad wrote a short article on this in the 1980s:

http://darrow.faithweb.com/peasantmultiply.htm

grumblepeet• 14 years ago

My son was taught this method at school as THE way to do multiplication. Imagine my confusion when he brought homework back and I started doing multiplication the way we were all taught, only to be told "DADDY, you don't know anything!".

exDM69• 14 years ago

Do you live in the UK? I read an article some time ago about a new methods of multiplication and division that was being taught at UK elementary schools. Parents had trouble with it because they were not taught that way.

While the new simple methods got the job done, I still think the old methods are worth teaching because they're required when doing some advanced math later on.

The difficult method of long division, for example. After elementary school arithmetic, I've had to re-learn the method several times. In grade school it was doing divisions of numbers but later the same method was used for division of polynomials, then doing binary and again when learning how to compute crc checksums and hassling with polynomial fields in crypto class.

Math education is not necessarily supposed to be about learning how to get shit done (if it were, it would be obsolete because of calculators), but rather learning methods to deal with numbers, polynomials and other algebraic beings.

einhverfr2• 14 years ago

This has been attributed to so many places. I actually spent some time coming up with an algebraic proof that it worked when I was in college. It turns out that it is perfectly clear what is happening if you write both numbers in binary as another poster has pointed out.

However for historical purposes, the question is why? I think there is a very simple reason. Before you have based number systems, most number systems are usually derived from tally sticks. This makes some functional sense, and once you think about it from a tally stick, roman numerals make perfect sense. For example consider the number XXIV. It represents a position on a tally stick:

IIIIVIIIIXIIIIVIIIIXIIIIVIIIIXIIIIVIIIIXIIIIVIIIIL

Count to the second X and then one before the V. IXL is the same. Count backwards one X and then one I from the L. So while our system of numbers today is based on position of digits, many earlier systems were based on visualized markings on tally sticks. So you have numbers without a base system. This divide and add approach works very well when you don't have a number system. You can take your tally stick, figure out the number, and the same on the other side. I cannot think of another way to do multiplication on a tally stick.

Interestingly tally sticks of a slightly different sort were in use up until the early 19th century in Britain as tax receipts and in 1836 the attempt of the British government to get rid of these humble staves leveled both houses of parliament. Before you have widespread numeracy, tally sticks are how you track amounts for everything from debts to receipts. It isn't surprising that this would be a widespread method.

regularfry• 14 years ago

The interesting part is that Romans wouldn't have written 24 as XXIV. They'd have written it as XXIIII, which makes it much simpler because you only ever go left to right..

einhverfr2• 14 years ago

the Romans, IIRC were extremely inconsistent. Sometimes, for example, you see IIXX for 18. However either way it represents a place on a tally stick.

rfzabick• 14 years ago

Some folks have pointed out the relationship to binary multiplication. Here's a TED talk that discusses the long history of binary math in ancient Africa. http://www.ted.com/talks/ron_eglash_on_african_fractals.html Spoiler: Boole got the idea from Africa by way of the Middle East!

Kafka• 14 years ago

In Ruby:

  # Ethiopian Multiplication
  # usage: ruby em.rb 673 7
  m, n = ARGV.map(&:to_i)
  product = 0
  while m >= 1
    puts "%4d : %4d %s" % [m, n, m.even? ? "Ignore" : ""]
    product += n unless m.even?
    m = m / 2
    n = n * 2
  end
  puts "Product: #{product}"

https://gist.github.com/3660240

Ethiopian Multiplication

Related Stories