7 ms·

Ethiopian Binary Math

192 points by midgetjones 13y ago

vilhelm_s 13y ago
This algorithm is also known as Ancient Egyptian multiplication, Egyptian multiplication, Ethiopian multiplication, Russian multiplication, or peasant multiplication. https://en.wikipedia.org/wiki/Ancient_Egyptian_multiplication https://en.wikipedia.org/wiki/Ancient_Egyptian_multiplicatio...
- drnooo 13y ago
  This has made it to HN at least a few times. Maybe it should be part of math curriculum in schools so we wouldn't keep having this conversation.
  - halflings 13y ago
    One of my professors (I'm a French comp. sci student) taught us this as an intro on how we could build an Arithmetic Logic Unit (as part of a hardware architecture course).
  - troydj 13y ago
    There is also a reference to this method on page 61 of SICP (footnote 40 of exercise 1.18). http://mitpress.mit.edu/sicp/full-text/book/book-Z-H-11.html#footnote_Temp_68 http://mitpress.mit.edu/sicp/full-text/book/book-Z-H-11.html...
- JPKab 13y ago
  Thanks. The OP article is awful. Have the decency to put in a graphic if you are going to describe a math algorithm involving stones in holes.
  - deleted 13y ago
    [deleted]
  - gucc1 13y ago
    Oh. the OP ''article'' is AWFUL? have the DECENCY? First of all it isn't an article it's a transcription. If you can't picture simple math operations with stones and holes then something might be wrong with you.
    - piqufoh 13y ago
      It's not apparent from OP's web-page that the content is taken from a series of radio monologues, and it's true that sometimes adding a small infographic can help perception and understanding many fold. Maybe try to keep personal invective out of the discussion, it's not nice.
      - gucc1 13y ago
        yea sorry. the way he addressed to OP seemed a bit too harsh to me. did he expect OP to modify the University of Houston webpage to add a graphic? Come on. Also ''No. 504''. Sounds like a series of something? by John H. Lienhard Click here for audio of Episode 504. That definitely gives away the fact that it's a radio program.
MarcusBrutus 13y ago
I fail to see the ingenuity, or even any common sense in this. If to "run" the algorithm you are required to have as many stones as the end result (actually quite more if you count those spent on "evil" holes), you might as well spread out on the ground 34 groups of stones with 7 stones in each group and just count them. Or create a 34X7 rectangle and count the stones. So I dare say we differ a lot from the Ethiopian shaman. Reality doesn't always conform to the PC narrative of how all civilizations are equal. Unless you are a sociology major that is.
- alanctgardner2 13y ago
  Correction: to run the algorithm you're required to have at least as many stones as the end result. That's like saying because MAX_INT is set, math on computers is pointless. Any physical process will have a finite upper bound on the size of the result. I agree that this isn't a remarkably efficient algorithm, but it is novel (it's completely unintuitive to the average reader), and it has a sound basis in mathematics. For the people who employed it, it was an efficient algorithm, or else they wouldn't have continued to use it. Nobody is proposing you're not as smart because you don't do math this way (although frankly, I doubt if you would have derived this by yourself, under the same conditions). On a side note, I strongly recommend 'Guns, Germs and Steel'. I've been knocked for mentioning it before because it's a pop-sci book, but it explains why cultures 'progressed' at different rates because of largely environmental factors. This might help you overcome your ridiculously defensive bias against African cultures.
  - deleted 13y ago
    [deleted]
  - MarcusBrutus 13y ago
    It couldn't have been efficient since it is patently idiotic. Just spread 34 groups of 7 stones each on the ground and count them! That's all you have to do. No algorithm at all, just symbolic logic, and you need fewer stones, and probably takes less time as well. The only way to use this algorithm to portray the mathematical prowess of native Ethiopian culture in some positive way is to argue that the Shamans purposefully used this algorithm to obfuscate the process and maintain the life style and privileges of the priestly class. I dare you to claim with a straight face that this "algorithm" is even remotely comparable to what the Greeks did, e.g. Archimedes' proving, PROVING I repeat, in a mathematically rigorous way, in the 3rd century BC, that a sphere has 2/3 the volume and surface area of its circumscribing cylinder.
