This algorithm is also known as Ancient Egyptian multiplication, Egyptian multiplication, Ethiopian multiplication, Russian multiplication, or peasant multiplication.
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).
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.
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.
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.
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.
I don't see a particular reason why one should mention "PC narrative of all civilizations being equal" in this context. This article is merely an example of how stone-age "technology" can perform a certain task.
I also take issue with the automatism of accusing "political correctness". Nobody says civilizations are equal, there are numerous obvious differences. Somehow whenever I dig deeper and ask about what those people think, I get to hear/read profound racist undertones. The "PC" curse is really most common as a defense to accusations of racism.
The actual problem arises when people go on to make value-judgements along ethnical boundaries (racism). And then they go even further, using these not necessarily well founded judgements to pose "scientific facts" about how one ethnicity is genetically superior (because they believe all differences between two sets of humans have to come down to genetics/evolution)and thus are somehow entitled to more wealth than another ethnicity.
Their is no right to wealth and no birth right to it. That does not however imply a redistribution of wealth in the slightest way.
There are strong factors which contributed to the economic rise of Europe "first" and which have nothing to do with human genetics. Agriculture benefits from certain climates and soil conditions (ask the mayans about their collapse...). It also benefits a lot from domesticateable animals, and most animals are not nearly as well suited as for example horses and cows. Then the coastlines and rivers in Europe have shown to be much more conducive to commerce (before industrialization) than in Africa or America.
Systems are complex. Don't simplify them to justify judgements.
I wouldn't normally want to comment on that since it's not relevant to the original thread but what exactly do you mean "no birth right to it"? Like, I can't bequeath anything to my kids cause that would confer an "unfair" advantage on them? Or maybe we need a "fair" inheritance tax. Like 95% maybe? Somehow it is your political / worldview bias that's transparent in your post, not mine.
I said nothing about genetic overall superiority although it is plainly evident to anyone not blinded by PC that some peoples are genetically more likely to produce sublime music or advanced mathematical frameworks / complex works of art or advanced technology just like other peoples are genetically more likely to be stronger, better jumpers, runners, sturdier and so on. Environment certainly played a role but after many hundreds or even thousands of generations the genetic makeup of a people changes as well (as an aggregate statistical entity).
I've no doubt these genetic differences were non-existent when we were all together in the primordial soup but we've moved past that phase and these differences now exist. I am saying nothing about overall superiority and certainly nothing about rights of individuals.
If you make the extraordinary claim that the genetic makeup of a people played no role in the difference of achievements between cultures the onus is on you to prove a negative. Explain why we take it for granted that people of Samoan heritage are huge but it's somehow racist to argue that hey, that DNA thing may be affecting brain cells as well and not just bones / muscle tissue.
Quite simply, the variation within a population is far greater than the variation between populations.
Individuals have genes that make them sublime musicians or athletes or mathematicians or painters. Cultures have different patterns which set the tone of that music and sports and math and art.
Since you're hedging with "peoples are genetically different" instead of "people are genetically different" I wonder if you've had some kind of formal rhetorical training.
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.
Okay, first and foremost, the algorithm obviously was never actually used in the way this story describes, because it is totally ridiculous and that is not even the point of the article.
But let's say it was. In saying that the shaman knows how to put two sets of 7 stones in a particular pile, it is implying that the shaman also knows how to put 34 sets of 7 stones in a particular pile. He also knows how to count them, so the problem is already solved. What he is doing is a bit more "rube goldberg" than novel. It may have parallels with some real algorithm for multiplication, but it is certainly not a very direct representation of it.
We know that the algorithm was used because it was specifically described in ancient Egyptian texts. The calculator would use either symbols on paper or objects representing successively larger numbers (1,5,10 etc) to perform the algorithm. He obviously wouldn't use only a single stone to count out each number.
No, it absolutely does not help. In the algorithm you are citing, the numbers never leave their binary representation; there is no counting of the units that make up the number. The step of multiplying by 2 is done by shifting the binary representation of the number, which is not the way that this supposed "Ethiopian algorithm" works. The long multiplication algorithm (in binary or not) has complexity O(log(NM)), where N and M are the numbers to be multiplied, while this algorithm has complexity O(NM), and also gets there in a roundabout way.
This algorithm is totally pointless if you're not going to work with a positional notation for the number; I am sure it was never used in the way described, with stones. Anyone capable of understanding the problem in the first place - 34 goats, 7 pieces per goat - would count out the price - here is 7 for the first goat, 7 for the next, etc. - and tell the shaman to take a hike. This story amounts to calling Ethiopians idiots for taking an algorithm suited for positionally represented numbers - or at least numbers in some kind of a concise representation - and using it in a totally unnecessary way with numbers represented as groups of stones, and not understanding the pointlessness of all the drudgery.
No, the algorithm as described is very different from binary multiplication. It requires a number of stones proportional to the result, while the number of bits required when doing binary multiplication is polylogarithmic.
It's a big difference: 1000 * 1000 would require 1000000 stones if done with the "Ehiopian algorithm", but it can be done with less than 1000 stones by using normal binary multiplication.
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.
I don't get why there has to be a 'positive' or 'negative' angle on the story. You're trying to compare two different cultures in terms of which is 'better', which is a completely pointless goal. Nobody is saying native Ethiopians developed abstract mathematics as complicated as those of Greek, Arab, Chinese, etc. cultures.
>This algorithm allows people to multiply two numbers if all they can do is multiply and divide by 2, and add.
Yes, and the algorithm of making N groups of M and then counting allows people to multiply if all they can do is count. And they will do it far faster than the shaman every time.
>And yet is it so efficient it is how computers multiply.
> Yes, and the algorithm of making N groups of M and then counting allows people to multiply if all they can do is count. And they will do it far faster than the shaman every time.
I don't know. I notice that I am confused, so I know that between my existing beliefs and the details of this story, something important is fictional.
My strongest guess is that it's the stones. In any base > 1 the algorithm is efficient. In unary (counting stones), it inefficient to the point of being nonsensical.
So my guess is that this was not used by counting stones, but with some form of positional number system, and that in the retelling, stones have been added as a way to make it sound more "tribal".
Edit: Alternatively, it may be the idea that they're doing this exactly. If the doubling side is done by rough estimation (eyeballing the size of the piles), it might be faster.
You are comparing a later development of mathematics to an ancient one and then calling the ancient one stupid.It is basically like studying string theory now and then calling Galileo's speculations idiotic because he used his pulse to measure time instead of a quantum-logic clock.
No, he is comparing an ancient system (ethiopian multiplication) with an even more ancient one (just fucking counting) and calling it stupid. As far as I can tell, he's got a point.
That's a fine argument with 7 times 34, because you only need 7 holes of 34 stones.
But it breaks down when multiplying much larger numbers, because the number of holes you need increases by N. With this addition system, you only need log(N) holes.
The system exists to remove cumbersome aspects of multiplying large numbers by counting. Consider 34x34. While one fellow is out digging 34 holes, making sure not to make a mistake, or finding a piece of wood that has 34 holes marked in it, the other guy never needs more than 10 holes if his numbers are less than 1024. This keeps his working area small, and he can see all of it at the same time. It's less cumbersome this way.
As described, the Ethiopian Method would take far more stones and far more time. The larger the numbers you are working with, the larger the discrepancy.
John H. Lienhard is Professor Emeritus of Mechanical Engineering and History, getting his PhD from UC Berkeley.
> I fail to see the ingenuity,
You can't see something ingenious with probably illiterate people using a different base to multiply numbers? As per the Wikipedia link posted by vilhem_s "The method as interpreted by conversion to binary is therefore still in wide use today as implemented by binary multiplier circuits in modern computer processors."
You can't see something ingenious with probably illiterate people using a different base to multiply numbers?
While it's a nice trick, it's a circuitous route to get to the answer, and requires considerably more stones than the number you're trying to count to. Simply laying out X stones per Y items and counting them uses no methods that the shaman's system doesn't already use, requires less stones, and doesn't require any 'good' or 'evil' silliness.
Besides, if a trick works, but it isn't understood why it works, then the users of it lose the 'ingenious' tag, methinks.
Given that they speak of "evil numbers", I think it is reasonable to assume that the Shamans did not understand how the algorithm works. The inventor may have, but it seems likely that the users did not.
I see ingenuity in the creation of the technique, but if it was handed down over generations without the understanding of why it works, then that isn't a display of ingenuity. Contrast that to a typical student in who is given the same task of multiplying 7 x 34. They can get the same result and are also taught why multiplication works.
> I see ingenuity in the creation of the technique, but if it was handed down over generations without the understanding of why it works, then that isn't a display of ingenuity.
Sure. Me laying in bed listening to radio 4 is not ingenious, even though there's some ingenuity in creating radio (and the industrial infrastructure to get a radio to me).
Of course, no-one is yelling about ZOMG PC CONSPIRACY when I say how amazing it is that I can buy a radio for a few dollars.
> John H. Lienhard is Professor Emeritus of Mechanical Engineering and History, getting his PhD from UC Berkeley.
Close enough for me. Frankly I doubt that he honestly believed every word he wrote. People in high places have to routinely perform public worship of the PC god, "all cultures are equal", etc.
You're taking a cute fictional story and running wild with it to somehow fit your weird anti-PC agenda. No one here, including the original article's author, is claiming that this is evidence of cultural equality. Way to waste your energy.
> So how do we and that Ethiopian shaman differ? Very little, I reckon.
> Very little indeed. Of course, I wouldn't be surprised if he makes fewer mistakes than we do.
The article clearly dumbs down (or misunderstands)the algortihm, insulting the audience's intelligence to make a feel-good claim about the arithmetic talent of "uncivilized" Ethiopians, and is accidentally racist in the process.
Good grief. Lienhard's "Engines of Our Ingenuity" is a series of short (<5 min) radio monologues that are played every weekday morning and afternoon on KUHF public radio in Houston, (and other places I'm told). I would imagine that Lienhard simplified the bit to get it in the allotted time, and to make it understandable and interesting to a radio audience. I've met Lienhard several times and I can tell you that he is a quite personable guy for an old engineer. It is pretty funny to imagine Lienhard, or much else of KUHF as if it were some enclave of PC progressive liberal influence. And, if you'd ever been to the UH campus, especially the College of Engineering buildings, you probably wouldn't be stricken by the grandeur of the place.
It is simply a way of performing multiplication without requiring a positional notation system. If you don't have that this allows you to do multiplication of very large numbers assuming you can divide and multiply by 2. You could do this on paper but usually you would have objects that would represent number units used in the culture such as 50,10,5,1 etc. So your objection that you might as well count them out is simply not true, this method is faster than what you suggested.
>>Reality doesn't always conform to the PC narrative of how all civilizations are equal. Unless you are a sociology major that is.
I'm not sure what your point is. True positional numerals have a long cultural history that doesn't lend itself easily to an analysis of which culture performed math better.
How is that an answer? In the end you're still going to be counting out 2736 stones either way. In the shaman's algorithm, you'll end up doing so twice and some change, in a much more complicated and easily screwed up algorithm.
The algorithm actually does make sense for positional systems (or compact notations in general). Think of long multiplication: it assumes you can multiply by a one-digit number, and lets you get from there to multiplying by a many-digit number. This is the same thing, but it only assumes you can multiply by two, instead of by any one-digit number. So this is a variant of long multiplication, and equivalent to performing long multiplication in binary. But it only makes sense if you have a compact representation of your numbers, since otherwise you may indeed just perform the multiplication directly by counting out 7 stones for the first goat, 7 for the next, and so on.
It is the version described by Lienhard - which involves counting out the whole number anyway, which you could just as easily do without any special algorithm - that is pointless.
The algorithm only requires 12 holes, and scales the number of holes logarithmically. As opposed to make one group per unit, which scales the number of groups linearly. Less holes, less work, win.
If you squint your eyes a bit, you can even imagine where this comes from. To avoid creating too many holes, you start with a group of 7 stones, then double them, then again, until you "double" them 34 times. Obviously 34 is not a power of two, so you need some extra machinery to make it work for non powers of two.
I have an algorithm that only takes 7 holes compared to your 12 which is seven bucks per sheep means make seven holes and shove 34 sheep into each money hole then count the total.
Its an interesting Sunday morning to rack my brain trying to figure out which algorithm "wins" when parallel processed.
Obviously 34 shamans working together could each count out seven dollars/rocks, but someone needs to count up all those rocks.
There's an obvious token passing algorithm involving three shamans and I believe 7+34=41 rocks and 4 holes where one does a long count of the total and count++ every time upstream hands him a rock, then upstreams upstream does the same. So one dude counts to 34 using 34 rocks one time, the next dude counts to 7 (and does it 34 times) using 7 rocks, and the last dude counts every time dude 2 hands him a rock and never resets to zero (at least until done) giving him a total.
You can tell scientists invented the original algorithm not engineers just by a simple observation of actually implementing the algo... "Yo shaman come over and mult 7 by 34 for me" "OK but how many rocks will I need to multiply this... do me a favor and whip out your iphone and google 7 asterisk 34 so I know a lower bound of how many rocks to bring to implement this algo.."
The worst part of the whole discussion is it reads like a really extraordinarily bad stereotypical tech interview question. "So, I see you've got extensive experience on the job with Scala and Mysql and play framework, thats all very nice, but a major problem we often have here at BigCorp is sometimes we want to measure precisely 4 oz of rum but we only have a 3 oz and 5 oz cup and we were wondering what you thought of that ..." You know some kind of space alien anthropologist is going to hear this is how those ancient "humans" used to select their programmers and the space aliens who hear pop sci stories about human programmer interviews are going to think 1) We were insane/stupid 2) They're superior. Theres not much other reason for the whole story.
> I have an algorithm that only takes 7 holes compared to your 12 which is seven bucks per sheep means make seven holes and shove 34 sheep into each money hole then count the total.
Good thing for the shaman's job security that there are more numbers that can be multiplied than 7 and 34, then. Try multiplying 34x34.
For large multiplications, using the method described uses a logarithmically smaller working space in a society where positional numbers didn't exist and paper was rare, expensive, or nonexistent.
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
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.
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.
> 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.
You are flailing at windmills here. Sure the country has a long history of Christianity; however that part of the world has a long history of overlapping animistic traditions too.
It's true that Ethiopia has had large ancient Christian (and also Jewish and Muslim) populations, but it also has established Folk traditions that exists even today, there are still about 2 million animists in Ethiopia.
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.
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])
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.
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.
https://en.wikipedia.org/wiki/Ancient_Egyptian_multiplicatio...