| Peter_APIIT |
05-02-2009 05:18 AM |
Karatsuba Wrong Answer After 6 digits Decimal
Hello to all, i have code karatsuba but it is not compute correctly after 6 decimal digits.
Code:
#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;
}
}
// =============================================
Thanks. |
