Integers.

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

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

where

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

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

• one word for s mathend000# and
• one word for n mathend000#

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 mathend000# 2^N mathend000#-digits requires $\cal {O}$(n) mathend000# word operations
• the MULTIPLICATION of two integers with at most n mathend000# 2^N mathend000#-digits requires $\cal {O}$(n²) mathend000# word operations.