On paper

Comba's method is an optimization for performing multiplication on a computer using the same "long multiplication" method that would be performed with pencil and paper. In a paper in the IBM Systems Journal in 1990, Paul G. Comba observed that most programmers would implement multiple precision arithmetic following the established patterns of manual calculation, but these were not necessarily optimal for a computer. He suggested a rearrangement of the calculations which, since they apply to the pencil and paper method, we can demonstrate in the same way.

Suppose we are multiplying 23 by 89. Then the standard method gives

    2 3
x   8 9
=======
  2_0_7
1_8_4
=======
2_0 4 7
where the underscore character denotes a carry from one digit position to the next. Comba made the observation that this order of calculation produced far too many carries from one digit position to the next, and it was computationally expensive, requiring extra instructions and registers. In this example, it makes little sense for there to be 5 carries, when the final result only has 4 digits.

Reversing the order of the operands does not help:

    8 9
x   2 3
=======
  2_6_7
1_7_8
=======
2_0_4 7
- in fact, the situation appears worse, requiring 6 carry operations. This may appear something of a paradox, that the order of inputs should affect the execution time. A good method should perform equally well, no matter which order the inputs are supplied.

Comba observed that the carries in the intermediate results were effectively wastes of computation, since carries could be produced in the final addition in any case. The first improvement then is to ignore the carries in these intermediate results, and deal with them at the end. Ignoring the carries though comes at a cost; the intermediate results may now have two digits in each column:

         2  3
x        8  9
  ===========
        18 27
     16 24
  ===========
   2 _0 _4 _7
However, the apparent paradox is resolved. It now does not matter which order the question is asked, the intermediate results are the same, each a product of single digits. Furthermore, all the carries from column to column are performed in the end result - although it costs extra width in the columns (which now may conceal some 'internal' carries. These should only be a bother for us humans, not for a computer).

In the computer

This subheading is offered as an invitation to start skimming.

The next trick that Comba applied was to minimize the number of memory writes when the computer performed this calculation. If the calculation was performed in row order, as is typical on pencil and paper, some storage needed to be allocated to store the intermediate results. Instead, the computer should be instructed to compute the products, column by column, and keep the results in registers. The only time a digit is written to memory is at the bottom of each column, and it is a final result in the answer. The carry into the next column remains in registers.

While the theory behind this approach appeared good, there were a couple of technical issues to resolve. One was, with all this carry propagation left to the last moment, the carry itself could get quite large. This may not show in this 2-digit example, but what about when multiplying two 13-digit numbers? In that case, each column could be as deep as 13 lines, and each number in the column could be as large as 81, so the sum could be as large as 1053 - the carry could be as large as three digits wide. Comba's approach was to allow more registers for the carry, and only consider those extra registers in the later digits summed over each column.

Getting the additional registers came as a side-effect of the solution to the second technical issue. This method requires some subtlety on a computer, because not all the columns have the same number of partial results. The conventional method used two nested loops and did not have to consider this, every row in the partial results was the same length. Comba's resolution to this issue was a common optimization for loops; simply unroll them. Instead of looping over the same code again and again, make enough duplicate copies of the code, one after the other. A routine that was originally only about a dozen bytes in length could suddenly unroll to be several KB in size, and there may even have to be a different routine for every length of input number. However, it could all be programmed quite quickly with assembler macros, and all the difficulties could be addressed - each digit combination could in effect have its own code if needed, to squeeze every last drop of optimization out of the routine. There were no longer any loop counters because there were no loops - the registers saved could address the carry issue.

How good is it?

Comba's measurements on an 8086 processor showed his optimizations were a significant 30% faster than the "obvious" approach. However, much of this gain had a lot to do with the processor architecture of the time. Newer processors have caching architectures that mean loop unrolling makes less significant improvements, or in some cases could even be detrimental. Improvements such as pipelining and hyperthreading mean the specific issues that Comba addressed may be no longer a concern. The same experiments today, on a modern processor, may show only marginal effects, but any performance improvement is worthwhile, particularly in routines that execute many thousands of times. OpenSSL and other libraries make heavy use of the Comba method, which wins over the straightforward approach or more complex, alternative algorithms for small sizes (between 4 and 16 words).

