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.

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 …

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):

## All 6 Replies

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...

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

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

Thanks.

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.

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.

Be a part of the DaniWeb community

We're a friendly, industry-focused community of 1.20 million developers, IT pros, digital marketers, and technology enthusiasts learning and sharing knowledge.