Geeky awesomeness.

[theweaselking]

Wherein I lose half my audience because I'm geeky, but I usually make sense to laypersons:

"Russian peasants multiply using a most curious method. They start by writing the two numbers to be multiplied at the head of two columns. Then they repeatedly divide the number in the left column by two (dropping any remainder) and double the number in the right column, writing the two new numbers immediately below their predecessors, until the number in the left column is one. Then they cross out all rows where the number in the left column is even, and add the remaining numbers in the right column, which is the desired product. For instance, the product eighteen times twenty-three is found like this."



Your challenge:
Are they right to do so?
Can you explain why/why not?

(I know the right answer to both questions, for the record. But this still makes me happy)

Comments

[kafziel.livejournal.com]

It appears sound, and I think I know why, though this explanation is gonna be shit.

We're halving and doubling, so think in terms of binary. To divide a binary number in half, and drop the remainder, you simply remove the least significant digit. 18, in binary, becomes 10010. That becomes 1001. Then 100. Then 10. Then 1. Or, in decimal, it becomes 9, then 4, then 2, then 1.

A binary number is "Even" if the least significant digit is a 0. So what we're eliminating is each iteration of the first number in which there is a 0 in the binary. That is, leaving only the iterations where there's a 1.

Now, if you think of it in terms of, instead of 18 x 23, being 23 * 2^1 + 23 * 2^4 - because that's what 18 is, 2^1 + 2^4 - then it makes sense. You're doubling the second number each time, so each digit of the binary first number corresponds to the second number multiplied by the significance of the last digit. That is, when we're checking what was originally the 4s digit to see whether it's currently even, on that line on the right side we have 23 * 4. When we're checking the 16s digit on the left, we have 23 * 16 on the right.

So, on the right, we end up with 23, 23 * 2, 23 * 4, 23 * 8, and 23 * 16, and we eliminate each one that doesn't match up to a 1 in the binary representation of the left number - that is, cross out 23 * 1, 23 * 4, and 23 * 8 - and are left with just 23 * 2 + 23 * 16. Which is 23 * 18.

Like I said, shitty explanation, but I'm not a math guy. But it seems to make sense and be viable.

[theweaselking.livejournal.com]

Yes! kafziel is exactly right! And I will screen your comment now, for the record, to avoid spoiling it for latecomers!

[hypatiasghost.livejournal.com]

oooooooh.

[dreamshade.livejournal.com]

Well, I didn't know right off the top of my head, so maybe I won't know for certain, but when you look at the list the right side, it looks a bit like you're looking at a polynomial, sort of like...

0*2^0 + 23*2^1 + 0*2^2 + 0*2^3 + 23*2^4

And actually, 10010 in binary is equal to 18 in decimal... Ah ha, you're basically converting the number on the left into a binary number and taking it times the number on the right. The test cases I've put together seem to confirm the conspicion, so I'll say that it always works.

[theweaselking.livejournal.com]

A winner is dreamshade!

[ipslore.livejournal.com]

I can see it, but I can't quite put it into words. The dividing/crossing-out process converts the first factor into a binary string - 10010 in this case - and the multiplying applies it to the second factor, so that you end up adding 2*23 and 16*23, and you get 18*23.

[ronebofh.livejournal.com]

I'm no mathematician, but it seems to me that rows with odd numbers function as a "remainder" holder, with the 1 row being the "subtotal". That's why it works.

[larabeaton.livejournal.com]

I would say that it is.

18 * 23 =
9 * 46 =
(4 * 92) + 46 =
(2 * 184) + 46 =
(1 * 368) + 46 = 414

When you can't divide a number by 2 evenly, you are left with 1 .... unit? left over. Each subsequent reduction needs to take that remainder into account. Ones that divide evenly don't need to account for the remainder.

[unknownpoltroon.livejournal.com]

I am going to nned 2 liters of potato vodka to figure this out.

[dglenn.livejournal.com]

Tired and cranky and too lazy to think it through, so let's see whether I can get it right mostly intuition without being obvious about the use of algebra ...

If they were retaining remainders, they'd be simply restating the same product different ways. Because they do drop remainders, the final "1 x $foo" line isn't quite correct, but each line with an odd left-hand multiplicand immediately precedes an introduction of error by rounding ... and the right-hand multiplicand on such a line contains the amount of error that will be inserted by the rounding in the next line. Add up just the (thus conveniently preserved) rounding errors and the final line, and unless today's heat and humidity have addled my brain as much as I've feared, the rounding is compensated for.

Aha! I thought it looked like it should work. I may work it out as a formal proof later, depending on how long you leave others' answers screened.

[kierthos.livejournal.com]

I almost feel obliged to quote from Tom Lehrer's "New Math", although that dealt with subtraction, not multiplication.

Simply put, however, yes, the Russian peasants are correct, because multiplication is associative. Which means that if x = a * b, then x * y = (a*b)*y

[falconwarrior.livejournal.com]

No, they are wrong because this is more complicated than the conventional method, and the simplest solution is always the best.

[hypatiasghost.livejournal.com]

That may be true, but why is the simplest solution always the best? Is it always the best, or is this a rule of thumb? What do you mean when you say "more complicated"?

I'm interested in your reasoning because I agree with you, but we're stepping into philosophy of science with this assertion and out of the realm of pure mathematics.

[falconwarrior.livejournal.com]

Well, obviously it doesn't have to do with pure mathematics. I knew right when I posted this that it wasn't the answer theweaselking was looking for.

