"Do the math!" - Sega 16-bit video game-set commercial, c. mid-1980's
Recently (September 2019) 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" ("Learning with Teacher Schmidt") and consists mainly of math videos by a math teacher in Germany, though at his web site he also covers topics such as physics, German (grammar and literature), education, and handicrafts. They are of course in German without subtitles.I work through it below, but basically the method is to iteratively double one number and halve the other (always rounding down, AKA truncating), then adding together all the numbers in the doubled column for which the corresponding halved numbers are odd. At first 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. With that I immediately recognized it as the standard binary multiplication method I had learned decades ago either in USAF tech school or for my computer science degree; I hadn't recognized it because he uses 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 seniors themselves, so their grandparents had to have learned it in the late 1800's). 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, how to add, and how to tell whether a number is odd or even.
Since for some odd reason not everybody understands German, I'm writing this page to present Lehrer Schmidt's method in English. Then I describe binary multiplication to show how and why this works.
2020 Feb 05
The Numberphile channel on YouTube just uploaded a video, Russian Multiplication featuring Johnny Ball, a British television personality and mathematics popularizer. This video will provide you an explanation and demonstration in English.His addition to the narrative ties the procedure to the "Russian" part of the name. When he was shown the procedure as a boy, the adult made joking references to Stalin's infamous purges. To explain dropping the fraction when you divide an odd number by 2, he was told that the Russians hated fractions so they'd purge them out. And to explain eliminating the lines with the even number on the left, then the Russians hated even numbers on the left and so the entire line would be purged. Makes for a colorful story to help a child remember the procedure without asking for the real reason why, which I will explain at length below.
Johnny Ball also fills in a bit more of the history of this technique. He pointed out that it's not restricted to Russian peasants, but rather has been used by peasants of all nationalities, especially where sufficient education to learn multiplication was not available. He has traced it back to Elizabethan England and even further back to ancient Egypt. The Egyptian procedure is a bit different, but he goes through it as well.
2022 Jan 30
I just saw a History Matters video on YouTube, Why does the west use Arabic Numerals? (Short Animated Documentary), which includes an application of this multiplication method to Roman numerals: XIII × XIII.I added a new section, The Method Applied to Roman Numerals, to discuss this idea.
Here are the examples from the video:
And so you see that it does work.
Now to discover why.
BTW, 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 in Germany).
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.
To illustrate that point, the video launches into an example of multiplying two Roman numerals together, XIII × XIII using our "Old German Multiplication Method" (AKA "Russian Peasant Multiplication").
The video does not actually claim that this method was used to multiply Roman numerals together, but a similiar method was reportedly used in ancient Egypt, so it's a possibility.
Also, Google'ing on Roman numeral multiplication yielded links and quick answers which all (at least the ones I checked) point to the Romans having used this method.
In order to double, halve, and add Roman numerals, it's easier to just convert to Arabic, perform the arithmetic, then convert back.
However with a little practice I devised my own methods of doing it in Roman numerals without having to convert.
I won't bother you by attempting to explain what I did, but it's very much like what's described on this page,
How to Multiply Roman Numerals -- I'm certain that you can find many similar pages on Roman numeral arithmetic through your own searches.
HINT: Before doing the arithmetic, convert subtractive notation to straight counts of four symbols; eg, XL → XXXX, IV → IIII. That way you won't need to try to juggle all that in your head but rather you just double the symbols and then group them together in the final step; eg:
Also, keep in mind that a digit's value depends on its position in Arabic numerals, but not in Roman numerals --
except for in subtractive notation (eg, XL, IV) which is why you should remove subtractive notation before doing arithmetic in Roman numerals (eg, XL → XXXX, IV → IIII).
Think of a Roman numeral as a pile of money of different denominations: it doesn't matter in what order you stack the bills or coins, the value will still add up to the same amount. Stacking your money in order of descending denomination just makes it easier to count.
So, redoing a few of the examples above as Roman numerals plus recreating the video's example (XIII × XIII):
But first we need some background knowledge so that everyone can understand it.
Basic Number Theory
Don'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).
This basic number theory was most of the "New Math" in the mid-1960's when I had it in junior high summer school.
I understood it completely within the first hour of instruction, 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 -- though now apparently when a student studies hard, "hitting the books", that's also "pauken" ("beating a drum")).
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" (sound familiar?).
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:
Please note that the position values are based on the powers of the number of digits in the number base, which for decimal is 10:
Binary, Base 2, has two digits, 1 and 0. The position values of a binary number are:
That's what we end up doing, but what are we actually doing?
We are actually placing the digits in their positions and multiplying each digit to its place value.
That is exactly what we do in decimal:
001001112 = 39
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), which by definition is octal, and with 4 bits you can represent 16 digits (0 to F), which by definition is hexadecimal.
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, since we almost always use either octal or hex to work with binary values (hexadecimal, AKA "hex", is most commonly used at present).
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 Multiplication
Since understanding binary multiplication by doing it by hand 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 is 212 × 210 = 222; I am a programmer after all, so nice round numbers like these powers of two come immediately to mind).
We will need standard mathematical terminology for multiplication:
I will use the standard form that I learned in elementary school in the late 1950's in the USA.
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 taught 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.
So then rather pedantically:
HINT: to multiply by a power of ten, you shift the multiplicand left that number of times; eg, to multiply by 100 (102) you shift left by two places (AKA adding two zeros on the right end).
That is what we are doing in long multiplication albeit described in a pedantic New-Math approach.
We will use this understanding to approach long multiplication in binary.
But in the meantime, let's now apply our understanding to the standard format we're all familiar with (at least the one taught when I went through the program). As we do this, use the treatment above to understand what's behind our actions in the standard format:
And just so that you can see it in a more familiar form, here is the final result with zeros replaced by blanks:
Now as we move on to long multiplication in binary, we will see that it works in the exact same way.
However, there are a couple things that makes it much easier and which are reflected in this "Old Multiplication" method.
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 my mother had been taught.
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 Multiplication
Long multiplication in binary works like long multiplication in decimal, except for two things:
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.
These two unique characteristics of binary multiplication is why computer students and professionals describe it as "Shift-and-add".
I will demonstrate this below.
So how do you add in binary?
Basically the same way as you do in decimal: starting at the one's place you add each pair of digits and, if that results in a two-digit sum, then you carry that higher-order digit to the next column and add it to that pair.
For example, 1 + 1 is 2, which is a two-digit value in binary (ie, 102) so you carry it to next higher column.
Addition of two bits (A and B) can be represented by the following truth table:
Note the last line where you add 1 + 1 = 2, which in binary would be 102, just as in decimal 5 + 5 = 1010.
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, 1210 = 11002 and 3110 = 111112.
For this example I will not show leading zeros, but, since a computer's registers are of a fixed length, in a computer those leading zeros will be there. The example:
Refer to the description of Lehrer Schmidt's method and look at this problem, 12 × 31, and note:
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.
This is one of the simplest ways to explain how computers work:
The sidebar to the right is a very brief, very simplified explanation of how computers work. This will help you understand the following explanation of how they multiply.
One of a programmer's common techniques in designing or debugging code 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 as the code changes them and examining the results.
That is basically what Lehrer Schmidt is doing in his method.
And I will do the same here.
From the perspective of CPU instructions and registers, here is the algorithm for performing integer multiplication:
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 (ie, a zero in the 1's place), then the number is even, but if the LSB is a one (ie, a one in the 1's place) then the number is odd.
The LSB is the bit that we're multiplying the shifted multiplicand by, so if the LSB is a one then we multiply by 1 and add the result to the accumulator, but if the LSB is zero then we add zero to the accumulator.
Now let's play computer! This is what I have done so very many times 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 environment for a traditional programmer.
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 → 1012 × 110012:
Here's another example, the one we did binary long multiplication one above, 12 × 31:
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 them.
This code is provided solely for educational purposes and should not be used in commercial products.
Besides, C fully supports multiplication and division (both integer and floating-point, though which is used depends on the data types of the numbers so you need to keep that in mind).
This kind of code would only be needed for emulating multiplication in assembly programs for processors that do not have multiply instructions, but in that case you should be using a third-party math emulation package for commercial products.
Share and enjoy!
First uploaded on 2019 September 27.
The Method
Here's the basic procedure presented in the video:
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
Please note that the first line contains the numbers in the statement of the problem.
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
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 372
The Method Applied to Roman Numerals
There's a video on YouTube, Why does the west use Arabic Numerals? (Short Animated Documentary) by History Matters, which summarizes the history of how Europe switched from Roman numerals to our current system using Arabic numerals (actually of Hindu origin and transmitted to us by the Muslims).
One of the themes of that video, besides resistance to the change for political and religious reasons, was how difficult it was to perform calculations with Roman numerals and how the greater ease and efficiency of doing the math with Arabic numerals won over the banking families (eg, the Medici).
double LXXX → LLXXXXXX → CLX
Use grouping symbols if that helps; eg (XXXXX)XXX → LXXX, CLX(IIIII)IIII → CLX(VIIII) → CLXIX.
double XL → double XXXX → XXXXXXXX → LXXX
double XIII → XXIIIIII → XXVI
double XXVI → XXXXVVII → XXXXXII → LII
add XIII + LII + CIV → XIII + LII + CIIII → XIIILIICIIII → CLXVIIII → CLXIX
4 × 35 5 × 35 6 × 40 12 × 31 13 × 13
IV × XXXV V × XXXV VI × XL XII × XXXI XIII × XIII
IV -- XXXV V -- XXXV VI -- XL XII -- XXXI XIII -- XIII
II -- LXX II -- LXX III -- LXXX VI -- LXII VI -- XXVI
I -- CXL I -- CXL I -- CLX III -- CXXIV III -- LII
I -- CCXLVIII I -- CIV
Please note that the first line contains the numbers in the statement of the problem.
4 × 35 5 × 35 6 × 40 12 × 31 13 × 13
IV × XXXV V × XXXV VI × XL XII × XXXI XIII × XIII
IV -- XXXV V -- XXXV VI -- XL XII -- XXXI XIII -- XIII
II -- LXX II -- LXX III -- LXXX VI -- LXII VI -- XXVI
I -- CXL I -- CXL I -- CLX III -- CXXIV III -- LII
I -- CCXLVIII I -- CIV
4 × 35 5 × 35 6 × 40 12 × 31 13 × 13
IV × XXXV V × XXXV VI × XL XII × XXXI XIII × XIII
XIII
XXXV LXXX CXXIV LII
+ CXL + CXL + CLX + CCXLVIII + CIV
----- ----- ------ ---------- -------
CXL CLXXV CCXL CCCLXXII CLXIX
140 175 240 372 169
How It Works (Multiplying in Binary)
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.
About four decades ago I went through USAF tech school in computer systems repair (AFSC305x4, Electronics Computer Systems Repairman) and then I worked on my computer science degree.
In one of those experiences (I forget which, but my memory's leaning towards tech school), we went through how a computer performs integer multiplication.
Basically, that operation is a series of shifts and conditional adds, which I will discuss below.
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 + 4
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 = 100; 10 = 101; 100 = 102; 1,000 = 103
Therefore:
1234 = 1 × 103 + 2 × 102 + 3 × 101 + 4 × 100 = 1,000 + 200 + 30 + 4
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 (28) values ranging from 0 to 255.
20 = 1
21 = 2
22 = 4
23 = 8
24 = 16
25 = 32
26 = 64
27 = 128
This demonstrates a unique characteristic of working with binary numbers.
The values of the digits (AKA "binary digits", AKA "bits") are one of two values: 1 or 0.
So when you multiply a digit to its position value, then you are multiplying by 1 or by zero.
One times any number is that number (eg, 1 × 42 = 42) and zero times any number is zero.
So to find the value of a binary number you do not need to actually do any multiplying, but rather all you need to do is see which positions contain ones and simply add all such position values together.
Not only is it very simple, but that same unique characteristic of working in binary will come into play in binary multiplication.
001001112 = 0 × 27 + 0 × 26 + 1 × 25 + 0 × 24 + 0 × 23 + 1 × 22 + 1 × 21 + 1 × 20
= 0 + 0 + 25 + 0 + 0 + 22 + 21 + 20
= 32 + 4 + 2 + 1
= (4,096 × 100 × 4) + (4,096 × 101 × 2) + (4,096 × 102 × 0) + (4,096 × 103 × 1)
product = 16,384 + 81,920 + 4,096,000
4096 Multiplicand
× 1024 Multiplier
---------
4096 Multiplicand
× 1024 Multiplier
---------
16384
4096 Multiplicand
× 1024 Multiplier
---------
16384
81920
4096 Multiplicand
× 1024 Multiplier
---------
16384
81920
Of course, we're taught to just skip that step when the multiplier's digit is zero, but in reality we are actually multiplying the multiplicand by zero, which is zero, and add that to the intermediate results, which does not change them.
So we're effectively skipping that step, but we need to keep in mind what's actually happening, the reason why we're effectively skipping that step.
4096 Multiplicand
× 1024 Multiplier
---------
16384
81920
4096000
4096 Multiplicand
× 1024 Multiplier
---------
16384
81920
4096000
---------
4194304 Product
4096 Multiplicand
× 1024 Multiplier
---------
16384
8192
4096
---------
4194304 Product
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.
A + B A B Sum Carry 0 0 0 0 0 1 1 0 1 0 1 0 1 1 0 1
11002 × 111112
11111 Multiplicand
× 1100 Multiplier
---------
11111 Multiplicand
× 1100 Multiplier
---------
11111 Multiplicand
× 1100 Multiplier
---------
11111 Multiplicand
× 1100 Multiplier
---------
1111100
11111 Multiplicand
× 1100 Multiplier
---------
1111100
11111000
---------
101110100
11111 Multiplicand
× 1100 Multiplier
---------
1111100
11111000
---------
101110100 Product
1011101002 = 37210
How Computers Multiply
5 × 25 ⟶ 1012 × 110012
multiplier multiplicand accumulator
0101 11001 0 Load the registers.
0101 11001 11001 First test. LSB is 1 (ie, line is odd) so add multiplicand to the accumulator.
0010 110010 11001 Shift and test. LSB is 0 (ie, line is even) so add nothing to the accumulator.
0001 1100100 1111101 Shift and test. LSB is 1 (ie, line is odd) so add shifted multiplicand to the accumulator.
0000 11001000 1111101 Shift and test. Multiplier is zero, so exit. Product is in the accumulator.
11111012 = 12510
12 × 31 ⟶ 11002 × 111112
multiplier multiplicand accumulator
1100 11111 0 Initialize the registers.
1100 11111 0 First test. LSB is 0 (ie, line is even) so add nothing to the accumulator.
0110 111110 0 Shift and test. LSB is 0 (ie, line is even) so add nothing to the accumulator.
0011 1111100 1111100 Shift and test. LSB is 1 (ie, line is odd) so add shifted multiplicand to the accumulator
0001 11111000 101110100 Shift and test. LSB is 1 (ie, line is odd) so add shifted multiplicand to the accumulator
0000 11111000 101110100 Shift and test. Multiplier is zero, so exit. Product is in the accumulator.
1011101002 = 37210
The Multiplication Algorithm in C
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(short multiplicand, short multiplier)
{
long acc = 0L; // declare accumulator and initialize it to zero
// test that multiplicand is non-zero
// if multiplicand is zero, then the product will be 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
}
// Note: all values are actually in binary, so shifting is also in binary
multiplicand <<= 1; // double multiplicand; shift left by one
multiplier >>= 1; // halve multiplier; shift right by one
}
}
return acc;
}
Return to DWise1's Home Page
Updated on 2020 September 18.