Comba multiplication is a good example of optimization as an implementation detail. The underlying algorithm still remained the same, and thus still remained O(n2), rather than being an improvement in time complexity such as offered by Karatsuba multiplication or some other algorithm. Comba's refinements merely reduced the hidden constant that the big-oh notation conceals.

Can it be better?

Nevertheless, Comba multiplication does have some potential. For example, it is one of very few computer multiplication algorithms that can readily be explained using pencil and paper, or that can be performed manually. One way do do this is to write the two numbers on the corners of pieces of paper, and either reverse one, or turn the paper upside-down. Now slide the two numbers past each other. As the digits align, they determine the order of the Comba multiplication products. In the 23 x 89 example:

  |
  |3 2
  `----
----.      => 3*9           = 27   => 2047
 8 9|                        / |
    |                       /  |
                  _________/   |
  |              / carry 2     |
  |3 2          /              |
  `----        /               |
  ----.    => 2 + 3*8 + 2*9 = 44
   8 9|                      / |
      |                     /  |
                  _________/   |
  |              / carry 4     |
  |3 2          /              |
  `----        /               |
    ----.  => 4 + 2*8       = 20
     8 9|
        |
With a little practice, the two numbers sliding past each other can be visualized in the mind's eye, and the answer to a multiplication can be written down, right to left, in an impressive feat of mental arithmetic! Or so I'm told.

Even on paper, Comba's method has potential for improvement. One of the issues mentioned earlier was that the size of the products in the individual columns, and their sums, can get quite large. One way of minimizing this problem is to drop some of the limitations of our decimal number system. If digits are allowed to be negative, then the products can be made smaller (at the expense of being signed). For example, 89 = 8*10 + 9 = 9*10 - 1 = 1*100 - 1*10 - 1 could be written (1, -1, -1) in this relaxed system, and the multiplication now becomes:

         2  3
x     1 -1 -1
  ===========
        -2 -3
     -2 -3
   2  3
  ===========
   2  1 -5 -3
  ===========
   2  0  4  7
It takes a bit of thought to keep everything straight, but the individual products are much smaller. You need never multiply by 6, 7, 8 or 9 again!. As in this example, the inputs may grow by an extra digit, but such considerations may not matter on a computer, where an appropriate choice of limb size allows this modified Comba method to be quite efficient. There is still value in deferring the carry propagation to the last moment.

Who invented it?

Interestingly, there is some controversy over Comba's attribution to the method. Similar techniques were mentioned in 1986 in the paper that proposed Barrett reduction, so many claim Barrett should be credited with the column-by-column approach. However, it turns out the method had been known about for quite some time. An unknown author detailed the method in Treviso Arithmetic, published in Treviso, Italy as early as 1478.

Sources

Comba, P. G. Exponentiation cryptosystems on the IBM PC, IBM Systems Journal, Vol. 29, No. 4, December 1990. http://www.research.ibm.com/journal/sj/294/ibmsj2904E.pdf, viewed on July 13, 2005
Harley, Robert. Re: Comba attributed to Barrett?. Posting on sci.crypt, May 20 2003, archived at http://www.derkeiler.com/Newsgroups/sci.crypt/2003-05/1447.html, viewed on July 13, 2005.
Granlund, T. The GNU Multiple Precision Arithmetic Library, http://www.swox.com/gmp/gmp-man-4.1.4.pdf, as viewed on July 13, 2005.
St Denis, T. LibTom Projects, http://libtomcrypt.org/talk_lsm.pdf, as viewed on July 13, 2005.

Thanks to randombit for the OpenSSL reference and empirical performance data.

Log in or register to write something here or to contact authors.