10 - Exact Arithmetic

Summary

In this chapter, we show you how to represent exact numbers of arbitrary size. In certain applications, our ability to compute with such numbers is indispensible, especially so in computer algebra. Formal systems of symbolic computation, such as Maple [14], Mathematica [44], or Axiom [19], exploit an exact rational arithmetic. Moreover, programming languages oriented toward symbolic computation generally support exact computations. Such is particularly the case of Caml with the libraries bignum and ratio.

The sets of numbers that we will treat here are the natural numbers (also known as integers for counting), the signed integers (that is, both positive and negative), and the rational numbers. The natural numbers will be represented by the sequence of their digits in a given base. The sequence itself can be represented in various ways. We will represent natural numbers primarily by ordinary lists. This choice is not very efficient because it supports traversal in only one direction. If we decide to put least significant digits at the head of the list, then we can multiply and add fairly efficiently, but division will be inefficient because we must then turn the lists around.

Nevertheless, if we represent natural numbers as lists, then we can program the usual operations simply, and that model can serve later as the point of reference for getting into various other representations, such as representations by doubly linked circular lists or by arrays—representations used in “real” implementations.