#include <iostream>
#include <vector>
#include <algorithm>
#include <limits>
#include <cmath>
#include <cctype>
 
// ================================================
using namespace std;
 
typedef unsigned long ulong;
 
void userInput(ulong&, ulong&);
int numberLength(ulong);
 
ulong leftSplit(ulong, int);
ulong rightSplit(ulong, int);
 
int numberPower(const ulong&, const ulong&, const ulong&);
ulong Karatsuba(const ulong&, const ulong&);
 
const int MINLENGTH = 5;
 
// =============================================
int main(int argc, char *argv[])
{
	ulong first(0), second(0);
 
 while (1)
 {
	 userInput(first, second);
	 cout << "The result of " << 
		 first << " * " << second << " : "
		 << Karatsuba(first, second);
 
 }
	return 0;
}
// =============================================
void userInput(ulong& first, ulong& second)
{
	cout << "\nEnter First Number : ";
	cin >> first;
 
	while (cin.fail())
	{
		cin.clear();
		cin.ignore(std::numeric_limits<int>::max(), '\n');
 
		cout << "\nEnter First Number : ";
		cin >> first;
	}
 
	cout << "\nEnter Second Number : ";
	cin >> second;
 
	while (cin.fail())
	{
		cin.clear();
		cin.ignore(std::numeric_limits<int>::max(), '\n');
 
		cout << "\nEnter Second Number : ";
		cin >> second;
	}
}
// =============================================
int numberLength(ulong number)
{
	int len(0);
 
	// Check length of integer algorithm
	// * 10 = To shift left 1 digit in number
	// % 10  = To get last digit of number
	while (number >= 1)
	{
		number /= 10;
		++len;
	}
 
	return len;
}
// =============================================
ulong leftSplit(ulong number, int length)
{
	int middle = length / 2;
	vector<int> remainder(0);
 
	// To get most significant digit
	while (number >= 10)
	{
		remainder.push_back(number % 10);
		number /= 10;
	}
 
	std::reverse(remainder.begin(), remainder.end());
 
	ulong result(number);int remLoop(0);
	for (int loop = 0;loop < middle - 1;++loop)
	{
		if (remLoop < static_cast<int>(remainder.size()))
		{
			result = result * 10 + remainder[remLoop];
		}
		++remLoop;
	}
 
	return result;
}
// =============================================
ulong rightSplit(ulong number, int length)
{
	int remainder(0), multiply(1);
	ulong result(0);
	for (int loop = 0; loop < length;++loop)
	{
		remainder = number % 10;
		number /= 10;
		result += remainder * multiply ;
		multiply *= 10;
	}
 
	return result;
}
// =============================================
int numberPower(const ulong& first, const ulong& x1, 
								const ulong& y1)
{
	int lengthPower(1);
 
	const int base(10);
 
	while (first - y1 != (x1 * (pow(static_cast<double>(base), 
		static_cast<int>(lengthPower)))) )
	{
		++lengthPower;
	}
 
	return lengthPower;
}
// =============================================
ulong Karatsuba(const ulong& first, const ulong& second)
{
	if (first != 0 && second != 0)
	{
		if (numberLength(first) > MINLENGTH 
			&& numberLength(second) > MINLENGTH)
		{
			ulong x1 = leftSplit(first, numberLength(first));
			ulong	y1 = leftSplit(second, numberLength(second));
 
			ulong x0 = rightSplit(first, numberLength(first) - numberLength(x1));
			ulong y0 = rightSplit(second, numberLength(second) - numberLength(y1));
 
			int lengthPower = numberPower(first, x1, x0);
 
			unsigned long X = Karatsuba(x1, y1);
			int length = numberLength(X);
			ulong Y = Karatsuba(x0, y0);
			ulong Z = Karatsuba(x1 + x0, y1 + y0);
			Z = Z - X - Y;
 
			return (X * static_cast<unsigned long>(pow(10.0, 2.0 * lengthPower))) +  
				(Z * static_cast<unsigned long>(pow(10.0, lengthPower))) + Y;
		}
		else
		{
			return first * second;
		}
	}
	else
	{
		return 0;
	}
 
}
// =============================================

123456 * 654321 * 80779853  == 6525384681074833728