"Do the math!"- Sega 16-bit video game-set commercial, c. mid-1980's

A couple weeks ago on YouTube I stumbled upon an odd offering: Altes Multiplizieren - vergessenes Wissen! Das hast du noch nie gesehen! ("Old Multiplication -- Forgotten Knowledge. You have never seen that before!"). The video series is "Lernen mit Lehrer Schmidt" ("Learn with Teacher Schmidt") and appears to be math videos by a math teacher, though at his web site he also covers topics such as physics, German (grammar and literature), and handicrafts. They are of course in German without subtitles.Basically, the method is to iteratively double one number and halve the other (always rounding down), then adding together all the doubled numbers for which the corresponding halved numbers are odd. It looks very strange and I was about to try to figure it out with an algebraic proof when I saw a comment describe it as a binary operation. I immediately recognized it as the standard binary multiplication method I had learned decades ago for my computer science degree; I hadn't realized that because this one was using decimal numbers instead of binary ones. Now what he's doing makes perfect sense.

This method is certainly old. Most of the comments either said that they had never seen this before or else their grandparents had shown it to them (these were mainly middle-aged or senior themselves). What I'm still not sure of is whether this was indeed how everybody used to be taught in German schools and if this method was also used in other countries. We do know that binary mathematics go back to ancient India and Egypt, so it would make sense that a mathematician would have devised this method long ago. I have found this method described in Wikipedia as Russian Peasant Multiplication, the advantage being that you do not need to memorize multiplication tables but rather you only need to know how to multiply and divide by 2 and to add.

Since not everybody understands German, I'm writing this page to present the method in English. Then I describe binary multiplication to show how and why this works.

Here's the basic procedure:

- Write the numbers side by side with the smaller number on the left.
- Successively double the number on the right and halve the number on the left until the number on the left is one (1). When you halve an odd number, just drop the fraction (ie, round down).
- Cross out (ie, remove) all lines where the number on the left is even.
- Add all the remaining numbers on the right and you get the answer.
Here are the examples from the video:

- Set up the problems and do the doubling and halving:
5 × 25 4 × 35 3 × 25 5 × 35 7 × 45 6 × 40 7 × 21 12 × 31 5 -- 25 4 -- 35 3 -- 25 5 -- 35 7 -- 45 6 -- 40 7 -- 21 12 -- 31 2 -- 50 2 -- 70 1 -- 50 2 -- 70 3 -- 90 3 -- 80 3 -- 42 6 -- 62 1 -- 100 1 -- 140 1 -- 140 1 -- 180 1 -- 160 1 -- 84 3 -- 124 1 -- 248

- Eliminate the lines with an even number on the left by crossing out those lines:
5 × 25 4 × 35 3 × 25 5 × 35 7 × 45 6 × 40 7 × 21 12 × 31 5 -- 25~~4 -- 35~~3 -- 25 5 -- 35 7 -- 45~~6 -- 40~~7 -- 21~~12 -- 31~~~~2 -- 50~~~~2 -- 70~~1 -- 50~~2 -- 70~~3 -- 90 3 -- 80 3 -- 42~~6 -- 62~~1 -- 100 1 -- 140 1 -- 140 1 -- 180 1 -- 160 1 -- 84 3 -- 124 1 -- 248

- Add the remaining numbers on the right, which are the ones with an odd number on the left:
5 × 25 4 × 35 3 × 25 5 × 35 7 × 45 6 × 40 7 × 21 12 × 31 5 -- 25~~4 -- 35~~3 -- 25 5 -- 35 7 -- 45~~6 -- 40~~7 -- 21~~12 -- 31~~~~2 -- 50~~~~2 -- 70~~1 -- 50~~2 -- 70~~3 -- 90 3 -- 80 3 -- 42~~6 -- 62~~1 -- 100 1 -- 140 1 -- 140 1 -- 180 1 -- 160 1 -- 84 3 -- 124 1 -- 248 ----- ----- ---- ----- ----- ----- ----- ----- 125 140 75 175 315 240 147 372And so you can see that it works.

