16 ms·
Russian Peasant Multiplication
- lawlessone 9y agoCould this be used to speed up multiplcation by computer? or is that already a "perfectly" optimized?
- jwilk 9y agoThis is mostly equivalent to grade-school multiplication, but in binary. Good enough for multiplying small numbers; too slow for very big numbers.
- sirclueless 9y agoActually, this is basically how it is done in circuits, with some minor optimizations on top and without the explicit doubling operation. It's about as simple as you can make a task like this. The grade school mechanism doesn't look so bad, when you consider that where multiplying by a digit 0-9 occasionally involves some carrying and non-trivial work but multiplying by a binary digit is a simple AND operation. The result is that with fixed operand size and no carrying, each digit you would write under the line using the grade school method can be determined directly as the AND of two bits of the input, and what's left is only a bunch of binary addition. https://en.wikipedia.org/wiki/Binary_multiplier https://en.wikipedia.org/wiki/Binary_multiplier
- ColinWright 9y agoSee also: http://www.solipsys.co.uk/new/RussianPeasantMultiplication.html http://www.solipsys.co.uk/new/RussianPeasantMultiplication.h...
- deleted 9y ago[deleted]
- sounds 9y agoThis is a good introduction to how to create a binary multiplier unit in digital logic.
- tandav 9y agoBTW There are many fast algorithms https://en.m.wikipedia.org/wiki/Multiplication_algorithm https://en.m.wikipedia.org/wiki/Multiplication_algorithm Fastest of them use FFT and parallelism
- gozur88 9y agoI really love this kind of stuff, and it makes me wonder how the first person who did it figured it out.
- tgb 9y agoMy takeaway (since I'm okay at multiplying numbers) is the algorithm for figuring out the binary digits of a number. I've always just done "okay, it's bigger than 256, so subtract that and then it's bigger than 64 so subtract, etc." I much prefer this strategy of successively divide by 2 and discard remainder, mark a 1 for each time that the result is odd and 0 for even.
- romwell 9y agoThat's, essentially, the algorithm for computing the representation of a number in a given base: divide by the base and write down the remainders. To build up intuition on how this works, do it with base 10. What are the digits of the number 8675309 ? Just remainders after repeatedly dividing by 10. Now when it's almost obvious it works for base 10, you realize there's no reason it wouldn't work the same way for other bases. Hence the algorithm.
- tgb 9y agoYou're of course completely correct, but I feel like that misses the point. The great thing about this algorithm is not that it works - there are plenty of ways to figure out the binary representation of a number. Rather, it's that it only needs operations that are easy to perform and requires little state to remember. I'd much rather divide by two and round down than subtract the largest power of two that's less than my number from it. And I don't have to remember which power of N I last worked to know how many zeros I need to add before using the next power of 2 that fits in my number.
- jcoffland 9y agoI've been using a less strict version of this method to multiply in my head since I was a kid. Nice to know there's a name for it. You can also take advantage of multiples of 5 and 10. For example: 115 x 37 = (100 + 10 + 5) x 37 = 3700 + 370 + 370/2 = 3700 + 370 + 300/2 + 70/2 = 3700 + 370 + 150 + 35 = 4255
- ricardobeat 9y agoThat's exactly how I do multiplication in my head! I wonder why school never taught something like this, I find the standard right-to-left-and-carry-over method impossible to keep track of without paper.
- pbhjpbhj 9y agoThey teach this method in my kids UK school, I'm pretty sure it's part of the standard curriculum.
- ricardobeat 9y agoWouldn't that be the 'grid multiplication' method? https://en.m.wikipedia.org/wiki/Grid_method_multiplication https://en.m.wikipedia.org/wiki/Grid_method_multiplication
- lancebeet 9y agoIn this case I would do 115 x 37 = 115 x (40-3) = 460 x 10 - 3 x 115 = 4600 - 345 = 4255 Since 15 x 3 and 15 x 4 are trivial calculations the only caveat is the subtraction which isn't too bad.
- smallnamespace 9y agoSomewhat surprisingly, this is how Common Core arithmetic is taught nowadays. Some parents are making a fuss because 'that's not how they learned arithmetic' [1], but actually anyone who is good with mental math uses these sort of tricks, particularly taking advantage of commutativity and distributivity. In fact this builds far stronger intuition for the properties of numbers and is a good way to prepare for algebra and proof-based approaches later on. Same sort of mental shortcuts for two-digit squaring: 52² = (50 + 2)² = (5 ⋅ 10)² + 2 * (50 ⋅ 2) + 4² = 5² ⋅ 10² + 200 + 4 = 2500 + 200 + 4 = 2604 [1] https://www.salon.com/2015/11/28/youre_wrong_about_common_core_math_sorry_parents_but_it_makes_more_sense_than_you_think/ https://www.salon.com/2015/11/28/youre_wrong_about_common_co...
- pmoriarty 9y agoAnyone interested in this should watch some "Flash Anzan" videos. Here are some of the more impressive ones I've seen: [1], [2], [3] Here's one describing more of the basics: [4] [1] - https://www.youtube.com/watch?v=JawF0cv50Lk https://www.youtube.com/watch?v=JawF0cv50Lk [2] - https://www.youtube.com/watch?v=7ktpme4xcoQ https://www.youtube.com/watch?v=7ktpme4xcoQ [3] - https://www.youtube.com/watch?v=_vGMsVirYKs https://www.youtube.com/watch?v=_vGMsVirYKs [4] - https://www.youtube.com/watch?v=OFmDvAnIXo8 https://www.youtube.com/watch?v=OFmDvAnIXo8
- nthState 9y agoI struggled and still do with multiplication taught in School. As a child my dad showed me "Napier's Bones". I haven't looked back since, it may be slower, more drawing, but for me it works https://en.wikipedia.org/wiki/Napier%27s_bones https://en.wikipedia.org/wiki/Napier%27s_bones https://www.youtube.com/watch?v=WZLpqTyZMM4 https://www.youtube.com/watch?v=WZLpqTyZMM4
- jeffwass 9y agoThat was awesome, I never heard of them before, just spent twenty minutes with the wiki link.
- adrianratnapala 9y agoStrange, to me that just looks like the standard algorithm put in a form that can be partly mechanised. I am surprised that it helps people who do not have a physical set of the bones themselves.
- fjsolwmv 9y agoIt doesn't, parent poster was confused. The bones are required to make the method useful
- jacobolus 9y agoYour video link just shows the common lattice method for writing the standard multiplication algorithm, used since at least the 1200s by Arabs and common around the world ever since. Napier's bones is a physical artifact, which tries to eliminate the required memorization of a 1-digit multiplication table, and is very rarely used in practice by anyone anywhere. https://en.wikipedia.org/wiki/Lattice_multiplication https://en.wikipedia.org/wiki/Lattice_multiplication
- nthState 9y agooh, I always thought it was called Napier's Bones, oh well.
- deleted 9y ago
- PinkMilkshake 9y agoAnother impressive system for mental arithmetic is the Trachtenberg System: https://en.wikipedia.org/wiki/Trachtenberg_system https://en.wikipedia.org/wiki/Trachtenberg_system
- tzhenghao 9y agoI highly recommend the Secrets of Mental Math book: http://a.co/095nXaa http://a.co/095nXaa Lots of good insights on how to make shortcut mental calculations.
- userbinator 9y agoAlso known as "shift-and-add", and very commonly implemented in microcontrollers and early microprocessors that didn't have multiplication instructions in hardware.
- knowThySelfx 9y agoSome of the Vedic Multiplication short cuts: http://mathlearners.com/vedic-mathematics/multiplication-in-vedic-mathematics/ http://mathlearners.com/vedic-mathematics/multiplication-in-...
- ztjio 9y agoWow! This website design is what everyone would have if the 90's dial-up BBS scene aesthetic had been the guiding light of website design from then on. And I like it.
- milankovic 9y agoEspecially that twisting Tag animation.. :)