Team-Fly

# Chapter 4: The Fundamental Operations

## Overview

Thus calculation can be seen as the basis and foundation of all the arts.

And you, poor creature, you are completely useless. Look at me. Everyone needs me.

Aesop, "The Fir and the Blackberry Bush"

There is one small prerequisite for mastering the mathemagic tricks in this chapter you need to know the multiplication tables through 10 backward and forward.

Arthur Benjamin, Michael B. Shermer, Mathemagics

THE FUNDAMENTAL BUILDING BLOCKS OF any software package for computer arithmetic are the functions that carry out the basic operations of addition, subtraction, multiplication, and division. The efficiency of the entire package hangs on the last two of these, and for that reason great care must be taken in the selection and implementation of the associated algorithms. Fortunately, volume 2 of Donald Knuth's classic The Art of Computer Programming contains most of what we need for this portion of the FLINT/C functions.

In anticipation of their representation to come, the functions developed in the following sections use the operations cpy_l() , which copies one CLINT object to another in the sense of an allocation, and cmp_l() , which makes a comparison of the sizes of two CLINT values. For a more precise description see Section 7.4 and Chapter 8.

Let us mention at this point that for the sake of clarity, in this chapter the functions for the fundamental arithmetic operations are developed all of a piece, while in Chapter 5 it will prove practical to split some of the functions into their respective " core " operations and from there develop additional steps such as the elimination of leading zeros and the handling of overflow and underflow, where, however, the syntax and semantics of the functions are kept intact. For an understanding of the relations described in this chapter this is irrelevant, so that for now we can forget about these more difficult issues.

 Team-Fly
Team-Fly

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

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

1. Set i 0 and c 0.

2. Set t a i + b i + c , s i t mod B , and c t / B .

3. Set i i + 1; if i n 1, go to step 2.

4. Set t a i + c , s i t mod B , and c t / B .

5. Set i i + 1; if i m 1, go to step 4.

6. Set s m c .

7. Output s = ( s m s 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.

 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

```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)); }
```

In the first loop of add_l the digits of a_l and b_l are added and stored in the result variable ss_l . Any leading zeros cause no problem, and they are simply used in the calculation and filtered out when the result is copied to s_l . The loop runs from the least-significant digit of b_l to the most-significant digit. This corresponds exactly to the process of pencil-and-paper addition as learned at school. As promised , here is the implementation of the carry.

```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 after the second loop there is a carry, the result is one digit longer than a_l . If it is determined that the result exceeds the maximal value N max representable by the CLINT type, then the result is reduced modulo ( N max + 1) (see Chapter 5), analogously to the treatment of standard unsigned types. In this case the status announcement of the error code E_CLINT_OFL is returned.

```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

1. Set i 0 and c 1.

2. If c = 1, set t B + a i b i ; otherwise , set t B 1 + a i b i .

3. Set s i t mod B and c t / B .

4. Set i i + 1; if i n 1, go to step 2.

5. If c = 1, set t B + a i ; otherwise, set t B 1 + a i .

6. Set s i t mod B and c t / B .

7. Set i i + 1; if i m 1, go to step 5.

8. 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 .

 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

```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);
```

In the following the case a_l < b_l is considered , in which b_l is subtracted not from a_l , but from the largest possible value, N max . Later, the value (minuend+1) is added to this difference, so that altogether the calculation is carried out modulo ( N max + 1). To generate the value N max the auxiliary function setmax_l() is used.

```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);
```

The required addition of (minuend + 1) to the difference N max b_l stored in d_l is carried out before the output of 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.

 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

```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; }
```

 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

```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 .

 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

```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; }
```

 Function: decrement a CLINT object by 1 Syntax: int dec_l (CLINT a_l); Input: a_l (minuend) Output: a_l (difference) Return: E_CLINT_OK if all is ok E_CLINT_UFL if underflow

```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.

 Team-Fly