If your browser does not support the strikethrough tag that I used, then refer to this write-up as you watch the video, in which Lehrer Schmidt writes all this out, one problem at a time (yes, that really is how they write ones and sevens and nines). There you can see him crossing out the lines with an even number on the left and leaving those lines out of the addition step.

So how does it work? I was ready to try to work it out algebraically when I noticed an entry in the comments section that this was binary multiplication. It was about four decades ago and I forget whether it was while working on my computer science degree or before that while going through military technical training as an electronic computer systems repairman (more likely the latter) that we were taken through how a computer performs integer multiplication. Basically, that operation is a series of shifts and conditional adds, which I will discuss below.But first we need some background knowledge so that everyone can understand it.

Basic Number TheoryDon't be afraid. It's just simply how we do position-value numbers (which you just know as "numbers") and how that translates to other number bases (maybe the only new concept for you here). That was a most of the "New Math" in the mid-1960's when I had it in junior high summer school. I understood it completely right away, but then we spent weeks of monotonous busy work in order to drum it into us (Trivia note: in German student slang, a teacher is a "Pauker", a drum beater, because he drums the subject matter into your head).

We'll work first in decimal, AKA "Base 10" because it uses ten digits which range from 0 to 9. Those digits are placed into positions in the number which define their values. The other number bases work their numbers the same way as decimal, the difference being how many digits they use which will also change the positions' values.

For example, consider the number 1234, one thousand two hundred thirty four. Going from right to left, the positions are "the one's place", "the ten's place", "the hundred's place", and "the thousand's place". So to find the value of 1234, we take each digit, multiply it by its position's value, and finally add them all together. Therefore:

Yeah, it's that simple. And the New Math had us spend half the summer decomposing numbers and then performing basic arithmetic with those decomposed numbers. But it helps us to understand how to work with other number bases.1234 = 1 × 1,000 + 2 × 100 + 3 × 10 + 4 × 1 = 1,000 + 200 + 30 + 4Please note that the position values are based on the powers of the number of digits in the number base, which for decimal is 10:

That more general form is the key to creating numbers in other number bases. Since our goal here is working in binary, let's examine that.1 = 10Therefore:^{0}; 10 = 10^{1}; 100 = 10^{2}; 1,000 = 10^{3}1234 = 1 × 10^{3}+ 2 × 10^{2}+ 3 × 10^{1}+ 4 × 10^{0}= 4 + 30 + 200 + 1,000Binary, Base 2, has two digits, 1 and 0. The position values of a binary number are:

So if we take the binary number 00100111, we find that we have ones in the 32's place, the 4's place, the 2's place, and the 1's place. To convert that number to its decimal equivalent, we add the values of the ones: 32 + 4 + 2 + 1 = 39. I should also mention that with 8 bits (binary digits) you can express 256 (22^{0}= 1

2^{1}= 2

2^{2}= 4

2^{3}= 8

2^{4}= 16

2^{5}= 32

2^{6}= 64

2^{7}= 128

^{8}) values ranging from 0 to 255.I'll quickly mention two other bases that programmers have commonly worked with: octal (Base 8) and hexadecimal (Base 16). The reason why they are so common is because you can easily convert back and forth between them and binary. With three bits you can represent 8 digits (0 to 7) and with 4 bits you can represent 16 digits (0 to F). To convert from binary to octal or hexadecimal you group the bits by 3 or by 4, respectively, and simply read them. Every experienced programmer has the binary code for those digits memorized from repeated use. These two number bases are of no use in this discussion, but if you're interested in learning more about them then follow those links to their Wikipedia articles.

Long MultiplicationSince binary multiplication is derived from decimal long multiplication, we'll review decimal first.

Let's start with an example problem: 4,096 × 1,024 = 4,194,304 (yes, that's 2

^{12}× 2^{10}= 2^{22}; I am a programmer after all). We will need this terminology: 4,096 is the multiplicand, 1,024 is the multiplier, and 4,194,304 is the product.I will use the standard form that I learned in elementary school in the late 1950's. I'm qualifying this just in case they've changed how they teach it

^{1}, or in case you're from a country where it's done differently. So to examine that standard form, let's revert to the New Math approach of the mid-60's in order to see exactly what's happening:

