Karatsuba Wrong Answer After 6 Decimal digits

[Peter_APIIT]

Hello to all, i have code karatsuba but it is not compute correctly after 6 decimal digits.

#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;
	}

}
// =============================================

For example, 123456 * 654321 * 80779853 but my program display wrong answer.

Thanks.

[ArkM]

Take into account that

123456 * 654321 * 80779853  == 6525384681074833728

but std::numeric_limits<long>::max() is equal to 2147483647 on 32-bit processors (integer overflow is not detected).
Try long long type (it's supported by modern compilers now), its max value is 9223372036854775807.
Otherwise try one of big int class libraries...

[Peter_APIIT]

Why will causing this value although it can fit that value ?

Do you have any good big integer library ?

I need those supports up to 512 bits ?

Thanks

[ArkM]

No, I have not bigint libraries. I have no need in these libraries.
Have you ever seen the phrase "Search Google"?
Try this (for bigint library) and you will get lots of links, for example (from the 1st page):
http://mattmccutchen.net/bigint/
http://en.wikipedia.org/wiki/Arbitrary-precision_arithmetic
http://math.libtomcrypt.com/
and many many others...

[Peter_APIIT]

I do searching in google but i not sure which one is easy, popular.

How about GNU MP ?

Thanks.

[ArkM]

It seems you don't understand that no need in Karatsuba algorithm while you are trying to get unsigned long results: use built-in arithmetic - that's all. But if the result is greater than unsigned long max value you can't return unsigned long value from Karatsuba function! No need in Karatsuba algorithm if you have bigint library: there is bigint multiplication in every such library.

Therefore all your codes are senseless from the beginning. Start your design from the big int representation. See, for example, http://en.wikipedia.org/wiki/Karatsuba_algorithm .

Apropos: the simplest (but ineffective) arbitrary precision integer representation is a simple text string. Try to implement Karatsuba algorithm for this representation.

[Peter_APIIT]

Thanks for your help. In cases, iI don't want to create my own big int class since there are many outside. I just want some big int library which is template based, easy to use.
For instance,

bigInt<150> aBigInt;
150 is the number of bits.