Recursion in multiplication

The processor

Everything in this paper depends on how the processor stores numbers, so we describe it before anything else. Leaving this vague is how a hidden multiplication can slip into a method that is supposed to avoid them.

Two things follow from this, and the rest of the paper rests on them.

Carrying does not need subtraction. When two digits are added the answer is somewhere between 0 and 19. If it is more than 9 we would normally subtract 10 and carry 1, but this processor cannot subtract. Adding 6 instead and keeping only the lower four bits gives the same digit, because for any value from 10 to 19, (value + 6) & 15 equals value − 10. The carry appears on its own. So carrying is done with an addition, which the processor has.

Multiplying by ten is not an operation. Because the processor counts in tens and stores one digit per slot, moving a number one place to the left means writing it starting one slot further along. Section 4 uses this.

Why the decimal requirement is not just convenient

Stating a requirement and then presenting a method that happens to need it looks circular. So it is worth checking the other direction. What happens if we take the requirement away?

Suppose the processor stores numbers in binary instead - as ones and zeros packed into a word, which is how nearly every real processor works. Nothing else changes. Moving a number one decimal place is now real work, so we have to compute it by adding. The table below counts additions for 32-bit numbers, averaged over four thousand random pairs. The base is how many different digits the number system uses: base ten uses 0 to 9, base two uses 0 and 1.

Base ten does worse than every binary option, including base two, which needs no multiples table at all. That is the point. The table has ten entries because base ten has ten digits. Base ten is worth using because moving a place is free. Moving a place is free because the processor stores decimal digits. Take away the decimal storage and all three fall together - the sensible base becomes two or four, and the multiples table, which is the whole subject of this paper, shrinks to nothing.

To be clear, decimal is not chosen for speed. This method needs roughly two hundred digit additions for numbers of about 32 bits, while a binary processor needs about forty-four word additions for the same work. Binary is several times faster. Decimal storage exists because binary cannot represent decimal fractions such as 0.1 exactly, which matters in money, tax, and accounting. That is why decimal formats were added to the IEEE 754 standard in 2008 and why IBM builds decimal hardware. Section 9 returns to this.

The problem

Take 726 × 25. The obvious approach is to add 726 to itself 25 times. It works, but the number of additions depends on the value of the multiplier rather than its length. A six-digit multiplier would need close to a million additions. This is not merely slow; it becomes unusable as soon as the numbers grow.

Long multiplication, the method taught in school, fixes this by splitting the multiplier into digits:

726 × 25  =  726×5  +  726×2 × 10

Now the work depends on how many digits the multiplier has, not how large it is. But it leaves two things a processor without a multiplier cannot do:

1. Work out 726×5 and 726×2. Sections 3 handles this.
2. Apply the factor of ten. Section 4 handles this.

We could store a ten-by-ten times table and look the answers up. We deliberately do not, because the interesting question is what structure the multiples have when you are forced to work them out. The answer turns out to be something mathematicians already have a name for.

Building the multiples

We build the multiples of the whole number being multiplied, not of single digits. This removes the inner digit-by-digit loop completely. Writing x for that number, we want t[k] = k × x for every k from 0 to 9. Each one is built from ones already finished:

Nine additions for the whole table. Every value a row needs is finished before that row is reached, so the table can be filled from top to bottom with no reordering.

Nine additions is the best possible

Eight of the rows do not exist until something creates them, and one addition creates at most one value. So eight additions is a floor. One extra is spent because row 7 has to be built on top of row 6 rather than sharing a doubling with something else. Nine is not just good, it is the least that will work.

What this pattern is called

A sequence that starts at 1 where every later number is the sum of two earlier ones is called an addition chain. Mathematicians have studied these since the 1930s. Alfred Brauer wrote about them in 1939 [3], and Knuth gives the standard summary [4]. Our table is a small collection of such chains growing out of 1.

This is worth knowing for two reasons. It confirms our table is a known object rather than a lucky arrangement, and it means the general problem is harder than our small case suggests. Finding the shortest chain for a large number is difficult, and one question about them, the Scholz–Brauer conjecture from 1937, is still unanswered.

Removing place value

Adding a zero to the end of a number is free only when the way you count matches the way you store. That one condition settles the whole design:

