#include #include #include using namespace std; inline int numberOfDigits(unsigned long long n) { return log10(n) + 1; } inline int halfOfDigits(unsigned long long input) { int digits = numberOfDigits(input); return digits/2 + digits%2; } inline unsigned long long lastDigits(unsigned long long input) { int power; unsigned long long output; power = halfOfDigits(input); return input % (unsigned long long) pow(10, power); } inline unsigned long long firstDigits(unsigned long long input) { int power; unsigned long long output; power = halfOfDigits(input); output = input / (unsigned long long)pow(10, power); return output; } inline unsigned long long caratsuba(unsigned long long a, unsigned long long b) { if(numberOfDigits(a) < 5) { return a*b; } int power = halfOfDigits(a); unsigned long long aFirstDigits, bFirstDigits, aLastDigits, bLastDigits, helpA, helpB; unsigned long long output1, output2, output3; aFirstDigits = firstDigits(a); bFirstDigits = firstDigits(b); aLastDigits = lastDigits(a); bLastDigits = lastDigits(b); helpA = aFirstDigits + aLastDigits; helpB = bFirstDigits + bLastDigits; output1 = caratsuba(aFirstDigits, bFirstDigits); output2 = caratsuba(aLastDigits, bLastDigits); output3 = caratsuba(helpA, helpB); return output1*((unsigned long long)pow(10, (2*power))) + ((unsigned long long)pow(10, power))*(output3 - output1 - output2 )+ output2; } int main() { unsigned long long n, m; while (true) { cout << "Please give 2 integer numbers with the same length!" << endl; if (cin.peek() == '-') { cout << "The given integers should be positiv!" << endl; cin.clear(); cin.ignore(10000, '\n'); } else { cin >> n; cin >> m; if (cin.fail()) { cout << "The given string is not an unsigned integer!" << endl; cin.clear(); cin.ignore(10000, '\n'); } else { if (numberOfDigits(n) != numberOfDigits(m)) cout << "The length of the given integers are not equal!" << endl; else { cout << n << " * " << m << " = " << caratsuba(n, m) << endl; } } } } return 0; }

Caratsuba Algorithm