This model of computation closely resembles a typical modern-day com-

puter, except that we have abstracted away many annoying details. How-

ever, there are two details of real machines that cannot be ignored; namely,

any real machine has a ¬nite number of memory cells, and each cell can

store numbers only in some ¬xed range.

The ¬rst limitation must be dealt with by either purchasing su¬cient

memory or designing more space-e¬cient algorithms.

The second limitation is especially annoying, as we will want to perform

computations with quite large integers ” much larger than will ¬t into any

single memory cell of an actual machine. To deal with this limitation, we

shall represent such large integers as vectors of digits to some ¬xed base, so

that each digit is bounded so as to ¬t into a memory cell. This is discussed in

more detail in the next section. Using this strategy, the only other numbers

we actually need to store in memory cells are “small” numbers represent-

ing array indices, addresses, and the like, which hopefully will ¬t into the

memory cells of actual machines.

Thus, whenever we speak of an algorithm, we shall mean an algorithm that

can be implemented on a RAM, such that all numbers stored in memory cells

are “small” numbers, as discussed above. Admittedly, this is a bit imprecise.

For the reader who demands more precision, we can make a restriction such

as the following: there exist positive constants c and d, such that at any

point in the computation, if k memory cells have been written to (including

inputs), then all numbers stored in memory cells are bounded by k c + d in

absolute value.

Even with these caveats and restrictions, the running time as we have de-

¬ned it for a RAM is still only a rough predictor of performance on an actual

machine. On a real machine, di¬erent instructions may take signi¬cantly dif-

ferent amounts of time to execute; for example, a division instruction may

take much longer than an addition instruction. Also, on a real machine, the

behavior of the cache may signi¬cantly a¬ect the time it takes to load or

store the operands of an instruction. Finally, the precise running time of an

38 Computing with large integers

algorithm given by a high-level description will depend on the quality of the

translation of this algorithm into “machine code.” However, despite all of

these problems, it still turns out that measuring the running time on a RAM

as we propose here is nevertheless a good “¬rst order” predictor of perfor-

mance on real machines in many cases. Also, we shall only state the running

time of an algorithm using a big-O estimate, so that implementation-speci¬c

constant factors are anyway “swept under the rug.”

If we have an algorithm for solving a certain type of problem, we expect

that “larger” instances of the problem will require more time to solve than

“smaller” instances. Theoretical computer scientists sometimes equate the

notion of an “e¬cient” algorithm with that of a polynomial-time algo-

rithm (although not everyone takes theoretical computer scientists very se-

riously, especially on this point). A polynomial-time algorithm is one whose

running time on inputs of length n is bounded by nc + d for some constants

c and d (a “real” theoretical computer scientist will write this as nO(1) ). To

make this notion mathematically precise, one needs to de¬ne the length of

an algorithm™s input.

To de¬ne the length of an input, one chooses a “reasonable” scheme to

encode all possible inputs as a string of symbols from some ¬nite alphabet,

and then de¬nes the length of an input as the number of symbols in its

encoding.

We will be dealing with algorithms whose inputs consist of arbitrary in-

tegers, or lists of such integers. We describe a possible encoding scheme

using the alphabet consisting of the six symbols ˜0™, ˜1™, ˜-™, ˜,™, ˜(™, and ˜)™.

An integer is encoded in binary, with possibly a negative sign. Thus, the

length of an integer x is approximately equal to log2 |x|. We can encode

a list of integers x1 , . . . , xn as “(¯1 , . . . , xn )”, where xi is the encoding of

x ¯ ¯

xi . We can also encode lists of lists, and so on, in the obvious way. All of

the mathematical objects we shall wish to compute with can be encoded in

this way. For example, to encode an n — n matrix of rational numbers, we

may encode each rational number as a pair of integers (the numerator and

denominator), each row of the matrix as a list of n encodings of rational

numbers, and the matrix as a list of n encodings of rows.

It is clear that other encoding schemes are possible, giving rise to di¬erent

de¬nitions of input length. For example, we could encode inputs in some

base other than 2 (but not unary!) or use a di¬erent alphabet. Indeed, it