Our processor is the first row, so we never move a number at all. Each partial result is added into the running total starting at the slot matching its digit's position:

/* j is where the multiplier digit sits, and also the place value */
for (j = 0; j < yn; j++) {
    d = y[j];
    if (d == 0) continue;
    add_at(out, xn + yn, t[d], tn, j);
}

That j in the last argument is the multiplication by ten, hundred, or thousand. There is no arithmetic, no shift instruction, no appended zero. Long multiplication on paper has always worked this way - the indentation of each row is exactly this position - but naming it turns a rule we would otherwise have to justify into a property of how memory is addressed.

Why we do not build a ten times entry

If we did want 10 × x, the cheapest way is t[5] + t[5]: one addition, and a doubling, so it reads one value rather than two. Built from scratch it would take four additions, so this is a real saving.

We do not build it, because nothing would use it. t[10] holds ten times the number being multiplied, but the only thing that ever needs scaling is the running total, and that holds a different value at every step. No table computed once can supply it.

We tested the strongest version of this idea, in which the whole table is kept scaled and moved along one place at a time using t[5] + t[5]. There the trick is genuinely used, and it still loses: 52.2 additions on average, against 48.9 for the simpler approach and 42.5 for base four. Rebuilding the table after each move costs more than it saves. We note the construction here in case anyone ports this to a binary processor, where it would be the right choice.

The method

The inputs are two lists of digits, x with m digits and y with n digits, ones digit first. The answer needs m + n slots.

1. Start. Copy x into t[1], with one extra zero slot at the end so the larger multiples fit.
2. Build. For k from 2 to 9, copy one earlier row into t[k] and add another into it, following the table in Section 3.
3. Total up. For each digit position j in y, if that digit is not zero, add t[digit] into the answer starting at slot j.

Both loops have a known length, so the program contains no recursion when it runs. Section 8 explains why that matters.

Only building what is used

Building all nine rows is wasteful when the multiplier uses only a few digits. Instead, mark the digits that actually appear in y, then work backwards through the table marking the rows those rows depend on. Build only what is marked.

For 726 × 25 this marks rows 5, 4 and 2, so three rows are built instead of eight, and the cost drops from 40 additions to 20. The saving is largest exactly where the full table is hardest to justify, namely short multipliers.

Try it

Type two numbers and press Step. The left panel builds the multiples one addition at a time. The right panel writes each partial result into the running total at its position. The counters below track every digit addition performed.

The shift counter stays at zero whatever you type, which is the claim of Section 4 shown rather than asserted. The swap counter shows what the same answer would cost with the two numbers exchanged; Section 7 explains why they differ. Try 1234 × 5678 or 10 × 999999999.

How much it costs

Let m and n be the number of digits in each input, and z the count of non-zero digits in the multiplier. Costs are measured in digit additions, since that is the only arithmetic the processor can do.

The total grows as m × n. Repeated adding grows with the value of the multiplier instead, which is the difference between a program that finishes and one that does not. Measured figures:

The last row shows both effects. A multiplier that uses every digit gains nothing from building fewer rows, but still drops from 98 to 77 simply by swapping the two numbers around. That is the next subsection.

Which number goes where

Since a × b and b × a give the same answer, either number can play either role. The two choices do not cost the same. Building the table depends on the length of the first number, while adding up depends on which digits the second number contains. These pull in different directions.

Across 117,117 pairs, comparing each arrangement with its reverse:

Some individual cases are dramatic. 1234 × 5678 costs 55 additions one way and 35 the other. 10 × 999999999 costs 39 one way and 10 the other.

Choosing correctly does not require trying both. The cost of an arrangement is predicted by

cost  ≈  (rows needed + non-zero digits) × (length of first number + 1)

Work this out both ways and take the smaller. Across the sweep it picked the cheaper arrangement on 104,642 of 104,642 pairs where the two differed - every one. It is also cheap enough to run on the target processor: both quantities are below twenty, so the one multiplication it appears to need is itself a table entry.

When the table stops being worth it

The table is a fixed cost spread over the digits of the multiplier. For a one-digit multiplier it is a loss. Building only what is used recovers most of that, and choosing the better arrangement puts the shorter number into the multiplier position, which helps again. Below about three digits the honest answer is to build the single multiple needed and skip the table.