mcphilip 13y ago
For a much clearer visual explanation, see this BBC video on the subject: http://youtu.be/Nc4yrFXw20Q http://youtu.be/Nc4yrFXw20Q
cpleppert 13y ago
How to multiply isn't necessarily self evident, especially if you don't have a positional notation system. Even after the introduction of arabic numerals into Europe there were many different algorithms for performing multiplication, some of which are only moderately recognizable as our long multiplication system: http://www.pballew.net/old_mult.htm http://www.pballew.net/old_mult.htm This method in practice would have used objects that represent larger numbers(1,5,10) and with those a practitioner only needs to know how to add, subtract and multiply or divide by 2. All of which are operations which can be performed quickly. It certainly isn't true that you would need as many stones as the final result.
- yaakov34 13y ago
  If you used objects to represent 5, 10, 100 stones, etc., and were capable of e.g. saying that 7 and 7 stones equal one 10-stone and 4 stones, you would have a compact representation of your number, and that would be the proper use of this algorithm. But note that this is different from what John H. Lienhard explicitly says: "the hole contains 224 stones". His version is completely pointless. None of us are objecting to the algorithm itself - yes, it is equivalent to long multiplication in binary, it has been known since ancient times, and there is nothing wrong with it. However, Lienhart has a) apparently misunderstood the point of the algorithm, and b) ascribed it to Ethiopian village "shamans", which gives one the mental image of Ethiopians standing around and watching a shaman manipulate hundreds of stones, instead of simply counting out the price - 7 for the first goat, 7 for the second, etc. This probably never happened, and would be stupid if it did; and yet people are coming here to defend this as an example of "Ethiopian ingenuity". What kind of "shamans" is Ethiopia supposed to have, anyway? Aren't they a Siberian thing? Ethiopia has one of the most ancient Christian traditions in the world, you know. I agree with some other posters that this whole thing is some kind of a politically correct cringe which somehow tries to compliment Ethiopians for something they have nothing to do with, and only ends up insulting them. And every reader's intelligence, to boot.
  - phaemon 13y ago
    > What kind of "shamans" is Ethiopia supposed to have, anyway? Aren't they a Siberian thing? Erm, no. Ethiopia has the kind of shamanic spiritual healers/wise men that are quite common within the various cultures that exist in that country.
alphakappa 13y ago
It's probably appropriate to also mention the (supposedly ancient) form of mathematics taught in India as Vedic Mathematics [1] that provides computational shortcuts. (The origin of this is in question though [2]) 1. http://ed.ted.com/lessons/the-magic-of-vedic-math-gaurav-tekriwal http://ed.ted.com/lessons/the-magic-of-vedic-math-gaurav-tek... 2. http://www.openthemagazine.com/article/art-culture/the-fraud-of-vedic-maths http://www.openthemagazine.com/article/art-culture/the-fraud...
pbiggar 13y ago
Looking at https://en.wikipedia.org/wiki/Multiplication_algorithm#Peasant_or_binary_multiplication https://en.wikipedia.org/wiki/Multiplication_algorithm#Peasa..., isn't this exactly the same as decimal long multiplication, except using binary?
- bcoates 13y ago
  The long multiplication algorithm has two nested inner loops, each reducing one of the inputs to digits (dividing and multiplying by fixed values), multiplying them with a lookup table, then performing add-with-carry against inner and outer accumulators. The Russian Peasant Algorithm optimizes this for the binary case by noticing that the inner multiply is always by 0 or 1 so it's trivial and never carries, removing the inner loop entirely and allowing you to use only one accumulator.
eadlam 13y ago
So how do we and that Ethiopian shaman differ? Paper! Seriously, this was 1960? Even ancient Sumerians were using paper to do math. I don't understand why in 1960 anyone would seriously still be doing math with holes and rocks.
jatin085 13y ago
Wouldn't it be more quick by filling the hole with 7 stones for 34 times? They could use 34 extra stones (or goats) to keep the count. That could be done by any farmer.

