Modular Number Systems

A modular integer system is a special case of fixed-point systems where there are no fractional digits. It operates within a subset of integers.

Modular systems are important because all computers use them to approximate integer operations. In order to represent true integers, which can have an infinite number of digits, a computer would require an infinite amount of memory to store those digits.

Example 15.2. A modulo-100 System

To illustrate the concept, consider a subset of the non-negative integers limited to 2 decimal digits.

Such a set only includes value from 0 to 99, and is known as the modulo-100 set. The value 100 is known as the modulus.

    94          10          03
+   12      /   03      *   03
-------     -------     -------
  1 06          03 R1       09

Note that the same problems with overflow and round-off/truncation occur with any fixed-point system. The integer addition result of 106 is too large to fit in 2 digits, to the '1' is dropped and the result is 06.

Results of integer division may be truncated, leaving a remainder. We can correct the results of the multiplication above by adding the remainder from division: 03 * 03 + 1 = 10.

When performing operations such as addition or multiplication on modular systems, we follow the exact same procedure as we would for any other fixed point system.

Looking at it another way, when counting in a modular system, after reaching the largest allowable value, we "circle back" or "wrap" to zero. I.e., 99 + 1 = 0 in modulo-100 arithmetic.

Computers behave the same way when performing "integer" operations. We must be aware that what we call integers in computer programming are actually modular number systems, limited to a certain number of binary digits. They can and often do overflow, and this does not normally trigger an error condition in a program. Instead, the program continues unaware and produces incorrect results if it was assuming that it's working in the infinite integer set. The programmer usually must explicitly check for this following calculations that have the potential to overflow, or code them in such a way that overflow will never happen. Some programming languages insert checks automatically, but this severely reduces program performance, because it requires additional machine instructions following every integer arithmetic instruction.


There are 3 possible results from a computational error in a program:
  1. The program produces a meaningful error message telling the user what went wrong. This is what happens when the programmer is competent.
  2. The program crashes or produces a misleading or uninformative error message. We have all been annoyed by these issues.
  3. The program continues and produces incorrect results. This is the worst possible outcome, the kind of thing that causes billion-dollar space probes to crash.

Programmers must be aware of the range of the modular integer sets used by any computer and take measures to ensure that overflows do not cause incorrect results.



Be sure to thoroughly review the instructions in Section 2, “Practice Problem Instructions” before doing the practice problems below.
  1. What is a modular number system?

  2. What would we call a modular system with 3 decimal digits?

  3. What is the range of a modulo-10 system?

  4. What happens when we add 1 to the largest possible value in a modular number system?

  5. What typically happens when an "integer" overflow occurs in a computer program?