The program

/* Add src into acc starting at slot off. No subtraction anywhere. */
static void add_at(uint8_t *acc, int alen,
                   const uint8_t *src, int slen, int off)
{
    int i, s, carry = 0;

    for (i = 0; i < slen && off + i < alen; i++) {
        s = acc[off + i] + src[i] + carry;
        g_digit_adds++;
        carry = (s > 9);
        acc[off + i] = carry ? ((s + 6) & 0x0F) : s;   /* add 6, not minus 10 */
    }
    while (carry && off + i < alen) {          /* let the carry run on */
        s = acc[off + i] + 1;
        g_digit_adds++;
        carry = (s > 9);
        acc[off + i] = carry ? ((s + 6) & 0x0F) : s;
        i++;
    }
}

/* CHAIN[k] = {a,b} means row k is row a plus row b, with a and b below k. */
static const uint8_t CHAIN[10][2] = {
    {0,0}, {0,0}, {1,1}, {1,2}, {2,2},
    {1,4}, {3,3}, {1,6}, {4,4}, {3,6}
};

void dec_mul(const uint8_t *x, int xn,
             const uint8_t *y, int yn, uint8_t *out)
{
    uint8_t t[10][MAXD];
    int tn = xn + 1, k, j;

    memset(t, 0, sizeof t);
    memcpy(t[1], x, xn);

    for (k = 2; k <= 9; k++) {                  /* nine additions */
        memcpy(t[k], t[CHAIN[k][0]], tn);
        add_at(t[k], tn, t[CHAIN[k][1]], tn, 0);
    }

    memset(out, 0, xn + yn);
    for (j = 0; j < yn; j++) {                  /* no shift exists */
        uint8_t d = y[j];
        if (d == 0) continue;
        add_at(out, xn + yn, t[d], tn, j);
    }
}

Choosing the better arrangement of the two inputs is small enough to sit alongside it:

/* Both factors are under 20, so the product below is itself a table
   entry on this machine. No real multiplication is needed here. */
static int order_cost(int xn, const uint8_t *y, int yn)
{
    int need[10], k, j, rows = 0, nonzero = 0;

    mark_needed(y, yn, need);
    for (k = 2; k <= 9; k++) rows += need[k];
    for (j = 0; j < yn; j++) if (y[j] != 0) nonzero++;

    return (rows + nonzero) * (xn + 1);
}

void dec_mul_auto(const uint8_t *x, int xn,
                  const uint8_t *y, int yn, uint8_t *out)
{
    if (order_cost(yn, x, xn) < order_cost(xn, y, yn))
        dec_mul(y, yn, x, xn, out, 1);      /* swapped */
    else
        dec_mul(x, xn, y, yn, out, 1);
}

Three notes on the code

• The register keyword does nothing in modern C. What this code actually provides is more useful: no heap, no recursion while running, a fixed working set, and a bounded stack.
• Rows 1, 2, 3, 4 and 6 all have to exist at the same time to finish the table. That is five stored values plus the running total, which is worth checking against the real processor before committing to this design.
• Negative numbers are out of scope. Negating a decimal number needs an operation this processor does not have, so the method handles positive whole numbers only. Section 9 describes how hardware designers get around this.

Related work

Both problems from Section 2 have been studied for decades, and the combination has been built in hardware many times. This section places our work against that background.

A. Decimal multiplier hardware

This is the closest match. Engineers building decimal multiplying circuits face exactly the question of Section 3, and they divide the multiples into easy and hard ones. Easy multiples can be produced by rewiring; hard ones need a carry to travel along the number, which takes time.

Erle and Schulte's 2003 design [1] stores a reduced set of multiples, much as we do, and their follow-up produces them as needed instead of storing them. Vázquez, Antelo and Montuschi [2] note that in their circuit, producing four times and eight times a number takes two and three times as long as doubling it, so they switch to a scheme using five times and ten times instead.

That difference is worth dwelling on. In our software version every row costs exactly one addition, so the order barely matters. In hardware, three times a number is awkward, because it cannot be produced by rewiring alone, while zero, one, two, four and five times are quick. The same method gives different answers depending on what you are counting.

