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:

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:

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:

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:

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.

∇