4.1 Addition and Subtraction

This notion of "further counting" means, "to the integer n₁ add the integer n₂," and the integer s at which one arrives by this further counting is called "the result of addition" or the "sum of n₁ and n₂" and is represented by n₁ + n₂.

—Leopold Kronecker, On the Idea of Number

Since addition and subtraction are in principle the same operation with differing signs, the underlying algorithms are equivalent, and we can deal with them together in this section. We consider operands a and b with representations

where we assume a ≥ b. For addition this condition represents no restriction, since it can always be achieved by interchanging the two summands. For subtraction it means that the difference is positive or zero and therefore can be represented as a CLINT object without reduction modulo (N_max + 1).

Addition consists essentially of the following steps.

Algorithm for the addition a + b

Set i ← 0 and c ← 0.
Set t ← a_i + b_i + c, s_i ← t mod B, and c ← ⌊t/B⌋.
Set i ← i + 1; if i ≤ n − 1, go to step 2.
Set t ← a_i + c, s_i ← t mod B, and c ← ⌊t/B⌋.
Set i ← i + 1; if i ≤ m − 1, go to step 4.
Set s_m ← c.
Output s = (s_ms_m−1 … s₀)_B.

The digits of the summands, together with the carry, are added in step 2, with the less-significant part stored as a digit of the sum, while the more-significant part is carried to the next digit. If the most-significant digit of one of the summands is reached, then in step 4 any remaining digits of the other summand are added to any remaining carries one after the other. Until the last summand digit is processed, the less-significant part is stored as a digit of the sum, and the more-significant part is used as a carry to the next digit. Finally, if there is a leftover carry at the end, it is stored as the most-significant digit of the sum. The output of this digit is suppressed if it has the value zero.

Steps 2 and 4 of the algorithm appear in a similar form in the case of subtraction, multiplication, and division. The associated code, which is illustrated by the following lines, is typical for arithmetic functions:^[1]

s = (USHORT)(carry = (ULONG)a + (ULONG)b + (ULONG)(USHORT)(carry >> BITPERDGT));

The intermediate value t that appears in the algorithm is represented by the variable carry, of type ULONG, which holds the sum of the digits a_i and b_i as well as the carry of the previous operation. The new summation digit s_i is stored in the less-significant part of carry, from where it is taken by means of a cast as a USHORT. The resulting carry from this operation is held in the more-significant part of carry for the next operation.

The implementation of this algorithm by our function add_l() deals with a possible overflow of the sum, where in this case a reduction of the sum modulo (N_max + 1) is carried out.

int
add_l (CLINT aa_l, CLINT bb_l, CLINT ss_l)
{
  clint ss_l[CLINTMAXSHORT + 1];
  clint *msdptra_l, *msdptrb_l;
  clint *aptr_l, *bptr_l, *sptr_l = LSDPTR_L (ss_l);
  ULONG carry = 0L;
  int OFL = E_CLINT_OK;

The pointers for the addition loop are set. Here it is checked which of the two summands has the greater number of digits. The pointers aptr_l and msdaptr_l are initialized such that they point respectively to the least-significant and most-significant digits of the summand that has the most digits, or to those digits of a_l if both summands are of the same length. This holds analogously for the pointers bptr_l and msdbptr_l, which point to the least-significant and most-significant digits of the shorter summand, or to those digits of b_l. The initialization is carried out with the help of the macro LSDPTR_L() for the least-significant digits and MSDPTR_L() for the most-significant digits of a CLINT object. The macro DIGITS_L (a_l) specifies the number of digits of the CLINT object a_l, and with SETDIGITS_L(a_l, n) the number of digits of a_l is set to the value n.

 if (DIGITS_L (a_l) < DIGITS_L (b_l))
   {
     aptr_l = LSDPTR_L (b_l);
     bptr_l = LSDPTR_L (a_l);
     msdptra_l = MSDPTR_L (b_l);
     msdptrb_l = MSDPTR_L (a_l);
     SETDIGITS_L (ss_l, DIGITS_L (b_l));
   }
 else
   {
     aptr_l = LSDPTR_L (a_l);
     bptr_l = LSDPTR_L (b_l);
     msdptra_l = MSDPTR_L (a_l);
     msdptrb_l = MSDPTR_L (b_l);
     SETDIGITS_L (ss_l, DIGITS_L (a_l));
   }

 while (bptr_l <= msdptrb_l)
   {
     *sptr_l++ = (USHORT)(carry = (ULONG)*aptr_l++
                 + (ULONG)*bptr_l++ + (ULONG)(USHORT)(carry >> BITPERDGT));
   }

The two USHORT values *aptr and *bptr are copied via a cast to ULONG representation and added. To this the carry from the last interation is added. The result is a ULONG value that contains the carry from the addition step in its higher-valued word. This value is allocated to the variable carry and there reserved for the next iteration. The value of the resulting digit is taken from the lower-valued word of the addition result via a cast to the type USHORT. The carry saved in the higher-valued word of carry is included in the next iteration by a shift to the right by the number BITPERDGT of bits used for the representation of USHORT and a cast to USHORT.

In the second loop only the remaining digits of a_l are added to a possible existing carry and stored in s_l.

 while (aptr_l <= msdptra_l)
   {
     *sptr_l++ = (USHORT)(carry = (ULONG)*aptr_l++
                         + (ULONG)(USHORT)(carry >> BITPERDGT));
   }

  if (carry & BASE)
    {
      *sptr_l = 1;
      SETDIGITS_L (ss_l, DIGITS_L (ss_l) + 1);
    }

  if (DIGITS_L (ss_l) > (USHORT)CLINTMAXDIGIT)     /* overflow? */
    {
      ANDMAX_L (ss_l);     /* reduce modulo (Nmax + 1) */
      OFL = E_CLINT_OFL;
    }

  cpy_l (s_l, ss_l);

  return OFL;
}