The simplest solution is the best because it allows less room for error. In the Russian way shown here, there are 4 multiplications and 4 divisions, as well as some truncation of numbers. Then there are rules applied in eliminating several of the numbers obtained, and adding the remaining numbers. In the conventional way, this equation would be calculated by adding the product of the ones column of number "A" and the entire number "B" with the tens column of number "A" with the entire number "B" times ten. Or, mathematically: (B*A[1])+10(B*A[10]). Or, more mechanically, ((B[1]*A[1])+(B[10]*A[1]))+10((B[1]*A[10])+(B[10]*A[10])) where the bracketed numbers denote whether then value is from the ones column or the tens column. For this example, it would be ((3*8)+(2*8))+10((3*1)+(2*1)). Explaining it like this makes it sound a hell of a lot more complicated than it really is; if I made one of those handy .gifs it'd seem as simple as it really is. What I've given is a pure formula though, where all the variables are easily acquired; and it doesn't really matter which value is used as number A and which is used as number B. It's a mechanical solution which can be done the same way for any two two-digit numbers, and the formula can be adjusted as needed for values with different character lengths. There is no truncation of remainders nor any additional fiddling around with all the numbers used in the process. This is what makes it "simpler".

Thinkin' as both a math-weenie and an ex-teacher...

[dglenn.livejournal.com]

Different steps are easy for different people, and the same method can be perceived by two people as having different numbers of steps if one person combines some steps mentally. So "simplest" is not always[*] unambiguous, and "easiest" or "fastest" can trump "simplest" in a great many situations. So I would be disinclined to say that this is wrong, though it may be sub-optimal for many (clearly not all) humans.

If following the algorithm correctly guarantees a correct answer, then the algorithm is correct. If it's harder to reliably do correctly, or slower, or more taxing, then it is not best, but is still correct.

"Simplest" would be to count out A beads into a bucket B times and then count the beads in the bucket when you're done. (And in fact as slightly more organized version of that is how I was initially taught to multiply -- with glass beads. When I got to multiplicands too large to conveniently do that way, I was taught a different way to multiply with glass beads that logically followed from the simple multiplication I'd been doing -- which turned out to be related to "Napier's bones" but I didn't hear that name until much later. When I learned long multiplication on paper in a form like what you described (at what, uh, 4th grade age? hard to remember for sure), I was able to instantly recognize it as an abstraction of the long multiplication I'd been doing with glass beads, and that a logical extension of simple multiplication I'd done earlier with glass beads. It's still not as simple as repetetive addition by counting out glass beads over and over.[**])

Have you ever gone, "I'm too sleepy to multiply by 98, so I'll multiply by a hundred and subtract twice"? Is it "simpler"? Some days it's faster. (For some people it's always faster.)

A pencil-and-paper abstraction of binary multiplication without converting from decimal to binary first doesn't seem inherently less simple than a pencil-and-paper abstraction of repetetive addition, as long as doubling and halving are perceived as trivial tasks by the do-er. It's just a less familiar starting place.

[*] Yes, I know that sometimes it is, too. I'm not saying 'never'; I'm saying 'not always'.

[**] My Montessori teacher was ever so worried that she hadn't given me a solid enough grounding in mathematics because she kept catching me reading when I was supposed to be doing math, but when I graduated from Montessori to a conventional school, it turned out that I actually had a grounding in mathematics rather than just some arithmetic skills like a lot of other students, because of how Montessori teaches math. A year after that, when I started algebra, a hell of a lot of it just looked obvious to me, because it looked just like what I'd done with glass beads, but with variables instead of digits.

[the-trav.livejournal.com]

fascinating... Umm, so by dividing the left and multiplying the right they're not actually changing the equation at all, because x*y == 2X*y/2, that part I get...

How do you handle odd left hand columns when they get to 3? stop dividing?
Ahh, I notice that you've rounded down a remainder when you went from 9 to 4.

So they're not changing the equation, except when they drop remainders and for those cases the number on the right hand side represents the amount of 1's that would come from that remainder... I could probably do a maths proof for that... lets see... 9*46 = 8*46 + 46 yeah, that's the basic multiplication dealy, that's how it works, so then we're just splitting the 8*46 thing down more and more until we end up with 1*368+8*46

HURRAY! worked it out without google

[publius1.livejournal.com]

Oh, just tell us ><

[theweaselking.livejournal.com]

Yes, they're right. What they're doing is binary long-form multiplication without actually using binary.

It's quite neat!

[publius1.livejournal.com]

Cool! I figured it actually had something to do with the distributive property of multiplication, but I just did not want to think about it too hard. Heh.

[skiriki.livejournal.com]

Figures that you also read the same site as I do where this was presented originally. :D

[doug-palmer.livejournal.com]

Works for me. It's essentially multiplication of binary numbers by shifting and accumulation. Every odd number on the left hand side means that the lowest bit is set and you add the shifted value to your running total.

[hypatiasghost.livejournal.com]

This is totally neat. I haven't read the comments that are on here yet today, but I saw yesterday you were screening them.

Yes, it work. It's really neat, and I don't quite know *why* it works, though I *feel* like there's a balancing out thing happening with the dropping of the remainder and then not adding in the right column when the left column is even. But I don't really get it, I'm not sure what's going on. Number theory is *so neat*, but I haven't played with numbers often enough to really feel it.

I don't know that they are right to do it this way. While it's easy to learn to divide and multiply by two, and then to add columns of numbers, it takes much longer and there are more steps involved, which means it is more prone to error for the careless (like me). The "long multiplication" method that I learned is faster, and has fewer steps, but does require that you "know" your "multiplication tables."

I am moved to post, again, Lockhart's Lament, that we do not play enough games with numbers like this as children. If only all children could be so lucky as to have really talented mathematicians for math teachers, writers for literature teachers, and scientists for science teachers...

[hypatiasghost.livejournal.com]

And I meant to use this icon to respond.