1 Multiple Precision Arithmetic

We need to go back to school and remember how we did basic arithmetic! Recall that we first learnt how to operate with small numbers i. e. the digits. Then we learnt how to represent and manipulate bigger numbers. Thus for us ``human''-sized symbols are the symbols 0-9 which we consider ``small''; in a similar way the numbers 0-2³² - 1 or the numbers made (in base 2) of thirty-two 0's and 1's are ``small'' for a computer. We must already know the following operations with these numbers; we use W to denote the set of basic symbols which represent natural numbers from 0 to M - 1 (M = 10 for humans and M = 2³² for computers):

addition

The operation of addition with carry

$$\tt add$$ : W×W×{0, 1}$$\to$$W×{0, 1}

where (a, b,$\mu$) $\mapsto$ (c,$\rho$) which satisfies

a + b + $$\mu$$ = c + $$\rho$$ ^. M

subtraction

The operation of subtraction with borrow

$$\tt sub$$ : W×W×{0, 1}$$\to$$W×{0, 1}

where (a, b,$\mu$) $\mapsto$ (c,$\rho$) which satisfies

a - b - $$\mu$$ = c - $$\rho$$ ^. M

multiplication

The operation of multiplication with remainder

$$\tt mul$$ : W×W$$\to$$W×W

where (a, b) $\mapsto$ (c, d ) which satisfies

a ^. b = c ^. M + d

division

The operation of division with remainder (this is a partial function)

$$\tt div$$ : W×W×W$$\to$$W×W

where (a, b, c) $\mapsto$ (d, e) when b < a and satisfies

b ^. M + c = a ^. d + e

with e < a.

There may be some further operations that we may need to check whether on element of W is less than another or equal to another and so on.

The main aim of this section is to write down methods of computing with integers written in the ``usual'' way as strings of symbols u₁u₂ ^... u_p representing u₁ ^. M^{p - 1} + ^... + u₁. We will also count the number of steps taken to make our calculations under the assumption that each of the above operations counts as one step.