B. Addition chains

As Section 3 noted, our table is a Brauer chain [3], and Knuth [4] gives the standard treatment. The usual modern application is cryptography, where raising a number to a large fixed power quickly depends on finding a short chain for that power. Our use, minimising additions rather than multiplications, is the same problem with the operations relabelled.

C. Multiplying by fixed constants

Engineers who design signal-processing circuits solve a very similar problem, which they call multiple constant multiplication: multiply an input by a known set of fixed numbers using as few adders as possible, because a full multiplier circuit is expensive [5].

Our Section 3 table is an instance of it - produce 2 through 9 times a number using as few additions as possible. Their version differs in two ways: it works in binary, where shifting is free, and it allows subtraction, which opens up shortcuts such as writing 23 times a number as 32 times minus 9 times. Their general problem has no efficient solution, which is why our small ten-target case being solvable by hand is a matter of scale rather than cleverness.

D. Rewriting digits, and the improvement we have not made

Booth's 1951 method [6] allows digits to be negative, so a long run of digits can be replaced by one addition and one subtraction. The decimal version rewrites each digit as a value between −5 and 5.

Applied here this is the largest improvement still available. Digits 6 through 9 become "ten minus four" through "ten minus one", so the multiples table only needs rows 1 to 5, which take four additions instead of nine. That is a 55% cut in table cost.

The obstacle is precise. Negative digits require negating a number, which our processor cannot do. Hardware designers avoid this by storing digits in a code where negating is just flipping bits. On our processor it would mean adding a new instruction or a small lookup, and that cost should be measured before the change is made.

E. Real decimal machines, past and present

The processor described in Section 1 is not imaginary. The IBM 1620, announced in 1959, was a decimal computer that performed addition, subtraction and multiplication by looking values up in tables held in memory rather than computing them in circuits [7]. Addition used a 100-digit table and multiplication a 200-digit one. It had no adding circuit at all. The tables were loaded when the machine started, so changing them changed how it counted, and corrupting a colleague's tables was reportedly a common prank. Users nicknamed it CADET, for "Can't Add, Doesn't Even Try."

Our design is its exact opposite. The 1620 had memory and no adder, so it bought arithmetic with tables. Our processor has an adder and no table, so it buys the table with arithmetic. This also explains why storing a ten-by-ten times table, which we rejected in Section 2, was the right choice for that machine.

Decimal arithmetic is not only history. It returned to importance because binary cannot store decimal fractions exactly, which is unacceptable when handling money. Decimal formats were added to the IEEE 754 standard in 2008, and IBM ships decimal arithmetic hardware in its POWER and mainframe processors.

What is new

An honest accounting, part by part.

Nothing in the result is new, and that was never the goal. What the work does have is something the published literature mostly leaves out: it reaches the standard answer from the requirements alone, without assuming the reader already knows what a partial result is. The sequence in Section 3 was found by asking which multiples could be reached from which, which is the same question Brauer asked in 1939. Arriving at a known best answer by the intended route seems to us a better outcome than copying it.

The missing seventh row is instructive rather than embarrassing. It survived because we generated rows in the order the doublings suggested, and seven is the one digit below ten with no convenient route in that order. It is the kind of gap a systematic search finds immediately and an intuitive derivation does not.

What we would do next

1. Measure the cost of negating a number. If it can be added cheaply, rewriting digits cuts the table from nine additions to four. This is by far the largest improvement left.
2. Skip the table for short multipliers. The crossover point can be measured with the counters already in the code.
3. Delay the carries. Allowing slots to hold values above nine during the additions and correcting once at the end would take the carry out of the inner loop. This is the software equivalent of a technique every hardware design in Section 9A uses.
4. Handle negative numbers, or state clearly that the method is for positive whole numbers only.

Check it yourself

Every number in this paper can be reproduced on your own machine. The archive contains the C program, two test scripts, and a short guide saying which file checks which claim.

You will need a C compiler and Node.js. There are no libraries to install. The random sampling uses a fixed starting value, so the figures print identically on every machine.

The C program and the JavaScript test are separate implementations of the same method, written independently. They agree on every answer and on every addition count. The interactive panel in Section 6 is a third. If all three agree, the method is probably right.

References