- Decompose the multiplier and write the problem thus:
- product = 4,096 × (1,000 × 1 + 100 × 0 + 10 × 2 + 1 × 4)

- Applying the commutative property to the decomposed multiplier, we reorder its terms to the order we will use in long multiplication:
- product = 4,096 × (1 × 4 + 10 × 2 + 100 × 0 + 1,000 × 1)

- Now apply the distributive property:
- product = 4,096 × (1 × 4 + 10 × 2 + 100 × 0 + 1,000 × 1)

= (4,096 × 1 × 4) + (4,096 × 10 × 2) + (4,096 × 100 × 0) + (4,096 × 1,000 × 1)

- Of course, the terms being multiplied by zero will be zero and hence can just be dropped out:
- product = (4,096 × 1 × 4) + (4,096 × 10 × 2) + (4,096 × 1,000 × 1)

- Next, in each term we multiply the multiplicand by the indicated powers of ten, which is accomplished by shifting the multiplicand left one place per zero:
- product = (4,096 × 4) + (40,960 × 2) + (4,096,000 × 1)

- Now in each term we multiply the multiplicand by the multiplier's digits:
- product = (4,096 × 4) + (40,960 × 2) + (4,096,000 × 1)

product = 16,384 + 81,920 + 4,096,000

- And finally we add the terms together to get the product:
- product = 4,194,304
That is what we are doing in long multiplication. We will use this understanding to approach long multiplication in binary.

Now let's apply our understanding to the standard format (at least the one taught when I went through the program):

- Write the problem, leaving out those pesky commas:
4096 Multiplicand × 1024 Multiplier ---------

- Multiply the multiplier's 1's digit (4) to the multiplicand with zero shift (ie, × 10
^{0}): 4096 Multiplicand × 1024 Multiplier --------- 16384

- Multiply the multiplier's 10's digit (2) to the multiplicand with a left shift of 1 (ie, × 10
^{1}). Note that I am including the right-most zero in order to show that explicit multiplication by a power of ten, whereas we were taught to just shift it left and leave a blank: 4096 Multiplicand × 1024 Multiplier --------- 16384 81920

- Multiply the multiplier's 100's digit (0) to the multiplicand with a left shift of 2 (ie, × 10
^{2}). Since we're multiplying by zero, we do not write anything down. However, another left shift has occurred, which we will see in the next step. 4096 Multiplicand × 1024 Multiplier --------- 16384 81920

- Multiply the multiplier's 1,000's digit (1) to the multiplicand with a left shift of 3 (ie, × 10
^{3}): 4096 Multiplicand × 1024 Multiplier --------- 16384 81920 4096000

- Add the terms to get the product:
4096 Multiplicand × 1024 Multiplier --------- 16384 81920 4096000 --------- 4194304 ProductAnd just so that you can see it in a more familiar form, here is the final result with zeros replaced by blanks:

4096 Multiplicand × 1024 Multiplier --------- 16384 8192 4096 --------- 4194304 ProductNow as we move on to long multiplication in binary, we will see that it works the same way. However, there are a couple things that makes it much easier and which are reflected in this "Old Multiplication" method.

Footnote 1:In 1964 Tom Lehrer wrote his satirical song, New Math, for the US version of the TV weekly news satire, That Was The Week That Was (TW3). The song was released on Tom Lehrer's album, That Was The Year That Was, along with his other songs for TW3 and his performance of the song in concert is on YouTube.The premise of the song is that the changes in the New Math means that parents can no longer help their children with their homework, so he offers a quick lesson to bring the parents up to speed with a simple subtraction problem. After doing it in decimal (Base 10), he notices that the book asks that we do it in Base 8 (octal -- "Don't worry. Base 8 is just like Base 10 if you're missing two fingers.").

While working with that problem, he reveals an earlier case of a change in how borrowing in subtraction was done. I was taught to "borrow 1" (actually 10 because of position values) from the top digit immediately to the left. But (in 1964) if you're over 35 or went to a private school, you would add 1 to the bottom digit immediately to the left. My mother told me that that was how she was taught to do it. I have a 1914 arithmetic primer for grades 1 through 6 which uses that same technique.

