Question

Write 6 big paragraphs Describing the algorithms that are actually used by modern computers to add, subtract, multiply and divide positive integers.

Answer 1

Addition - here is an algorithm for integer addition. In the algorithm, d is a carry bit. Our algorithms are given in a language that mixes mathematical notation and syntax similar to that found in many high-level computer languages. It should be straightforward to translate into a language such as C. Note that “:=” indicates a definition, and “←” indicates assignment. Line numbers are included if we need to refer to individual lines in the description or analysis of the algorithm.

Algorithm

. Let T be the number of different values taken by the data type representing the coefficients ai ,bi . (Clearly, β ≤ T, but equality does not necessarily hold, for example β = 109 and T = 232.) At step 3, the value of s can be as large as 2β − 1, which is not representable if β = T. Several workarounds are possible: either use a machine instruction that gives the possible carry of a_i + b_i , or use the fact that, if a carry occurs in ai + bi , then the computed Multiplication 3 sum – if performed modulo T – equals t := a_i +b_i −T < a_i ; thus, comparing t and ai will determine if a carry occurred. A third solution is to keep a bit in reserve, taking β ≤ T/2.

The subtraction code is very similar. Step 3 simply becomes s ← a_i−b_i+d, where d ∈ {−1, 0} is the borrow of the subtraction, and −β ≤ s < β. The other steps are unchanged, with the invariant A − B + din = dβⁿ + C. We use the arithmetic complexity model, where cost is measured by the number of machine instructions performed, or equivalently (up to a constant factor) the time on a single processor. Addition and subtraction of n-word integers cost O(n), which is negligible compared to the multiplication cost. However, it is worth trying to reduce the constant factor implicit in this O(n) cost. We shall see in §1.3 that “fast” multiplication algorithms are obtained by replacing multiplications by additions (usually more additions than the multiplications that they replace). Thus, the faster the additions are, the smaller will be the thresholds for changing over to the “fast” algorithms.

Multiplication:-

A nice application of large integer multiplication is the Kronecker–Schonhage ¨ trick, also called segmentation or substitution by some authors. Assume we want to multiply two polynomials, A(x) and B(x), with non-negative integer coefficients . Assume both polynomials have degree less than n, and the coefficients are bounded by ρ. Now take a power X = β ^k > nρ² of the base β, and multiply the integers a = A(X) and b = B(X) obtained by evaluating A and B at x = X. If C(x) = A(x)B(x) =, Ci xⁱ  we clearly have C(X) = Ci xⁱ   . Now since the c_i are bounded by nρ² < X, the coefficients c_i can be retrieved by simply “reading” blocks of k words in C(X). Assume for example that we want to compute (6x ⁵ + 6x ⁴ + 4x ³ + 9x ² + x + 3)(7x ⁴ + x ³ + 2x ² + x + 7), with degree less than n = 6, and coefficients bounded by ρ = 9. We can take X = 103 > nρ2 , and perform the integer multiplication 6006004009001003 × 7001002001007 = 42048046085072086042070010021, from which we can read off the product 42x ⁹ + 48x ⁸ + 46x ⁷ + 85x ⁶ + 72x ⁵ + 86x ⁴ + 42x ³ + 70x ² + 10x + 21.Conversely, suppose we want to multiply two integers a= 0<=i<n ^b_iβⁱ and b= 0<=j<n ^b_j  β^{j .} Multiply the polynomials

A(x)= 0<=i<n ^b_iβⁱ and B(x)= 0<=j<n ^b_j  β^j j , obtaining a polynomial C(x), then evaluate C(x) at x = β to obtain ab. Note that the coefficients of C(x) may be larger than β, in fact they may be up to about nβ² . For example, with a = 123, b = 456, and β = 10, we obtain A(x) = x ² + 2x + 3, B(x) = 4x ² + 5x + 6, with product C(x) = 4x ⁴ +13x ³ +28x ² +27x+18, and C(10) = 56088. These examples demonstrate the analogy between operations on polynomials and integers, and also show the limits of the analogy. A common and very useful notation is to let M(n) denote the time to multiply n-bit integers, or polynomials of degree n − 1, depending on the context. In the polynomial case, we assume that the cost of multiplying coefficients is constant; this is known as the arithmetic complexity model, whereas the bit complexity model also takes into account the cost of multiplying coefficients, and thus their bit-size.

Division:

Many algorithms have been developed for implementing division in hardware. These algorithms differ in many aspects, including quotient convergence rate, fundamental hardware primitives, and mathematical formulations. The paper presents a taxonomy of division algorithms which classifies the algorithms based upon their hardware implementations and impact on system design. Division algorithms can be divided into five classes: digit recurrence, functional iteration, very high radix, table look-up, and variable latency. Many practical division algorithms are hybrids of several of these classes. These algorithms are explained and compared. It is found that, for low-cost implementations where chip area must be minimized, digit recurrence algorithms are suitable. An implementation of division by functional iteration can provide the lowest latency for typical multiplier latencies. Variable latency algorithms show promise for simultaneously minimizing average latency while also minimizing area.

Generally, the exact quotient of two integers is a fractional number. One can stop the division process at any stage, and return the approximate quotient and the remainder. It will be convenient to assume that the quotient is expanded as q = q0 + q_-1β ⁻¹ + q₋₂β ⁻² + . . . , (18) where 0 ≤ qj < β are the digits. Some division algorithms use generalized digits that satisfy a more relaxed condition such as −β < qj < β, cf. (6) and (8). In order to have the quotient in the above form, we assume that a and b are positive and normalized, such that a = a0 + a₋₁β ⁻¹ + a₋₂β ⁻² + . . . , b = b0 + b₋₁β ⁻¹ + b₋₂β ⁻² + . . . , (19) with a0 > 0 and b0 > 0, that is, we assume that 1 ≤ a < β and 1 ≤ b < β. This normalization can be achieved by pre-scaling, and one needs to do the corresponding adjustments to the final quotient after the division has been done.

Restoring division. The division algorithms we discuss here are only effective for small values of the radix β, and for simplicity, we consider the case β = 2 first. The first algorithm is called the restoring division, and works as follows. We compute a − b, and if a − b ≥ 0, then we set q0 = 1 and a ′ = a − b. In this case, since a < 2 and b ≥ 1, we have a ′ = a − b < 1 ≤ b. On the other hand, if a − b < 0, then we set q0 = 0 and a ′ = a. In this case, we also have a ′ = a < b. Now we apply the same process to a ′ and b ′ = 1 2 b, to compute the digit q−1. This process is repeated until the partial remainder becomes small enough. More formally, the algorithm sets α0 = a, and for j = 0, 1, . . ., performs

(αj+1, q−j) =(αj − 2 −j b, 1) if αj − 2 −j b ≥ 0, (αj , 0) if αj − 2 ^−j b < 0. (20)

The quantities αj are called partial remainders. We have 0 ≤ α₀ = a < 2 ≤ 2b. Taking 0 ≤ αj < 2^1−j b as the induction hypothesis, we have 0 ≤ α_j+1 = α_j − 2 ^−j b < 2 ^1−j b -2 ^−j b = 2 ^−j b, (21)

for the first branch of (20), while for the second branch 0 ≤ α_j+1 = α_j < 2 ^−j b holds trivially. By construction, we have α_j = q₋j2 ^−j b + α_j+1, (22) and so a = α₀ = q₀b + α₁ = q₀b + q−12 −1 b + α₂ = . . . = q₀b + q₋₁2 ⁻¹ b + . . . + q^_−n2 ⁻ⁿ b + α_n+1 = qb + α_n+1, (23)

where q = q₀ + q₋₁2 ⁻¹ + . . . + q_−n2 ⁻ⁿ . In light of the bound 0 ≤ α_n+1 = αj < 2 ⁻ⁿ b, this implies 0 ≤ a b − q < 2 −n , (24)

meaning that the digits of q are precisely the first n + 1 digits of the quotient a/b. Since the algorithm generates one correct bit per step, it terminates after n steps, where n is how many quotient digits we need. Furthermore, each step costs us a bit shift, a subtraction, and a comparison operation.In practical implementations of (20), it is more convenient to scale up the partial remainders, than to scale down the divisor. Thus, putting α_j = 2 ⁻j r_j into (20), we get the recurrence (r_j+1, q_−j) = (2(rj − b), 1) if rj − b ≥ 0, (2rj , 0) if rj − b < 0. (25) for j = 0, 1, . . .. On the other hand, the scaling α_j = 2 ^1−j r^j would give (r_j+1, q_−j) = (2rj − b, 1) if 2rj − b ≥ 0, (2rj , 0) if 2rj − b < 0, (26) for j = 0, 1, . . ., which is more standard in the literature. Note that in the latter case, the initialization becomes r₀ = 2 ⁻¹a (or equivalently, b is replaced by 2b). If one computes the difference 2r_j −b and overwrites its value into 2r_j , then in case 2r_j −b < 0, one has to “restore” the value 2r_j by adding b back. This is the reason for the name “restoring division.”