Integers.

One machine word can contain a SINGLE PRECISION INTEGER in the range $[0, 2^{N} - 1]$ . To represent integers outside of this range, so called MULTIPRECISION INTEGER, we use arrays of $N$ -bit words. To be precise we consider the $2^N$ -ary (or radix $2^N$ ) expansion of a nonzero integer:

$$a \ \ = \ \ (-1)^s \ {\Sigma}_{0 \leq \i \leq n} a_i 2^{N i}$$ (33)

where

• every $a_i \in [0, 2^{N} - 1]$ is a digit in the $2^N$ -ary expansion of $a$ ,
• $s \in \{0, 1\}$ determines the sign of $a$ ,
• $n + 1 \in [1, 2^{N}]$ is the number of $2^N$ -digits in the $2^N$ -ary expansion of $a$ ,
• $a_n \neq 0$ .

Then the integer $a$ with $(n+1)$ $2^N$ -digits can be represented by an array (of $N$ -bit words) with length $n +3$ since we need

• one word for $s$ and
• one word for $n$

The reasonable UNIT OPERATION for integers is the the WORD OPERATION. One can easily check that

• the ADDITION of two integers with at most $n$ $2^N$ -digits requires ${\cal O}(n)$ word operations
• the MULTIPLICATION of two integers with at most $n$ $2^N$ -digits requires ${\cal O}(n^2)$ word operations.