Complete the two large integers multiplication program using the divide and conq

Question

Complete the two large integers multiplication program using the divide and conquer algorithm discussed in the class. The algorithm has been discussed in the class and a short description is as follows. In general, if A AiA2 and B digit numbers), BiB2 (where A and B are n-digit, A, A2, B1, B2are n/2- A * B = A! * B1-10n + (A1 * B2 + Az * B1) . 10n/2 + A2 * B2 A small example: A * B where A-2135 and B = 4014 In this case, A1-21, A2-35, B1-40, B2-14, and n-4 So, A * B 21 * 40-104 + (21+14 + 35 * 40) .102 + 35 * 14 Recursively, the algorithm computes 21 40, 21 14,35 40, 35 14 following the above formula. Please write a program that takes any two large arbitrary integers (up to 256 digits per each number) as inputs, apply the divide-and-conquer algorithm of multiplication, and print the results of the multiplication of the two integers.

Explanation / Answer

multiply(a[1..p], b[1..q], base)                  // Operands containing rightmost digits at index 1
    tot = 0
    for ri = 1 to p + q - 1                       //For each digit of result
        for bi = MAX(1, ri - p + 1) to MIN(ri, q) //Digits from b that need to be considered
            ai = ri bi + 1                      //Digits from a follow "symmetry"
            tot = tot + (a[ai] * b[bi])
        product[ri] = tot mod base
        tot = floor(tot / base)
    product[p+q] = tot mod base                   //Last digit of the result comes from last carry
    return product

multiply(a[1..p], b[1..q], base)                            // Operands containing rightmost digits at index 1
product = [1..p+q]                                        //Allocate space for result
for b_i = 1 to q                                          // for all digits in b
    carry = 0
    for a_i = 1 to p                                        //for all digits in a
      product[a_i + b_i - 1] += carry + a[ai] * b[bi]
      carry = product[ai + bi - 1] / base
      product[a_i + b_i - 1] = product[ai + bi - 1] mod base
    product[b_i + p] += carry                               // last digit comes from final carry
return product

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.