## 2.6 Arithmetic with Large Integers Suppose that we need to do arithmetic operations on integers whose size exceeds the computer's hardware capability of representing integers. If we need to maintain all the significant digits in our results, switching to a floating-point representation would be of no value. In such cases, our only alternative is to use software to represent and manipulate the integers. We can accomplish this with the help of the divide-and-conquer approach. Our discussion focuses on integers represented in base 10. However, the methods developed can readily be modified for use in other bases. ### 2.6.1 Representation of Large Integers: Addition and Other Linear-Time Operaions A straightforward way to represent a large integer is to use an array of integers, in which each array slot stores one digit. For example, the integer 543,127 can be represented in the array *S* as follows:  To represent both positive and negative integers we need only reserve the high-order array slot for the sign. We could use 0 in that slot to represent a positive integer and 1 to represent a negative integer. We will assume this representation and use the defined data type **large\_integer** to mean an array big enough to represent the integers in the application of interest. It is not difficult to write linear-time algorithms for addition and subtraction, where *n* is the number of digits in the large integers. The basic operation consists of the manipulation of one decimal digit. In the exercises you are asked to write and analyze these algorithms. Furthermore, linear-time algorithms can readily be written that do the operation  where *u* represents a larger integer, *m* is a nonnegative integer, divide returns the quotient in integer division, and rem returns the remainder. This, too, is done in the exercises. ### 2.6.2 Multiplication of Large Integers A simple quadratic-time algorithm for multiplying large integers is one that mimics the standard way learned in grammar school. We will develop one that is better than quadratic time. Our algorithm is based on using divide-and-conquer to split an *n*-digit integer into two integers of approximately *n*/2 digits. Following are two examples of such splits.  In general, if *n* is the number of digits in the integer *u*, we will split the integer into two integers, one with \[*n*/2\] and the other with \[*n*/2\], as follows:  With this representation, the exponent *m* of 10 is given by  If we have two *n*-digit integers  their product is given by  We can multiply *u* and *v* by doing four multiplications on integers with about half as many digits and performing linear-time operations. The following example illustrates this method. Example 2.6****Consider the following:  Recursively, these smaller integers can then be multiplied by dividing them into yet smaller integers. This division process is continued until a threshold value is reached, at which time the multiplication can be done in the standard way. **** Although we illustrate the method using integers with about the same number of digits, it is still applicable when the number of digits is different. We simply use *m* = \[*n*/2\] to split both of them, where *n* is the number of digits in the larger integer. The algorithm now follows. We keep dividing until one of the integers is 0 or we reach some threshold value for the larger integer, at which time the multiplication is done using the hardware of the computer (that is, in the usual way). Algorithm 2.9: Large Integer Multiplication****Problem: Multiply two large integers, *u* and *v*. Inputs: large integers *u* and *v*. Outputs: *prod,* the product of *u* and *v*. ``` large_integer prod (large_integer u, large_integer v) { large_integer x, y, w, z; int n, m; n = maximum (number of digits in u, number of digits in v) if (u = = 0 || v = = 0) return 0; else if (n <= threshold) return u 脳 v obtained in the usual way; else{ m = [n/2]; x = u divide 10m; y = u rem 10m; w = v divide 10m; z = v rem 10m; return prod</1>(x,w) x 102m + (prod(w,y)) x 10m + prod(y,z); } } ``` **** Notice that *n* is an implicit input to the algorithm because it is the number of digits in the larger of the two integers. Remember that divide, rem, and 脳 represent linear-time functions that we need to write. ****Analysis of [Algorithm 2.9](#ch02ex23) Worst-Case Time Complexity (Large Integer Multiplication)We analyze how long it takes to multiply two *n*-digit integers. Basic operation: The manipulation of one decimal digit in a large integer when adding, subtracting, or doing divide 10m, rem 10m, or 脳 10m. Each of these latter three calls results in the basic operation being done *m* times. Input size: *n*, the number of digits in each of the two integers. The worst case is when both integers have no digits equal to 0, because the recursion only ends when *threshold* is passed. We will analyze this case. Suppose *n* is a power of 2. Then *x, y, w,* and *z* all have exactly *n*/2 digits, which means that the input size to each of the four recursive calls to *prod* is *n*/2. Because *m* = *n*/2, the linear-time operations of addition, subtraction, divide 10*m*, rem 10*m*, and 脳 10*m* all have linear-time complexities in terms of *n*. The maximum input size to these linear-time operations is not the same for all of them, so the determination of the exact time complexity is not straightforward. It is much simpler to group all the linear-time operations in the one term *cn*, where *c* is a positive constant. Our recurrence is then  The actual value *s* at which we no longer divide the instance is less than or equal to *threshold* and is a power of 2, because all the inputs in this case are powers of 2. For *n* not restricted to being a power of 2, it is possible to establish a recurrence like the previous one but involving floors and ceilings. Using an induction argument like the one in Example B.25 in [Appendix B](LiB0102.html#1369), we can show that *W* (*n*) is eventually nondecreasing. Therefore, Theorem B.6 in [Appendix B](LiB0102.html#1369) implies that  **** Our algorithm for multiplying large integers is still quadratic. The problem is that the algorithm does four multiplications on integers with half as many digits as the original integers. If we can reduce the numbers of these multiplications, we can obtain an algorithm that is better than quadratic. We do this in the following way. Recall that function *prod* must determine  and we accomplished this by calling function *prod* recursively four times to compute  If instead we set  then  This means we can get the three values in Expression 2.4 by determining the following three values:  To get these three values we need to do only three multiplications, while doing some additional linear-time additions and subtractions. The algorithm that follows implements this method. Algorithm 2.10: Large Integer Multiplication 2****Problem: Multiply two large integers, *u* and *v*. Inputs: large integers *u* and *v*. Outputs: *prod2*, the product of *u* and *v*. ``` large_integer prod2 (large_integer u, large_integer v) { large_integer x, y, w, z, r, p, q; int n, m; n = maximum (number of digits in u, number of digits in v); if (u == 0 || v == 0) return 0; else if (n <= threshold) return u 脳 v obtained in the usual way; else { m = [n/2]; x = u divide 10m; y = u rem 10m; w = v divide 10m; z = v rem 10m; r = prod2(x + y, w + z); p = prod2(x, w); q = prod2(y, z); return p 脳 102m + (r-p-q) 脳 10m+q; } } ``` **** **** Analysis of [Algorithm 2.10](#ch02ex25) Worst-Case Time Complexity (Large Integer Multiplications 2)We analyze how long it takes to multiply two *n*-digit integers. Basic operation: The manipulation of one decimal digit in a large integer when adding, subtracting, or doing **divide** 10m, **rem** 10m, or 脳 10m. Each of these latter three calls results in the basic operation being done *m* times. Input size: *n*, the number of digits in each of the two integers. The worst case happens when both integers have no digits equal to 0, because in this case the recursion ends only when the *threshold* is passed. We analyze this case. If *n* is a power of 2, then *x, y, w,* and *z* all have *n*/2 digits. Therefore, as [Table 2.4](#ch02table04) illustrates,  ****Table 2.4: Examples of the number of digits in x + y in [Algorithm 2.10](#ch02ex25)*n* *x* *y* *x + z* Number of Digits in *x +y* - - - - - - 4 10 10 20 2 =  4 99 99 198 3 =  8 1000 1000 2000 4 =  8 9999 9999 19,998 5 =  + 1 ****This means we can have the following input sizes for the given function calls:  Because *m* = *n*/2, the linear-time operations of addition, subtraction, **divide** 10*m*, **rem** 10*m*, and 脳 10*m* all have linear-time complexities in terms of *n*. Therefore, *W* (*n*) satisfies  where *s* is less than or equal to *threshold* and is a power of 2, because all the inputs in this case are powers of 2. For *n* not restricted to being a power of 2, it is possible to establish a recurrence like the previous one but involving floors and ceilings. Using an induction argument like the one in Example B.25 in [Appendix B](LiB0102.html#1369), we can show that *W* (*n*) is eventually nondecreasing. Therefore, owing to the left in equality in this recurrence and Theorem B.6, we have  Next we show that  To that end, let  Using the right inequality in the recurrence, we have  Because *W*(*n*) is nondecreasing, so is *W'*(*n*). Therefore, owing to Theorem B.6 in [Appendix B](LiB0102.html#1369),  and so  Combining our two results, we have  **** Using Fast Fourier Transforms, Borodin and Munro (1975) developed a 螛(*n*(lg *n*)2) algorithm for multiplying large integers. The survey article (Brassard, Monet, and Zuffelatto, 1986) concerns very large integer multiplication. It is possible to write algorithms for other operations on large integers, such as division and square root, whose time complexities are of the same order as that of the algorithm for multiplication.