More Multiplying

At the beginning of the month I posted about a neat Japanese visual method for multiplying smallish numbers. Besides its sheer visual attractiveness, it’s interesting in allowing one to multiply numbers without reference to multiplication tables (which, let’s face it, typically require rote memorization).

As I mentioned last time, my interest in multiplication is linked to my interest in generating Mandelbrot plots, which is a multiplication-intensive process. But for those learning math, digging into basic multiplication has some instructive value.

With that in mind, here are some other multiplication tricks.

Let’s start with a quick look at the long multiplication method most of us learned in grade school…

§ §

Figure 1.

Say we want to multiply 42 × 123. We would generally do it as shown in Figure 1.

Generally the smaller number goes below the bigger one (if one is smaller than the other), but it doesn’t matter mathematically — it’s the same result, called a product, either way.

(The order does have a slight impact the number of calculations, though.)

The calculation starts with the right-most digit of the bottom number (2, in this case). Multiply that digit by the top number: 2×123 =246. This intermediate product goes on the first line below the two numbers.

Moving left, take the next digit of the bottom number (a 4) and repeat the multiplication: 4×123=492. This new intermediate product goes below the first one. It’s also moved one space to the left (because the 4 is one space to the left).

If there were more digits in the bottom number, we’d keep repeating the process, building the intermediate products downwards, each one progressively moved one space to the left.

Figure 2.

Which is why most people put the smaller number below.

When the lower number is bigger (which is to say longer), there are more digits to cycle through, so there are more intermediate products to keep track of (see Figure 2).

The issue then is keeping the columns lined up. The Python code that generates these figures keeps everything in a nice grid, but when scribbling by hand, one has to be careful about columns.

(Of course, any sane person just uses a calculator.)

§

Speaking of the Python code, you may have noticed leading zeros in the final and intermediate products. It’s a consequence of what I explained last time about multiplication involving a Cartesian product of the multiplicands (the two numbers being multiplied).

If one multiplicand has length m, and the other has length n, then the result will have length m+n — although the first (left-most) digit may be zero.

As a simple example: 2×4=08 and 2×6=12

The edge cases show the limits: 1×1=01 and 9×9=81

There is also a degenerate case: 0×{any}=00

In Figure 1, the intermediate products have four digits (3+1) and the final product has five (3+2). In Figure 2, the intermediate products have three digits (2+1) while the final product has six (2+4).

That first digit is the carry digit. Sometimes a multiplication carries into it, sometimes it doesn’t.

Figure 3.

The figures so far don’t show the various carry operations applied to each intermediate result and to the final result.

When people do this by hand, they usually use little tiny carry numbers (as shown in Figure 3).

Four times three is twelve, so the 1 carries (making an eight a nine), and nine plus two is eleven, so that 1 also carries (making the four a five).

It’s possible to skip carrying until the final stage (although this makes the columns harder to keep track of).

Figure 4.

Figure 4 shows the same multiplication as Figure 1, but without the carry operations on either the intermediate products or on the initial sum of those products.

But once the sum is computed, a ripple carry (right-to-left) generates the final product.

(In fact, in this version, the code could skip the leading zeros except for the final result. Those leading zeros are to insure that the intermediate ripple carries have a carry digit in case they need it. Note that, in Figure 2, the first intermediate product did ripple into that carry digit: 3×4=12.)

§ §

That’s all pretty normal and what we’re used to (except, for some, perhaps the idea of not carrying until the last step).

Here’s a technique, attributed to Russian peasants, that requires only the ability to halve and double numbers (in addition to adding). It does not require memorizing multiplication tables.

(The ability to halve and double is multiplying by one-half and two, respectively, but the doubling is just adding, and halving is just its flip side, so it’s pretty easy to learn as a standalone skill.)

Let’s start with an example. We again multiply 42×123:

42 × 123
42 123
21 246
10 492
5 984
2 1968
1 3936
5166

For the first number, create a column of numbers below it by repeatedly halving the number (discarding any fraction — e.g. half of 5 is 2.5, so we just use the 2). Stop when the value reaches 1.

For the second number, create another column of numbers below it by repeatedly doubling the number.

Now use the odd numbers in the first column to select out the matching numbers in the second column. Ignore the ones across from the even numbers.

Sum the selected numbers. The sum is the product.

It’s a cute technique, and the way it works is slightly sneaky. (It’s actually two nice tricks in one.) I’ll explain at the end of the post to give you some time to think about it.

(Here’s a clue: the binary value 42 is 101010. (Which I’ve always thought was really cool.))

§

This also works with the numbers reversed:

123 × 42
123 42
61 84
30 168
15 336
7 672
3 1344
1 2688
5166

The answer is still 5166.

(Another clue: the binary value of 123 is 1111011.)

§ §

There is a similar method attributed to the ancient Egyptians. It uses only doubling, no halving. The downside is it requires some tetchy figuring:

42 × 123
1 123
2 246
4 492
8 984
16 1968
32 3936
5166

Below the first number, start with one and create a column by repeatedly doubling the value. Stop when the next doubled value would be above the first number. In the example, the next doubled value would be 64, which is greater than 42.

Below the second number do the same thing as in the Russian method. Start with the number and double it repeatedly to provide matches for the numbers in the left column.

Now the tetchy part. From the first column figure out which values sum to give the first number. Here 32+8+2=42, so those are the values we select. (Do that by starting with the greatest value (32) and subtracting it from the number (42-32=10). Then find the next greatest that can be subtracted and repeat: 10-8=2, 2-2=0.)

Finally, as in the Russian method, add the matching values from the second column. Their sum is the multiplication product.

§

And, of course, it works equally well with the numbers reversed:

123 × 42
1 42
2 84
4 168
8 336
16 672
32 1344
64 2688
5166

If you compare this with the Russian method, you’ll see they essentially do the same thing. I like the Russian method more, as it avoids the need for figuring out which factors in the left column to use. What the Egyptian method does, though, is make it a bit more obvious how the method works.

If you don’t see it, I’ll explain after one last multiplication method.

§ §

The diagonal lattice method is somewhat like the single-line modification of the Japanese visual method (see Figure 5 and Figure 6 in that post).

Figure 5.

As with the Japanese visual method, the focus is the grid created by the Cartesian product of the multiplicands, which are written along two edges of the grid.

Figure 5 and Figure 6 in this post illustrate the method with the usual multiplication: 42×123.

For each square of the grid, multiply the two digits that intersect at that square. The result is a two-digit number (the first digit can be zero), so write the digits in two parts of each box. First digit in the upper left; second in the lower right.

Sum the diagonals downwards. Note that each diagonal “bottoms out” on the top of the upper of the bottom two rows — they do not extend down into those boxes! Each diagonal ends on top of a box. Write the sums in that top row of boxes.

Figure 6.

The sums also have two digits, so again split them upper left and lower right. Now the lower set of diagonals come into play. Sum the upper row into the lower row diagonally.

Except for the ends, each diagonal has two digits in it. The right-most just drops into the right-most box. We can safely ignore the left-most digit with nowhere to go; it will always be a zero.

The sum in the lower row is the final product.

§

All three methods, lattice, Japanese visual, and long-hand, work by generating the Cartesian product and summing it diagonally. They differ in how they accomplish that diagonal summing.

The diagonal lattice keeps things nicely aligned, plus carrying is built in by how the diagonals work. One never has to ripple carry. And it has some of the visual appeal of the Japanese visual method.

That said, if one actually does have to do a multiplication by hand, it’s usually quickest and simplest just to use the old-fashioned long-hand method, although some version of the lattice method, once practiced, isn’t bad.

§ §

The Russian and Egyptian methods, on the other hand, work in a rather different way. They essentially do half-binary math.

The left column in both methods ends up being a binary representation of the number. The Russian method nicely generates it easily on the fly, whereas the Egyptian method gets with chain subtraction. Either way the first number is converted to binary.

Figure 7.

That effectively gives us something like Figure 7.

Note that each 1 bit just creates a copy of the upper number shifted by however many bits left that 1 bit is. One times a value is just that value. (If the bit is 0, then the intermediate product is also 0.)

However, each bit shift to the left represents a multiplication by two. We can’t sum those columns as shown. (Because we can’t really mix binary and decimal numbers this way.)

That’s why the Russian and Egyptian methods have a doubling of the second number in the right column. Those correspond to the a doubling of the intermediate product. The occurrences of 0123 in the intermediate product, with doubling, from top to bottom, are 246 (2×), 984 (8×), and 3936 (16×), which are the same shown in the examples of these methods above.

How about that?

An ancient technique using binary math way before computers.

Stay productive, my friends! Go forth and spread beauty and light.

About Wyrd Smythe

The canonical fool on the hill watching the sunset and the rotation of the planet and thinking what he imagines are large thoughts. View all posts by Wyrd Smythe

13 responses to “More Multiplying

  • Wyrd Smythe

    To illustrate why we can ignore that leftmost carry digit, here’s an edge case:

    The leftmost diagonal only has the carry digit of that one intermediate multiplication in the upper left corner. The most that square can be is 81 (9×9), so the most the carry digit can be is 8 (as shown).

    That means the highest possible value in the leftmost box of the upper of the bottom two rows is 08. That 0 on the far left is always a zero.

  • Wyrd Smythe

    BTW,… last night’s debate,… another travesty of American Politics, another embarrassment in front of the world. I’ve been holding off getting political, but starting tomorrow the gloves come off.

    • SelfAwarePatterns

      I didn’t watch the debate last night. The more I read and hear about it, the better I feel about that move. I even stayed offline once it was obvious everyone in social media was going to be venting about the extended dumpster fire. Overall I had a much more pleasant evening reading science fiction.

      • Wyrd Smythe

        It was almost a case of bearing witness to the death of democracy and American tradition. We are truly at an existential turning point.

      • SelfAwarePatterns

        It sounds like the debate commission is planning changes. Trump is objecting, but they’ve made it clear it isn’t a negotiation. Maybe the other debates won’t happen. Personally I think that would be for the best. I can’t imagine the few undecideds at this point are getting anything useful.

      • Wyrd Smythe

        I can’t fathom how anyone could be undecided at this point. I didn’t much care for Hillary Clinton in 2016 (or ever) but the choice was pretty clear. I don’t care much for Old Joe, either, but the case is abundantly clear.

      • SelfAwarePatterns

        Personally, it seems hard to imagine which candidate other than Trump wouldn’t be the clear choice. I’m pretty sure the Democrats could have nominated a turd pile and it would be getting my vote. But then, that was true for me in 2016.

      • Wyrd Smythe

        We’ll find out who and what we are as a nation in the next four months or so. I’m not optimistic.

      • SelfAwarePatterns

        All we can hope is that Biden wins with enough of a margin to minimize doubt. Unless he wins, Trump will claim it was fraudulent no matter what, but other Republicans will have to weigh loyalty to him against their own future career prospects. If it is close, it’s going to be very ugly.

      • Wyrd Smythe

        Yep, there needs to be a landslide, a clear mandate. (The terrifying thing is that Americans really suck at unity on anything these days.)

  • headbirths

    I’m enjoying your maths posts. This took me back to learning about Napier’s Bones at school (and Cuisenaire rods before that).

And what do you think?

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: