Question

C++ please

Write code to implement the Karatsuba multiplication algorithm in the file linked in Assignment 2 (karatsuba.cpp) in Canvas (please do not rename file or use cout/cin statements in your solution). As a reminder, the algorithm uses recursion to produce the results, so make sure you implement it as a recursive function. Please develop your code in small The test program (karatsuba_test.cpp) is also given. PLEASE DO NOT MODIFY THE TEST FILE.

KARATSUBA.CPP

/* Karatsuba multiplication */

#include <iostream>

using namespace std;

int numDigits(int num);

int pow10(int n);

int karatsuba(int x, int y) {

    

    

}

// Helper function - returns number of digits

int numDigits(int num) {

    

}

// Helper function - integer exponentiation

int pow10(int n) {

    

}

KARATSUBA_TEST.CPP

/* Karatsuba multiplication */

#include

using namespace std;

int karatsuba(int x, int y);

int main() {

    cout << "7*6 = " << karatsuba(7, 6) << endl;

    cout << "15*15 = " << karatsuba(15, 15) << endl;

    cout << "6*13 = " << karatsuba(6, 13) << endl;

    cout << "51*49 = " << karatsuba(51, 49) << endl;

    cout << "111*111 = " << karatsuba(111, 111) << endl;

    cout << "5678*1234 = " << karatsuba(5678, 1234) << endl;

    cout << "12345678*1 = " << karatsuba(12345678, 1) << endl;

    cout << "12345678*0 = " << karatsuba(12345678, 0) << endl;

    return 0;

}

Answer 1

Code to implement the Karatsuba multiplication algorithm :-

int karatsuba(int x,int y)

{

int xLength=getLength(x);

int yLength=getLength(y);

int N = (int) (fmax(xLength,yLength));   // the bigger of the two lengths

if(N<10)   // if the max length is small it's faster to just flat out multiply the two nums

return x*y;

N = (N/2) + (N%2);   //max length divided and rounded up

int multiplier = pow(10,N);

int b = x/multiplier;

int a = x - (b * multiplier);

int d = y / multiplier;

int c = y - (d * N);

int z0 = karatsuba(a,c);

int z1 = karatsuba(a+b,c+d);

int z2 = karatsuba(b,d);

return z0 + ((z1 - z0 - z2) * multiplier) + (z2 * (int) (pow(10,2*N)));

}