The run time t of all the procedures given here for addition and subtraction is t = O(n), and thus proportional to the number of digits of the larger of the two operands.

Now that we have seen addition, we shall present the algorithm for subtraction of two numbers a and b with representations

to base B.

Algorithm for the subtraction a − b

Set i ← 0 and c ← 1.
If c = 1, set t ← B + a_i − b_i; otherwise, set t ← B − 1 + a_i − b_i.
Set s_i ← t mod B and c ← ⌊t/B⌋.
Set i ← i + 1; if i ≤ n − 1, go to step 2.
If c = 1, set t ← B + a_i; otherwise, set t ← B − 1 + a_i.
Set s_i ← t mod B and c ← ⌊t/B⌋.
Set i ← i + 1; if i ≤ m − 1, go to step 5.
Output s = (s_{m − 1}s_{m − 2} … s₀)_B.

The implementation of subtraction is identical to that of addition, with the following exceptions:

The ULONG variable carry is used to "borrow" from the next-higher digit of the minuend if a digit of the minuend is smaller than the corresponding digit of the subtrahend.
Instead of an overflow one must be on the lookout for a possible underflow, in which case the result of the subtraction would actually be negative; however, since CLINT is an unsigned type, there will be a reduction modulo (N_max + 1) (see Chapter 5). The function returns the error code E_CLINT_UFL to indicate this situation.
Finally, any existing leading zeros are eliminated.

Thus we obtain the following function, which subtracts a CLINT number b_l from a number a_l.

int
sub_l (CLINT aa_l, CLINT bb_l, CLINT d_l)
{
  CLINT b_l;
  clint a_l[CLINTMAXSHORT + 1]; /* allow 1 additional digit in a_l */
  clint *msdptra_l, *msdptrb_l;
  clint *aptr_l = LSDPTR_L (a_l);
  clint *bptr_l = LSDPTR_L (b_l);
  clint *dptr_l = LSDPTR_L (d_l);
  ULONG carry = 0L;
  int UFL = E_CLINT_OK;

  cpy_l (a_l, aa_l);
  cpy_l (b_l, bb_l);
  msdptra_l = MSDPTR_L (a_l);
  msdptrb_l = MSDPTR_L (b_l);

 if (LT_L (a_l, b_l))
   {
     setmax_l (a_l);
     msdptra_l = a_l + CLINTMAXDIGIT;
     SETDIGITS_L (d_l, CLINTMAXDIGIT);
     UFL = E_CLINT_UFL;
   }
 else
   {
     SETDIGITS_L (d_l, DIGITS_L (a_l));
   }

 while (bptr_l <= msdptrb_l)
   {
     *dptr_l++ = (USHORT)(carry = (ULONG)*aptr_l++
                - (ULONG)*bptr_l++ - ((carry & BASE) >> BITPERDGT));
   }

 while (aptr_l <= msdptra_l)
   {
     *dptr_l++ = (USHORT)(carry = (ULONG)*aptr_l++
                   - ((carry & BASE) >> BITPERDGT));
   }

 RMLDZRS_L (d_l);

  if (UFL)
    {
      add_l (d_l, aa_l, d_l);
      inc_l (d_l);
    }

  return UFL;
}

