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:

$$\Sigma_{{{0 \leq \i \leq n}}}^{{}}$$ (32)

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²) word operations.