3.1 NATURAL NUMBERS

3.1.1 Weighted Systems

Any natural number (nonnegative integer) can be represented, in a unique way, in the form of a sum of powers Bⁱ of some natural number B greater than 1, each of them multiplied by a natural number smaller than B. The following theorem defines the base-B numeration system.

Theorem 3.1 Given a natural number B greater than 1, any natural number x smaller than Bⁿ can be expressed in the form

where every coefficient x_i is a natural number smaller than B. Furthermore, there is only one possible vector (x_n−1 x_n−2 … x₀) representing x.

The following algorithm computes the coefficients x_i:

Algorithm 3.1

for i in 0..n − 1 loop x(i):=x mod B; x:=x/B; end loop;

Definitions 3.1

1. The most commonly used values of B are 10 (decimal system), 2 (binary system), 16 (hexadecimal system), and 8 (octal system). The coefficients x_i of the base-B representation of x are called the base-B digits of x. The binary digits are called bits. The hexadecimal digits 10, 11, 12, 13, 14, and 15 are usually replaced by letters: A, B, C, D, E, and F.
2. This type of representation is called positional as the weight Bⁱ associated with the digit x_i depends on i, that is, on the position of the digit within the vector (x_n−1 x_n−2 … x₀).
3. The base-B digits could in turn be encoded in another base. As an example, if B = 10 and the decimal digits are represented in the form of 4-bit binary vectors, the so-obtained system is called binary-coded decimal (BCD).

Example 3.1 Compute the hexadecimal representation of 287645:

It is possible to define mixed numeration systems or mixed-radix systems, that is with several bases. For instance, the time is expressed in days of 24 hours, hours of 60 minutes, minutes of 60 seconds, seconds of 1000 milliseconds, and so on. The generalization of Theorem 3.1 is the following.

Theorem 3.2 Given n natural numbers b_n−1, b_n−2… b₀, greater than 1, any natural number x smaller than B_n = b_n−1.b_n−2. …. b₀, can be expressed in the form

where

and every coefficient x_i is a natural number smaller than b_i. Furthermore, there is only one possible vector (x_n−1 x_n−2 … x₀) representing x.

Base-B and mixed-radix numeration systems are weighted systems. In base B the weights are Bⁱ, that is the successive powers of B, while the weights in the mixed-radix system are given by

The following algorithm computes the coefficients x_i.

Algorithm 3.2

for i in 0..n−1 loop x(i):=x mod b(i); x:=x/b(i); end loop;

Example 3.2 Compute the representation of 287645 in the mixed base (13, 12, 15, 11, 12):

Comment 3.1 Given a natural number s, the conversion from the base-B representation of x (Theorem 3.1) to its base-B^s representation, and inversely, is straightforward. Suppose that n = s.q (if n were not divisible by s, then (n/s.s − n) initial 0's should be added). Then

where

As an example, the binary representation of the decimal number 287645 is 01000110001110011101. The conversion to its hexadecimal representation is straightforward:

3.1.2 Residue Number System

A residue number system (RNS) is defined by a set of s moduli {m_i). If the m_is are pairwise prime, the RNS is called nonredundant. The RNS-representation of a given natural number N is the vector R(N), whose components r_i are the respective residues modulo m_i, that is, the successive remainders of the integer division N/m_i

The least common multiple (lcm) of {m_i} is the range of the RNS, generally denoted M. The greatest natural number that can be represented in the RNS defined by {m_i} is

If the m_is are pairwise prime then

Garner's algorithm 2.2, restricted to the computation of the successive values of u, provides the mixed-radix components with respect to the weights

(see Example 2.4).