Another example was when my older sister was learning algebra, so our father would help her with her homework. Then one day she brought home a note from her teacher asking our father to stop helping her because he was using different methods from what they were teaching.

Binary MultiplicationLong multiplication in binary works like long multiplication in decimal, except for two things:

- Since the place values are in powers of two, when you shift a binary number to the left, then you are multiplying it by 2. And when you shift to the right, you are dividing by 2. This fact ties in directly to the "Old Multiplication" method.

- The only things you will multiply the multiplicand by will be either zero or one. Multiplying anything by zero is always zero. Multiplying anything by one is always itself -- just keep in mind that for each iteration we will have shifted the multiplicand to the left.
That second item, that you're multiplying by only 0 or 1, both of which are trivial to do. That is one reason why Lehrer Schmidt's method is so easy to use.

Addition of two bits (A and B) can be represented by the following truth table:

A + B A B Sum Carry 0 0 0 0 0 1 1 0 1 0 1 0 1 1 0 1 Note the last line where you add 1 + 1 = 2, which in binary would be 10

_{2}, just as in decimal 5 + 5 = 10_{10}. In both cases, the sum in that position is zero with a 1 being carried to the next higher position.Since keeping track of carries can get messy in long-column addition in binary, I will modify the long-multiplication method slightly by performing an addition in each iteration, thus maintaining a running subtotal. This will also reflect how the integer multiplication algorithm is performed on a computer.

For our example, let's use one of Lehrer Schmidt's examples: 12 × 31. In binary, 12

_{10}= 1100_{2}and 31_{10}= 11111_{2}. For this example I will not show leading zeros, but in a computer those leading zeros will be there.

- Set up the problem:
1100_{2}× 11111_{2}11111 Multiplicand × 1100 Multiplier ---------

- Multiply the multiplier's 1's digit (0) to the multiplicand with zero shift (ie, × 2
^{0}) Since we're multiplying by zero, we do not write anything down. 11111 Multiplicand × 1100 Multiplier ---------

- Multiply the multiplier's 2's digit (0) to the multiplicand with a left shift of one (ie, × 2
^{1}) Since we're multiplying by zero, we do not write anything down. 11111 Multiplicand × 1100 Multiplier ---------

- Multiply the multiplier's 4's digit (1) to the multiplicand with a left shift of two (ie, × 2
^{2}) Since we're multiplying by one, write the shifted multiplicand down. Since it's the first term, do not add (nothing to add it to except zero). 11111 Multiplicand × 1100 Multiplier --------- 1111100

- Multiply the multiplier's 8's digit (1) to the multiplicand with a left shift of three (ie, × 2
^{3}) Since we're multiplying by one, write the shifted multiplicand down and add it to the previous term. 11111 Multiplicand × 1100 Multiplier --------- 1111100 11111000 --------- 101110100

- Since the remaining higher-order bits of the multiplier are all zero, the subtotal is the final sum and hence the product.
11111 Multiplicand × 1100 Multiplier --------- 1111100 11111000 --------- 101110100 Product 101110100_{2}= 372_{10}Refer to the description of Lehrer Schmidt's method and look at this problem, 12 × 31, and note:

- We get the same product, 372.

- Lehrer Schmidt's example ignored the first two multiplications (evens) and only uses the last two (odds), just as we just did.
So this demonstrates that Lehrer Schmidt's method is using binary multiplication. However, in order to more closely match what he's doing we need to look at how computers multiply integers.

How Computers MultiplyOne of the techniques that programmers use is to "play computer" with pencil and paper. That is to say that we will test an algorithm or code function by stepping through the algorithm/code writing down the values of all the variables and examining the results. That is basically what Lehrer Schmidt is doing in his method. And I will do the same here.

Here is a highly simplified explanation of how computers work. In general (ie, actual mileage may vary in some specialized hardware):

- Every computer has at least one CPU (central processing unit), the actual "brain" of the computer which performs every instruction in a program.

