My interest in number multiplication goes back to exploring algorithms for generating Mandelbrot plots, which can require billions of multiplication operations on arbitrary precision numbers (numbers with lots and lots of digits).
Multiplying two numbers — calculating their product — is computationally intense because of the intermediate Cartesian product. Multiplying two 12-digit numbers creates a 24-digit result (12+12), but it also has an intermediate stage involving 144 (12×12) single digit multiplications.
Recently I learned an intriguing Japanese visual multiplication method.
For quite some time I’ve had notes about a possible post regarding the Cartesian product aspect of multiplication. Discovering this Japanese method provided a long-sought hook for it.
As I mentioned, Mandelbrot plots can require billions of multiplications, each with hundreds, even thousands, of digits, so it’s a topic of interest to me.
The thing about multiplication is that that the number of significant digits grows with each operation. A multiplication product has as many digits as its two factors combined. Multiplying two 50-digit numbers creates a 100-digit number. So would multiplying a 20-digit number times an 80-digit number.
The Mandelbrot formula starts with a given number, Z and squares it — that is, multiplies it by itself.
It adds another given number, C, to the product and uses the result as a new Z to keep repeating the calculation until it gets a result greater than two. (If this never happens, then C is in the Mandelbrot set.)
The thing is, each time through the loop, since Z multiplies itself, the number of digits doubles. That can’t be sustained for billions of operations, so at some (very large) length, the numbers are truncated and some precision is lost.
Here’s the killer part: Say we truncate our numbers at 500 digits. That’s a precision level way beyond Planck level (which is a mere 34 digits). But there are Mandelbrot zooms using thousands of digits, so we’re being quite reasonable with 500-digit numbers.
The product will have 1000 digits, but generating it requires 500×500 single-digit multiplications (each of which generates a two-digit intermediate product).
That’s 250,000 intermediate multiplications — the Cartesian product of two 500-digit numbers. That’s a lot of intermediate calculations to generate a result.
Note that a Cartesian product is naturally a table of rows and columns, like a spreadsheet. Summing the table cells along diagonals generates the multiplication product. (See illustration at top.)
The Japanese visual method for multiplication illustrates the tabular nature of the intermediate Cartesian product. The fun part is that it does it using base one arithmetic.
Let’s say we want to multiply 42 × 65. We start by drawing lines as shown in Figure 1.
For the first number, use lines that slant down to the right, and draw as many lines to match each digit. Note the number, as numbers do, flows from left-to-right — first the 4 and then the 2.
For the second number, use lines that slant up to the right, and again draw as many lines for each digit. Note again the number flows left-to-right, first the 6, then the 5.
To keep things clear be sure to keep some separation between the digits, and keep your lines nice and neat.
The next step is to count the number of intersections in each group of lines crossing. In this example, there are four such groups (Figure 2).
This is the base one arithmetic part. Each line crossing counts as one, and the total count of a group turns out to be the product of multiplying those two digits.
For example, in the top group, there are 12 line intersections (in a 2×6 grouping), and obviously 2 × 6 = 12.
The other three groups are similar — each is the product of multiplying the two digits involved. All four groups comprise the intermediate Cartesian product of multiplying 42 and 64. Each group itself is a Cartesian product of multiplying two digits.
Now we sum the groups.
We do this left-to-right starting with the first corner.
Then we combine matching corners. That can get a little tricky if the two factors have a different number of digits, but when both numbers have the same count of digits, the resulting diamond shape is simple.
(In fact, this technique is beautiful and interesting, but somewhat limited to numbers with only a few digits and — ideally — the same number of digits or nearly so. As you’ll see, things get unwieldy fast, which is only to be expected with base one arithmetic.)
The result is a row of sums across the bottom (see Figure 3).
The final step is just to carry the overflows.
This time we work from right-to-left, starting with the 10 and ending with the 24.
Starting with the 10, we carry the 1 to the left and keep the 0, so the rightmost digit of the final product is a 0.
The carried 1 increases the 32 to 33. We carry the tens 3 and keep the ones 3, so the next digit of the result is 3.
The carried 3 increases the 24 to 27. We carry the 2 and keep the 7, so the third digit is 7.
The carried 2 is alone, so it’s the final digit of the result product.
And, sure enough, 42 × 65 = 2730.
It’s a cute trick in that, if you really do just count the line intersections, there is no actual multiplication involved — just counting and addition.
It would be possible, but beyond unwieldy, to treat 42 and 65 as the single numeric quantities they actually are (rather than as a pair of base ten digits).
That makes the two numbers single “digits” (“symbols” is a better term here), and we’d draw it as a single group with 42 lines crossed by 65 lines. The count of all the intersections is 2,730 — the literal Cartesian product of 42×65.
By the way, area is another Cartesian product. A 50′ by 40′ field has 2000 square feet. Think of each square foot as an intersection among the 50 by 40 lines drawn each foot.
It’s a topic I’ll return to in the future, but for now an important point is that, with regard to multiplication’s intermediate Cartesian product, “digit” can be any numeric container we need (which is why “symbol” is a better term).
As the Japanese method demonstrates using base one, multiplication is ultimately just counting a Cartesian product. I find especially interesting that it’s easy to work with any numeric base due to how carry is deferred until the final step. Input and output numbers can be in any base.
(That’s a post for another time.)
Above I mentioned that multiplying two 50-digits numbers results in a 100-digit result.
The same goes for multiplying a 20-digit number times an 80-digit one. For that matter, likewise multiplying a one-digit number times a 99-digit number.
(Caveat: potentially; the result can be one digit shy. As a trivial example, 2×4=8, but 2×5=10. The upper limit is “all nines” numbers, 99×99=9801. In contrast, 11×11=121.)
There is a lot more difference when it comes to the intermediate products, though. Multiplying two 50-digit numbers generates a Cartesian product of 2500 values (50 rows, 50 columns). But when they are 20-digits and 80-digits, the intermediate table has only 1600 values.
And in the case of one-digit and 99-digits, there are only 99 intermediate values!
(It shows why the Mandelbrot calculation is such a killer. Squaring a number, by definition, means both factors are the same length, which is the worst-case scenario in terms of Cartesian product.)
As you might imagine, this business of drawing lines can get unwieldy. If we’re willing to forego the counting and do single-digit multiplying, this visual method is a bit easier (if less visual).
Rather than draw base one lines we must count, draw a single line for each digit (see Figure 5).
Rather than count lines intersections, at each digit crossing we do the single-digit multiplication we learned in grade school from multiplication tables.
Essentially we’re hiding counting the visual Cartesian product and using rote memory instead.
As an aside, a multiplication table is a Cartesian product generated from two matching sequences of integers. (Since the integer sequences are infinite, the table is “infinite-squared” — which is just infinite. Both are enumerable and, hence, the same size of infinity.)
Once we have the set of intermediate products (by multiplying rather than counting this time), the process proceeds as before.
We sum the diagonals starting at the leftmost corner and working across (see Figure 6).
(I’ll note again this looks more complicated when the two numbers are quite different in length, but it’s just a matter of lining up corners. As a self-check, you should always end with the rightmost corner on its own. In fact, you could work right-to-left from that rightmost corner. That would align nicely with the carry, which ripples right-to-left.)
You might notice this looks somewhat like the standard grade school technique of long multiplication.
In fact it does very much resemble it. A notable difference involves the carrying. Long multiplication does it throughout while this method defers it to the end.
The post I have notes for involves something very similar to, even isomorphic with, the Japanese visual multiplication method (although more in the reduced form shown directly above).
The image at the top of this post illustrates a “grid” method of multiplication, and you can see the similarities if you rotate the image at the top 45° clockwise, or if you rotate the Japanese diagrams 45° counter-clockwise. Either way, it’s the same sort of thing — a Cartesian product summed diagonally.
I may return to pick up the thread (although maybe not; perhaps this covers the topic well enough). For now, I’ll leave you with some images.
One night I got to thinking about how to code an algorithm to create images of the Japanese multiplication method.
As it turned out, pretty easy (like just a couple hours messing around got most of it done — the polishing took several times as long).
It was easy to code because I rotated the images 45° counter-clockwise (which aligns them with the image at the top of the post). Note that the first number, 123, runs along the left from bottom-to-top, and the second number, 789, runs along the top from left-to-right.
The thin red lines show the summing diagonals. In the image above (Figure 7), starting with the lower-left corner, the sums are: 7, 22, 46, 42, 27.
The carry ripples from right-to-left:
- 27→7, carry 2
- 42+2=44→4, carry 4
- 46+4=50→0, carry 5
- 22+5=27→7, carry 2
Giving us our final result: 97,047.
There are some limits to the technique:
It does get a bit crowded, especially with nines. (Although I can always just make the image larger.)
These two used factors with the same size, which results in a square grid with nice 45° diagonals (the ideal case for the Japanese method). You can easily rotate this to make it look exactly like that method.
It’s a bit less elegant when the numbers are different lengths:
The trick is to start at one corner and work across. (Or write code to do it!)
The algorithm requires each number have at least two digits, but it’ll accept leading zeros to create a minimal example:
(A true minimum would be 1×1, but that’s too boring.) Note how, when a digit is zero, there are no line intersections to count. In this case, only the upper-right corner — the last corner — has a non-zero value.
One tweak my algorithm needs is better spacing when there are only two digits. It only looks good with three or more. (And then not too many.)
Still. It makes pretty pictures, which was mainly the point.
Go forth and spread beauty and light!