In addition to the functions add_l() and sub_l() two special functions for addition and subtraction are available, which operate on a USHORT as the second argument instead of a CLINT. These are called mixed functions and identified by a function name with a prefixed "u," as in the functions uadd_l() and usub_l() to follow. The use of the function u2clint_l() for converting a USHORT value into a CLINT object follows in anticipation of its discussion in Chapter 8.

int
uadd_l (CLINT a_l, USHORT b, CLINT s_l)
{
  int err;
  CLINT tmp_l;

  u2clint_l (tmp_l, b);
  err = add_l (a_l, tmp_l, s_l);
  return err;
}

int
usub_l (CLINT a_l, USHORT b, CLINT d_l)
{
  int err;
  CLINT tmp_l;
  u2clint_l (tmp_l, b);
  err = sub_l (a_l, tmp_l, d_l);
  return err;
}

Two further useful special cases of addition and subtraction are realized in the functions inc_l() and dec_l(), which increase or decrease a CLINT value by 1. These functions are designed as accumulator routines: The operand is overwritten with the return value, which has proved practical in the implementation of many algorithms.

It is not surprising that the implementations of inc_l() and dec_l() are similar to those of the functions add_l() and sub_l(). They test for overflow and underflow, respectively, and return the corresponding error codes E_CLINT_OFL and E_CLINT_UFL.

int
inc_l (CLINT a_l)
{
  clint *msdptra_l, *aptr_l = LSDPTR_L (a_l);
  ULONG carry = BASE;
  int OFL = E_CLINT_OK;
  msdptra_l = MSDPTR_L (a_l);

  while ((aptr_l <= msdptra_l) && (carry & BASE))
    {
      *aptr_l = (USHORT)(carry = 1UL + (ULONG)*aptr_l);
      aptr_l++;
    }

  if ((aptr_l > msdptra_l) && (carry & BASE))
    {
      *aptr_l = 1;
      SETDIGITS_L (a_l, DIGITS_L (a_l) + 1);
      if (DIGITS_L (a_l) > (USHORT) CLINTMAXDIGIT)  /* overflow ? */
         {
           SETZERO_L (a_l);      /* reduce modulo (Nmax + 1) */
           OFL = E_CLINT_OFL;
         }
    }
  return OFL;
}

int
dec_l (CLINT a_l)
{
  clint *msdptra_l, *aptr_l = LSDPTR_L (a_l);
  ULONG carry = DBASEMINONE;

  if (EQZ_L (a_l))     /* underflow ? */
    {
      setmax_l (a_l);      /* reduce modulo max_l */
      return E_CLINT_UFL;
    }

  msdptra_l = MSDPTR_L (a_l);

  while ((aptr_l <= msdptra_l) && (carry & (BASEMINONEL << BITPERDGT)))
    {
      *aptr_l = (USHORT)(carry = (ULONG)*aptr_l - 1L);
      aptr_l++;
    }

  RMLDZRS_L (a_l);
  return E_CLINT_OK;
}

^[1]The C expression in this compact form is due to my colleague Robert Hammelrath.

Function:	addition
Syntax:	int add_l (CLINT aa_l, CLINT bb_l, CLINT ss_l);
Input:	aa_l, bb_l (summands)
Output:	ss_l (sum)
Return:	E_CLINT_OK if all is ok E_CLINT_OFL in the case of overflow

Function:	subtraction
Syntax:	int sub_l (CLINT aa_l, CLINT bb_l, CLINT d_l);
Input:	aa_l (minuend), bb_l (subtrahend)
Output:	d_l (difference)
Return:	E_CLINT_OK if all is ok. E_CLINT_UFL in the case of underflow

Function:	mixed addition of a CLINT type and a USHORT type
Syntax:	int uadd_l (CLINT a_l, USHORT b, CLINT s_l);
Input:	a_l, b (summands)
Output:	s_l (sum)
Return:	E_CLINT_OK if all is ok E_CLINT_OFL if overflow

Function:	subtraction of a USHORT type from a CLINT type
Syntax:	int usub_l (CLINT a_l, USHORT b, CLINT d_l);
Input:	a_l (minuend), b (subtrahend)
Output:	d_l (difference)
Return:	E_CLINT_OK if all is ok E_CLINT_UFL if underflow

Function:	increment a CLINT object by 1
Syntax:	int inc_l (CLINT a_l);
Input:	a_l (summand)
Output:	a_l (sum)
Return:	E_CLINT_OK if all is ok E_CLINT_OFL if overflow