A Different Kind of Multiplication

      It is often said that an important advantage of the decimal notation over the Roman one is that makes multiplication of numbers much easier. Adding CLXXVII to XXIII may be relatively straightforward--but how about multiplying the two?

    It is indeed easier to multiply these as decimal numbers 177 by 23, but the Romans also had a multiplication method of their own. It was probably discovered by trial and error, and it always worked, though the Romans did not know why.

    Here the method is described, and its secret explained. The Romans started by writing the numbers next to each other. Of course, they used Roman numerals--but to make it clear in what follows, here decimal notation will be used throughout. Suppose we need to derive

    After writing down the numbers (here the multiplication sign was added), halve the first one and double the second, writing the new numbers below the preceding ones. If the number being halved is odd, just ignore the remainder. Repeat this operation as long as you can:

    Now cross out in the second column all numbers where the corresponding number in the first column is even:

    Then add up the remaining numbers:

    You can verify that indeed 177 x 23 = 4071. The Romans did all this using their own cumbersome notation, but people used to handling numbers were experienced in doubling and halving, and could carry it out fairly quickly. Doubling can be relatively simple: XXIII doubled is XXXXVI, doubled again DXXXXII (Romans wrote 4=IIII,40=XXXX, and notations like 4=IV were only introduced in the middle ages). Like the method we use, it reduced the multiplication of two numbers to addition, which Roman numerals could handle.

But why did it work?

    To find the reason, one must express the numbers in the first column in binary notation--as a sum of powers of 2. The powers 2^N for N=0,1,2,3,4... are

    Every number can be written in just one way as the sum of powers of two. In this case

    When a number is written in binary notation, each digit represents one power of 2. Reading from right to left, a digit is 0 if that power of 2 is absent in the number, 1 if it is present. It can only be present once: if twice or more, a higher power of 2 could be used. This is very similar to the way we write decimal numbers: the digits of 177 tell us that 10⁰=1 is present 7 times, 10¹=10 is also present 7 times, and 10²=100 is present once. Since

    we have in binary notation

    The last digit of any binary number is 1 if it is odd, 0 if even. Lopping off that number creates a new binary number, with two properties:

1. The same binary number is produced for any odd number and the even number just below it, e.g.
   177 = 1011 0001 and 176 = 1011 0000 both give 1011 000 = 88
   
2. In the new number, each digit is demoted one binary level:
         the "2" digit in the original number becomes the "1" digit,
         the "4" digit becomes the "2" digit
         the "8" digit becomes the "4" digit
         the "16" digit becomes the "8" digit
   and so forth. That means,
         If the old number is even, the new number is half its value (no remainder)
         If the old number is odd, the new number is half its value (ignore remainder)

    Thus when we "divide by 2 and ignore the remainder" we end up with the number whose binary representation is obtained by lopping off the last binary digit. Let us rewrite the earlier table, but add binary representations, and for convenience, shift to the right entries which have even multiples of 23 and which in binary notation end in 0:

    Note whenever the left-hand number is odd, the last digit is 1. By singling out the odd numbers on the left, we identify the non-zero digits in the binary expansion!

    Now, how do we multiply two numbers in the decimal system, , say 177 by 23?

    The digits of 177 tell us that it contains 7 "ones", 7 "tens" and one "hundred":

    Therefore

    or else

    or else

    This reduces a complicated multiplication to a series of simple multiplications, followed by a simple addition.

    In the binary system, 10, 100, 1000, 10000... are powers of 2

    and so forth. To use a similar strategy for multiplying

    (for clarity, we use decimals to write 23), for every digit "1" in 1011 0001 we multiply 23 by the corresponding power of 2, and then add the result. 1011 0001 contains "1" four times, so we expect to add 4 powers of 2. Earlier we showed that

    and each "1" in 1011 0001 corresponds to one of those powers. To start from the smallest power (as in the above sum) we must look at the digits from left to right. The first "1" corresponds to "1" which is the same in binary or decimal. The next "1" shows that 177 contains (once) 10000 (binary) = 16 (decimal), and so on.

    The right hand column of our table, where 23 is doubled and redoubled, contains the number 23 times all powers of 2 = 1,2,4,8... . By adding there the numbers corresponding to the "1" digits of 177 = 1011 0001, we sum up the product of 23 by only those powers of 2, contained in 177. The result therefore equals 177 x 23.

    The Romans did not know anything about the binary system. They just knew that their method worked, which was good enough for them. Interestingly, electronic computers, which use binary numbers, employ a similar method!

Note