Programming Praxis

Over the next few exercises we’ll be developing a library of functions that provide arithmetic on big numbers: integers that are too large to fit into a machine word. Most languages, including Scheme, provide big numbers, either natively or through a standard library, so you are unlikely to need a library for big numbers. On the other hand, coding big numbers is fun, and makes a good exercise. We’ll get started today by defining a representation for big numbers and writing a few small functions.

The first decision to make when writing a big number library is to choose the radix in which numbers are represented. With binary computers, it is most economical to make the radix the largest convenient power of two; for a 32-bit CPU, the preferred radix is 2¹⁶, which means that single-place multiplication plus a carry never overflows a machine word. During development, we choose a radix of 1000 (“millenial digits”), which are convenient for debugging since the numbers are easily read by human eyes, but we’ll be careful not to rely on the radix, so that it is easy to switch to a larger radix when development is finished.

The second decision is how to represent numbers. A number is, of course, represented as a polynomial in the base of the radix, with the digits stored separately. We use a list, rather than an array, since lists are more natural in Scheme, and since lists don’t impose any additional limits on the size of the numbers. The exact representation we choose is called the signed magnitude representation, where the head of the list gives the number of digits in the list, as well as the sign of the number, and the tail of the list gives the digits themselves, least-significant digit first, always stored as a positive number. Thus, the number 12345678 is stored in our representation as the list (3 678 345 12) and the number -87654321 is stored as (-3 321 654 87), 1 is (1 1), -1 is (-1 1), and zero is (0). Among other things, this representation makes it easy to compare numbers: first compare the signed magnitude, and only compare the numbers digit-by-digit if the signed magnitudes are the same.

In today’s exercise we will implement the following procedures: functions to convert between big numbers and the native numbers of the underlying language, functions to take the absolute value of a big number and to negate a big number, predicates to identify positive, negative or zero big numbers and even or odd big numbers, and functions to compare two big numbers.

Your task is to implement those big number functions described using a signed-magnitude representation; we’ll write functions to do arithmetic on big numbers in future exercises. When you are finished, you are welcome to read or run a suggested solution, or to discuss the exercise or post your own solution in the comments below.

Pages: 1 2