Answer to Question #265714 in C++ for acky_1

Question

Write a C++ program which:

• Prompts user to enter two large integer numbers (x, y). Both numbers must be more

than 4 digits and less than 10 digits (do input validation, don’t use strings). The entered

numbers could be negative or positive. For example: 820778 and -58712979 where x is

6-digit positive number and y is 8-digit negative number.

• Make a function called Karatsuba() which takes these two integers and returns the

multiplication result using Karatsuba algorithm. You might need to make another helper

function called getDigits() which will get an integer as input and returns number of digits

of that integer. getDigits() will help you find the value of m and Bm.

• Display result in the main function.

Answer 1

#include <iostream>
#include <math.h>
using namespace std;
int getLength(long long value) {
	int counter = 0;
	while (value != 0) {
		counter++;
		value /= 10;
	}
	return counter;
}

long long multiply(long long x, long long y) {
	int xLength = getLength(x);
	int yLength = getLength(y);
	// the bigger of the two lengths
	int N = (int)(fmax(xLength, yLength));
	// if the max length is small it's faster to just flat out multiply the two nums
	if (N < 10)
	return x * y;
	//max length divided and rounded up
	N = (N/2) + (N%2);
	long long multiplier = pow(10, N);

	long long b = x/multiplier;
	long long a = x - (b * multiplier);
	long long d = y / multiplier;
	long long c = y - (d * N);

	long long z0 = multiply(a,c);
	long long z1 = multiply(a + b, c + d);
	long long z2 = multiply(b, d);

    return z0 + ((z1 - z0 - z2) * multiplier) + (z2 * (long long)(pow(10, 2 * N)));
}
int main() {
	// two numbers
	long long a = 2406994;
	long long b = 2328563;
	cout << multiply(a,b) << endl;
	return 0;
}