192 points by midgetjones 13y ago

This algorithm is also known as Ancient Egyptian multiplication, Egyptian multiplication, Ethiopian multiplication, Russian multiplication, or peasant multiplication. https://en.wikipedia.org/wiki/Ancient_Egyptian_multiplication https://en.wikipedia.org/wiki/Ancient_Egyptian_multiplicatio...

drnooo 13y ago
This has made it to HN at least a few times. Maybe it should be part of math curriculum in schools so we wouldn't keep having this conversation.
- halflings 13y ago
  One of my professors (I'm a French comp. sci student) taught us this as an intro on how we could build an Arithmetic Logic Unit (as part of a hardware architecture course).
- troydj 13y ago
  There is also a reference to this method on page 61 of SICP (footnote 40 of exercise 1.18). http://mitpress.mit.edu/sicp/full-text/book/book-Z-H-11.html#footnote_Temp_68 http://mitpress.mit.edu/sicp/full-text/book/book-Z-H-11.html...
JPKab 13y ago
Thanks. The OP article is awful. Have the decency to put in a graphic if you are going to describe a math algorithm involving stones in holes.
- deleted 13y ago
  [deleted]
- gucc1 13y ago
  Oh. the OP ''article'' is AWFUL? have the DECENCY? First of all it isn't an article it's a transcription. If you can't picture simple math operations with stones and holes then something might be wrong with you.
  - piqufoh 13y ago
    It's not apparent from OP's web-page that the content is taken from a series of radio monologues, and it's true that sometimes adding a small infographic can help perception and understanding many fold. Maybe try to keep personal invective out of the discussion, it's not nice.
    - gucc1 13y ago
      yea sorry. the way he addressed to OP seemed a bit too harsh to me. did he expect OP to modify the University of Houston webpage to add a graphic? Come on. Also ''No. 504''. Sounds like a series of something? by John H. Lienhard Click here for audio of Episode 504. That definitely gives away the fact that it's a radio program.

MarcusBrutus 13y ago

I fail to see the ingenuity, or even any common sense in this. If to "run" the algorithm you are required to have as many stones as the end result (actually quite more if you count those spent on "evil" holes), you might as well spread out on the ground 34 groups of stones with 7 stones in each group and just count them. Or create a 34X7 rectangle and count the stones. So I dare say we differ a lot from the Ethiopian shaman. Reality doesn't always conform to the PC narrative of how all civilizations are equal. Unless you are a sociology major that is.

alanctgardner2 13y ago
Correction: to run the algorithm you're required to have at least as many stones as the end result. That's like saying because MAX_INT is set, math on computers is pointless. Any physical process will have a finite upper bound on the size of the result. I agree that this isn't a remarkably efficient algorithm, but it is novel (it's completely unintuitive to the average reader), and it has a sound basis in mathematics. For the people who employed it, it was an efficient algorithm, or else they wouldn't have continued to use it. Nobody is proposing you're not as smart because you don't do math this way (although frankly, I doubt if you would have derived this by yourself, under the same conditions). On a side note, I strongly recommend 'Guns, Germs and Steel'. I've been knocked for mentioning it before because it's a pop-sci book, but it explains why cultures 'progressed' at different rates because of largely environmental factors. This might help you overcome your ridiculously defensive bias against African cultures.
- deleted 13y ago
  [deleted]
- MarcusBrutus 13y ago
  It couldn't have been efficient since it is patently idiotic. Just spread 34 groups of 7 stones each on the ground and count them! That's all you have to do. No algorithm at all, just symbolic logic, and you need fewer stones, and probably takes less time as well. The only way to use this algorithm to portray the mathematical prowess of native Ethiopian culture in some positive way is to argue that the Shamans purposefully used this algorithm to obfuscate the process and maintain the life style and privileges of the priestly class. I dare you to claim with a straight face that this "algorithm" is even remotely comparable to what the Greeks did, e.g. Archimedes' proving, PROVING I repeat, in a mathematically rigorous way, in the 3rd century BC, that a sphere has 2/3 the volume and surface area of its circumscribing cylinder.