is typical to assume, for simplicity, that inputs are encoded as bit strings.

However, such an alternative encoding scheme would change the de¬nition

3.3 Basic integer arithmetic 39

of input length by at most a constant multiplicative factor, and so would

not a¬ect the notion of a polynomial-time algorithm.

Note that algorithms may use data structures for representing mathe-

matical objects that look quite di¬erent from whatever encoding scheme

one might choose. Indeed, our mathematical objects may never actually be

written down using our encoding scheme (either by us or our programs) ”

the encoding scheme is a purely conceptual device that allows us to express

the running time of an algorithm as a function of the length of its input.

Also note that in de¬ning the notion of polynomial time on a RAM, it

is essential that we restrict the sizes of numbers that may be stored in the

machine™s memory cells, as we have done above. Without this restriction,

a program could perform arithmetic on huge numbers, being charged just

one unit of time for each arithmetic operation ” not only is this intuitively

“wrong,” it is possible to come up with programs that solve some problems

using a polynomial number of arithmetic operations on huge numbers, and

these problems cannot otherwise be solved in polynomial time (see §3.6).

3.3 Basic integer arithmetic

We will need algorithms to manipulate integers of arbitrary length. Since

such integers will exceed the word-size of actual machines, and to satisfy the

formal requirements of our random access model of computation, we shall

represent large integers as vectors of digits to some base B, along with a bit

indicating the sign. That is, for a ∈ Z, if we write

k’1

ai B i = ±(ak’1 · · · a1 a0 )B ,

a=±

i=0

where 0 ¤ ai < B for i = 0, . . . , k ’ 1, then a will be represented in memory

as a data structure consisting of the vector of base-B digits a0 , . . . , ak’1 ,

along with a “sign bit” to indicate the sign of a. When a is non-zero, the

high-order digit ak’1 in this representation should be non-zero.

For our purposes, we shall consider B to be a constant, and moreover, a

power of 2. The choice of B as a power of 2 is convenient for a number of

technical reasons.

A note to the reader: If you are not interested in the low-level details

of algorithms for integer arithmetic, or are willing to take them on faith,

you may safely skip ahead to §3.3.5, where the results of this section are

summarized.

We now discuss in detail basic arithmetic algorithms for unsigned (i.e.,

40 Computing with large integers

non-negative) integers ” these algorithms work with vectors of base-B dig-

its, and except where explicitly noted, we do not assume the high-order

digits of the input vectors are non-zero, nor do these algorithms ensure that

the high-order digit of the output vector is non-zero. These algorithms can

be very easily adapted to deal with arbitrary signed integers, and to take

proper care that the high-order digit of the vector representing a non-zero

number is non-zero (the reader is asked to ¬ll in these details in some of the

exercises below). All of these algorithms can be implemented directly in a

programming language that provides a “built-in” signed integer type that

can represent all integers of absolute value less than B 2 , and that provides

the basic arithmetic operations (addition, subtraction, multiplication, inte-

ger division). So, for example, using the C or Java programming language™s

int type on a typical 32-bit computer, we could take B = 215 . The resulting

software would be reasonably e¬cient, but certainly not the best possible.

Suppose we have the base-B representations of two unsigned integers a

and b. We present algorithms to compute the base-B representation of a+b,

a ’ b, a · b, a/b , and a mod b. To simplify the presentation, for integers

x, y with y = 0, we write divmod(x, y) to denote ( x/y , x mod y).

3.3.1 Addition

Let a = (ak’1 · · · a0 )B and b = (b ’1 · · · b0 )B be unsigned integers. Assume

that k ≥ ≥ 1 (if k < , then we can just swap a and b). The sum c := a + b

is of the form c = (ck ck’1 · · · c0 )B . Using the standard “paper-and-pencil”

method (adapted from base-10 to base-B, of course), we can compute the

base-B representation of a + b in time O(k), as follows:

carry ← 0

for i ← 0 to ’ 1 do

tmp ← ai + bi + carry, (carry, ci ) ← divmod(tmp, B)

for i ← to k ’ 1 do