KaratsubaMultiplication.cpp

// Author: Aakriti Sharma
// Date:   3rd August 2020
#include<iostream>
#include<string>
#include<algorithm>


// Funtion to compare if the number of digits are equal or not
// if not then add string of zeros in from of the smaller number
void addZeros(std::string* num1, std::string* num2) {
	if (num1->length() > num2->length()) {
		std::string zeros = std::string(num1->length() - num2->length(), '0'); // string of zeros
		*num2 = zeros + *num2;
	}
	if (num1->length() < num2->length()) {
		std::string zeros = std::string(num2->length() - num1->length(), '0'); // string of zeros
		*num1 = zeros + *num1;
	}
}

// Function to subtract num2 from num1 
// assumption: num1 is greater than num2
std::string subNumbers(std::string num1, std::string num2) {
	addZeros(&num1, &num2);
	int len = num1.length();

	std::string string_diff;
	int carry = 0;
	
	for (int i = 0; i < len; i++) {
		std::string digit1, digit2;
		digit1 = num1[len - i - 1];
		digit2 = num2[len - i - 1];

		int diff = stoi(digit1) - stoi(digit2) - carry;
		if (diff < 0) {
			diff += 10;
			carry = 1;
		}
		else
			carry = 0;
		
		string_diff = std::to_string(diff % 10) + string_diff;
	}
		
	return string_diff.erase(0, std::min(string_diff.find_first_not_of('0'), string_diff.length() - 1));
}

// Function to add 2 numbers
std::string addNumbers(std::string num1, std::string num2) {
	addZeros(&num1, &num2);
	int len = num1.length();

	std::string string_sum;
	int carry = 0;

	for (int i = 0; i < len; i++) {
		std::string digit1, digit2;
		digit1 = num1[len - i - 1];
		digit2 = num2[len - i - 1];

		int sum = carry + stoi(digit1) + stoi(digit2);
		carry = sum / 10;

		string_sum = std::to_string(sum % 10) + string_sum;
	}

	if (carry)
		string_sum = std::to_string(carry) + string_sum;

	return string_sum.erase(0, std::min(string_sum.find_first_not_of('0'), string_sum.length() - 1));;
}

// Function to multiply two numbers with help of karatsuba algorithm
std::string karatsubaMultiplication(std::string num1, std::string num2) {
	
	addZeros(&num1, &num2);
	unsigned int digits = num1.length();

	// Base condition
	// return the product directly if the values of x or y is less than 100
	if (digits <= 1) {
		return std::to_string(stoi(num1) * stoi(num2)); 
	}
	
	// if the values are greater than 9

	std::string lhs1 = num1.substr(0, digits / 2);  // calculating first half of the number
	std::string rhs1 = num1.substr(digits / 2, 2 * (digits - digits / 2));  // calculating second half of the number
	std::string lhs2 = num2.substr(0, digits / 2);  // calculating first half of the number
	std::string rhs2 = num2.substr(digits / 2, 2*(digits - digits/2));  // calculating second half of the number
	
	std::string prod1 = karatsubaMultiplication(lhs1, lhs2);  // 1st recursion call 
	std::string prod2 = karatsubaMultiplication(rhs1, rhs2);  // 2nd recursion call
	std::string prod3 = karatsubaMultiplication(addNumbers(lhs1, rhs1), addNumbers(lhs2, rhs2)); // 3rd call
	prod3 = subNumbers(prod3, addNumbers(prod1, prod2));
	
	prod1 = prod1 + std::string(2 * (digits - digits / 2), '0');
	prod3 = prod3 + std::string(digits - digits / 2, '0');

	// return the final product
	return addNumbers(addNumbers(prod1, prod2), prod3);
}

int main() {
	std::string num1, num2;

	//num1 = "3141592653589793238462643383279502884197169399375105820974944592";
	//num2 = "2718281828459045235360287471352662497757247093699959574966967627";
	std::cout << "Enter 2 numbers: ";
	std::cin >> num1 >> num2;

	std::cout << "Product:\t" << karatsubaMultiplication(num1, num2);
}