mcphilip 13y ago

For a much clearer visual explanation, see this BBC video on the subject: http://youtu.be/Nc4yrFXw20Q http://youtu.be/Nc4yrFXw20Q

cpleppert 13y ago

How to multiply isn't necessarily self evident, especially if you don't have a positional notation system. Even after the introduction of arabic numerals into Europe there were many different algorithms for performing multiplication, some of which are only moderately recognizable as our long multiplication system: http://www.pballew.net/old_mult.htm http://www.pballew.net/old_mult.htm This method in practice would have used objects that represent larger numbers(1,5,10) and with those a practitioner only needs to know how to add, subtract and multiply or divide by 2. All of which are operations which can be performed quickly. It certainly isn't true that you would need as many stones as the final result.

yaakov34 13y ago
If you used objects to represent 5, 10, 100 stones, etc., and were capable of e.g. saying that 7 and 7 stones equal one 10-stone and 4 stones, you would have a compact representation of your number, and that would be the proper use of this algorithm. But note that this is different from what John H. Lienhard explicitly says: "the hole contains 224 stones". His version is completely pointless. None of us are objecting to the algorithm itself - yes, it is equivalent to long multiplication in binary, it has been known since ancient times, and there is nothing wrong with it. However, Lienhart has a) apparently misunderstood the point of the algorithm, and b) ascribed it to Ethiopian village "shamans", which gives one the mental image of Ethiopians standing around and watching a shaman manipulate hundreds of stones, instead of simply counting out the price - 7 for the first goat, 7 for the second, etc. This probably never happened, and would be stupid if it did; and yet people are coming here to defend this as an example of "Ethiopian ingenuity". What kind of "shamans" is Ethiopia supposed to have, anyway? Aren't they a Siberian thing? Ethiopia has one of the most ancient Christian traditions in the world, you know. I agree with some other posters that this whole thing is some kind of a politically correct cringe which somehow tries to compliment Ethiopians for something they have nothing to do with, and only ends up insulting them. And every reader's intelligence, to boot.
- phaemon 13y ago
  > What kind of "shamans" is Ethiopia supposed to have, anyway? Aren't they a Siberian thing? Erm, no. Ethiopia has the kind of shamanic spiritual healers/wise men that are quite common within the various cultures that exist in that country.

alphakappa 13y ago

It's probably appropriate to also mention the (supposedly ancient) form of mathematics taught in India as Vedic Mathematics [1] that provides computational shortcuts. (The origin of this is in question though [2]) 1. http://ed.ted.com/lessons/the-magic-of-vedic-math-gaurav-tekriwal http://ed.ted.com/lessons/the-magic-of-vedic-math-gaurav-tek... 2. http://www.openthemagazine.com/article/art-culture/the-fraud-of-vedic-maths http://www.openthemagazine.com/article/art-culture/the-fraud...

pbiggar 13y ago

Looking at https://en.wikipedia.org/wiki/Multiplication_algorithm#Peasant_or_binary_multiplication https://en.wikipedia.org/wiki/Multiplication_algorithm#Peasa..., isn't this exactly the same as decimal long multiplication, except using binary?

bcoates 13y ago
The long multiplication algorithm has two nested inner loops, each reducing one of the inputs to digits (dividing and multiplying by fixed values), multiplying them with a lookup table, then performing add-with-carry against inner and outer accumulators. The Russian Peasant Algorithm optimizes this for the binary case by noticing that the inner multiply is always by 0 or 1 so it's trivial and never carries, removing the inner loop entirely and allowing you to use only one accumulator.

eadlam 13y ago

So how do we and that Ethiopian shaman differ? Paper! Seriously, this was 1960? Even ancient Sumerians were using paper to do math. I don't understand why in 1960 anyone would seriously still be doing math with holes and rocks.

jatin085 13y ago

Wouldn't it be more quick by filling the hole with 7 stones for 34 times? They could use 34 extra stones (or goats) to keep the count. That could be done by any farmer.