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.


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 = 80779843 but my program display wrong result.


EDIT:

The title of this thread suppose to be Karatsuba Wrong Answer After 6 Decimal digits
Thanks.

[Peter_APIIT]

Problem solved.

Please delete my thread since the title is wrong.

[Hack]

Title changed.

Also, please post your solution. It might help others with the same or similiar problem.

Thanks.

[Peter_APIIT]

OK. Here is my solution.


#include <iostream>
#include <vector>
#include <algorithm>
#include <limits>
#include <cmath>
#include <cctype>

// ================================================
using namespace std;

typedef unsigned long 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 << "\n\nEnter First Number : ";
cin >> first;

while (cin.fail())
{
cin.clear();
cin.ignore(std::numeric_limits<int>::max(), '\n');

cout << "\n\nEnter First Number : ";
cin >> first;
}

cout << "Enter 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<ulong> 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)
{
ulong 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 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;
}

}



Thanks.

[Hack]

Thanks...and you should be able to change things like the title on threads you create with the Edit button.