ANALYSIS OF ALGORITHMS Complete the two large integers multiplication program us

Question

ANALYSIS OF ALGORITHMS

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 = A_1 A_2 and B = B_1 B_2 (where A and B are n-digit, A_1, A_2, B_1, B_2 are n/2-digit numbers), A * B = A_1 * B_1 10^n + (A_1 * B_2 + A_2 * B_1) 10^n/2 + A_2 * B_2 A small example: A * B where A = 2135 and B = 4014 In this case, A_1 =21, A_2=35, B_1 = 40, B_2 = 14, and n = 4 So, A * B = 21 * 40 10^2 + 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

Algorithm:

BigInteger multiply(BigInteger a, BigInteger b) {
   int n = max(number of digits in a, number of digits in b)
   if(n == 1) {
   return a.intValue() * b.intValue();
   } else {
   BigInteger aR = bottom

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

---

---

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