Hacking Multiplication: Binary Multiply On Paper

We’ve often noted that whether had ancient man known binary, we could all count to 1023 on our fingers. We thought about that while watching [Numberphile’s] latest video about “Russian” multiplication (see below). Apparently, the method dates back quite a way, sometimes known as Ethiopian or peasant multiplication. Even the ancient Egyptians did a form of it.

If you’ve ever written long multiplication code for a microcontroller, you can probably tell how this works. Each halving of the number amounts to a right shift. Each doubling is a left shift. Throwing out the even numbers means you only take the values when the least-significant bit is zero. Booth’s algorithm is more efficient, but the “Russian” method is simple to do on paper.

The main difference between the Russian and Egyptian methods is if you start with one of the multiplicands (Russian) or start with 1 and work your way up (Egyptian). Either way, you ought to start with the smallest multiplicand.

For example, suppose you have 321 x 17. You would pick 17 since it is smaller and halve it to form the left side of your table. Throw away any halves as those are bits shifting off the right-hand side. The right side of the table starts with the other number (321) and doubles on each row. So:

17     321
 8     642
 4    1284
 2    2568
 1    5136

The rows for 8, 4, and 2 are even, so they represent multiply by zero in the long multiplication. You can cross them out. That leaves the row for 17 and 1. Adding those up, you get 5457, the correct answer.

If you want to see the binary case, consider 9×3, which we know is 27 and using the Russian method works out to 9+18. In binary, we would say:

    1001
x   0011
-----------
 000000
  000000
   10010 (18)
    1001  (9)
-------------
 0011011 (27)

Oddly, this is only one way the Egyptians knew how to calculate. Some of how they dealt with fractions was not completely understood until 2002.

This is a great example of how a rote method works, even if you don’t understand why, but it is better if you do understand. Of course, these days, we can just ask a computer.

m

12 thoughts on “Hacking Multiplication: Binary Multiply On Paper

  1. Nice post thanks, reminds me of an alternate CPU binary coding to avoid or perhaps mostly minimise recurring decimal equivalents like 1/3 etc in binary representations and with modern FPGA these days or even custom silicon can be encoded efficiently and with minimal impact on processing speed whilst avoiding many types of carry through round off errors causing outright incorrect results !

    Fwiw.
    In respect of hand-binary as the post touched on, counting to 31 on one hand & 1023 on two hands.
    I studied food chemistry post grad in 2010 along with informal review of the anthropology of eating implements. It came to light the rapid rise in civilization in terms of abstract math and more complex planning started soon after in (and well correlated also) in Europe and Mediterranean widespread use of copper bowls for cooking and storage With the conjunction of natural aspirin (bark of willow tree) And greater population mobility. Correlation qualified by the causal factor being the NMDA neural receptors reliance on copper for brain function. The chemicals influencing improved cognitive function likely also moderated by genetics. The earliest Babylonians seemed the best adapted to those mineral loaded foods and I understand exploited the hand-binary method to trade in busy markets with their hands in the air as well as calculating taxes on land. Much like the pre computer share market floor traders which had their own set of finger codings but, used hands in the air to signal offers. Its evident most far below homeostasis for copper on western diets and one wonders how much short attention span and other long term cognitive deficits tied with deficiencies of the 150 enzymes that need copper in humans as it’s also evident they compete for absorption…

    I wonder if successful floor traders of years gone by were lines of descendants of Barking Babylonian Brokers ;-)

    1. Try reversing this algorithm. To divide N by D, start by left shifting D until it’s bigger than N.
      Then left shift, and subtract. until you are below N, or you shift to zero.
      If your value drops below N again, go back to adding.

      1. it is:
        1) Leftshift D so that it is just smaller than N.
        2 Now subtract D (shifted) and note a 1.
        3 Next shift D back to the right.
        4 If this is bigger than what’s left of N, note a zero and go back to shifting D (step 3)
        5 if it is not bigger go to step 2.

    2. The way I did multiplication on a CPU was exactly the way I was taught to do same at school in pre-calculator days except binary instead of decimal.

      I was taught division like a successive approximation method that didn’t code well for binary.

      Instead, for binary (integer) division I just reversed one Boolean shift direction and use substrate instead of add.

Leave a Reply

Please be kind and respectful to help make the comments section excellent. (Comment Policy)

This site uses Akismet to reduce spam. Learn how your comment data is processed.