Question: The KaratsubaOfman algorithm provides a striking example of how the Divide and Conquer technique can achieve an asymptotic speedup over an ancient algorithm. The classroom
The KaratsubaOfman algorithm provides a striking example of how the Divide and Conquer technique can achieve an asymptotic speedup over an ancient algorithm. The classroom method of multiplying two n-digit integers requires ?(n 2 ) digit operations. Please convert the pseudocode into C++ source code. Also explain why this is the same as the pseudocode.
| procedure karatsuba(num1, num2) | |
| if (num1 < 10) or (num2 < 10) | |
| return num1*num2 | |
| /* calculates the size of the numbers */ | |
| m = max(size_base10(num1), size_base10(num2)) | |
| m2 = m/2 | |
| /* split the digit sequences about the middle */ | |
| high1, low1 = split_at(num1, m2) | |
| high2, low2 = split_at(num2, m2) | |
| /* 3 calls made to numbers approximately half the size */ | |
| z0 = karatsuba(low1,low2) | |
| z1 = karatsuba((low1+high1),(low2+high2)) | |
| z2 = karatsuba(high1,high2) | |
For example, ? m = max(size_base10(num1), size_base10(num2)) may not be valid in C++. How do you make it valid in C++?
Step by Step Solution
There are 3 Steps involved in it
Get step-by-step solutions from verified subject matter experts