- Every CPU has at least one ALU (arithmetic logic unit) which performs a set of binary integer arithmetic and logic operations on binary values input into it.

- Every CPU also has a number of registers. A register is hardware circuitry which contains a binary number of a number of bits specified by the computer design (eg, 8 bits, 16 bits, 32 bits, 64 bits -- notice how they tend to follow the powers of two, though many older designs had other word sizes; IOW, although there are conventions based on valid reasons, the design is also arbitrary).
The binary numbers contained in a register can be used as integer values, parts of a floating-point value (though there's also hardware that some computers have hardware to support floating-point values and operations, floating-point units (FPUs), or else they will emulate an FPU in software), a memory address containing data, a memory address containing a memory address containing data, etc ad infinitum (constrained by practical hardware and software limitations), character data, status flags, special data formats, etc. A particular pattern of bits has no inherent properties to tell you what they represent. Bits are bits. The significance of a particular grouping of bits depends entirely on how the software uses those bits. Admittedly, this very important point has no direct bearing on the subject of this page, but it is an important computer science point anyway.

Depending on the CPU's architecture, certain registers can be given special purposes as well as special operations. One of the purposes important to our discussion is the ability to shift left (ie, multiply by two) or right (ie, divide by two). Some CPUs will have general purpose registers capable of shifting, whereas other would need to do something like using the ALU to do that. Basically, every CPU architecture is unique, so compilers for those architectures will need to be written to take that into account in order to get the same results at the higher level. Almost all of that ends up being transparent to all users and programmers.

In some architectures, two registers can be linked together to logically form a single register twice the normal length. For example, multiplying two registers of standard size will result in a product that could be at least twice the size of either the multiplicand or the multiplier. In such cases for the multiplication algorithm (see immediately below), the "register" allocated to contain the product could instead be a pair of registers containing the higher- and lower-order bits of the product. In some architectures, the instruction set can take that into account, whereas in other you have to take care of that yourself. Same outcome, but different means of getting there.

Also, some registers have special functions and some functions have more functionality than others. For example, one, the instruction pointer, always contains the address of the next instruction to be executed. The Memory Address Register is loaded with the memory address to be access. Some more complex instructions require certain registers to be loaded with the parameters that it needs. And there is one very special general purpose register, the accumulator (almost always Register A), which supports all possible arithmetic and logical operations, including shifting. We will use the accumulator below.

- Every CPU supports an instruction set, a set of individual operations that the CPU can perform. In my technician training with the COM-TRAN TEN trainer (used both by the US Air Force and US Navy around the late 70's), we "chased sparks" through the logic diagrams representing the hardware in those computers, seeing how every individual instruction was implemented in that computer. Those instructions include (but not limited to) moving data from register to register, from register to memory, from memory to register, from register to I/O device (which contains its own registers), from I/O device to register, from memory to I/O device, from memory location to memory location, etc. Those instructions also include arithmetic and logic operations on a single register or between any combination of registers and memory locations (possible permutations depending on individual instruction sets) -- that includes setting to zero, AND'ing, OR'ing, XOR'ing, shifting left or right, incrementing, decrementing, negating, adding, subtracting, multiplying, dividing (older, less powerful processors wouldn't have multiply or divide instructions but rather that had to be emulated in software). Those instructions also include performing a number of tests on status or individual bits in a register and jumping to another location in the program depending on that test.
And so on, all depending on the instruction set and CPU architecture, which varies from one processor to the next, though different processors within the same processor family tries to maintain some degree of compatibility. When you have an Apple app (on a Motorola processor, though that knowledge could be outdated) and try to load and run it on a Windows box (Intel, an entirely different processor), that could not possibly work because those two processor families have entirely different instruction sets -- did I forget to mention that every instruction has a binary numeric op-code value which varies between processors? Then pile on top of all that the necessary differences between operating systems (eg, a Linux executable will not run on Windows even though they usually use the same Intel processor family), but the point is that the choice of CPUs is the first barrier.

- All computer programs that have ever been written have been translated down to a sequence of CPU instructions. The translation of extremely high-level programs down to a sequence of individual CPU instructions can be mind-bogglingly complex, but it does still happen none-the-less.

So from the perspective of CPU instructions and registers, here is the algorithm for performing integer multiplication:

- Load two shift registers with the multiplier and multiplicand and zero out a third register, an accumulator, which will end up containing the product.
- If the multiplier is zero, exit. The product is in the accumulator.
- Test the least significant bit (LSB) of the multiplier. If the LSB is a 1, then add the multiplicand to the accumulator.
- Shift the multiplicand left by 1 (double it) and shift the multiplier right by 1 (halve it).
- Goto Step 2.
Did I forget to define even and odd numbers? Algebraically, an even number is 2n while an odd number is 2n+1. In a binary number, if the least significant bit (LSB) is a zero, then the number is even, but if the LSB is a one then the number is odd.

Now let's play computer!This is what I have done repeatedly for the four decades of my computer engineering training and career.First, let's assign values to registers. If we were doing this in a higher-level language, these would be variables -- for the last few decades of my career, I mostly worked in C, which occupies a gray zone between higher- and lower-level languages, a comfortable place for a traditional programmer to be in.

Let's set up three registers/variables: the multiplier, the multiplicand, and the accumulator as referred to in the algorithm specified directly above. The accumulator (to which the shifted multiplicand will be added as per the algorithm and which will end up containing the product). We will load the multiplier value into the multiplier, the multiplicand into the multiplicand, and zero into the accumulator. Also note that, if registers are used, the multiplier and multiplicand registers must support shifting.

Our example will be one of Lehrer Schmidt's examples: 5 × 25 → 101

_{2}× 11001_{2}:5 × 25 --> 101_{2}× 11001_{2}multiplier multiplicand accumulator 0101 11001 0 Load the registers. 0101 11001 11001 Shift. LSB is 1 (ie, line is odd) so add to the accumulator. 0010 110010 11001 Shift. LSB is 0 (ie, line is even) so do not add to the accumulator. 0001 1100100 1111101 Shift. LSB is 1 (ie, line is odd) so add to the accumulator. 0000 11001000 1111101 multiplier is zero, so exit. Product is in the accumulator. 1111101_{2}= 125_{10}Here's another example, the one we did binary long multiplication one above, 4 × 35:

4 × 35 --> 1100_{2}× 11111_{2}multiplier multiplicand accumulator 1100 11111 0 Initialize the registers. 1100 11111 0 Shift. LSB is 0 (ie, line is even) so do not add to the accumulator. 0110 111110 0 Shift. LSB is 0 (ie, line is even) so do not add to the accumulator. 0011 1111100 1111100 Shift. LSB is 1 (ie, line is odd) so add to the accumulator 0001 11111000 101110100 Shift. LSB is 1 (ie, line is odd) so add to the accumulator 0000 11111000 101110100 multiplier is zero, so exit. Product is in the accumulator. 101110100_{2}= 372_{10}

That is what Lehrer Schmidt is doing in his video, except he keeps the values in their decimal form instead going straight to binary. Decimal numbers still retain their binary properties; you just cannot see that.

Here's a simple implementation of the binary multiplication algorithm in a higher-level language, C. Note that I have not tested it for negative numbers (which would be represented with two's complement, but I've taxed your brain too much already).

long multiply(int multiplicand, int multiplier) { long acc = 0L; // declare accumulator and initialize it to zero // ensure that multiplicand is non-zero if (multiplicand) { while (multiplier) // loop while multiplier is not zero { // in all tests, zero == false, non-zero == true if (multiplier & 1) // perform AND to test LSB. { // if LSB is 1, then multiplier is odd acc += multiplicand; // add multiplicand to the accumulator } multiplicand <<= 1; // double multiplicand; shift left by one multiplier >>= 1; // halve multiplier; shift right by one } } return acc; }This code is provided solely for educational purposes and should not be used in commercial products. Besides, C fully supports multiplication and division. This kind of code would only be needed for emulating multiplication in assembly programs for processors that do have a multiply instructions, but in that case you should be using a third-party math emulation package.

Return to DWise1's Home Page

*Share and enjoy!*

*First uploaded on 2019 September 27.
*

*
*