LinuxQuestions.org
Visit Jeremy's Blog.
Go Back   LinuxQuestions.org > Forums > Non-*NIX Forums > Programming
User Name
Password
Programming This forum is for all programming questions.
The question does not have to be directly related to Linux and any language is fair game.

Notices


Reply
  Search this Thread
Old 05-02-2009, 05:18 AM   #1
Peter_APIIT
Member
 
Registered: Dec 2006
Posts: 582

Rep: Reputation: 31
Thumbs up 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.
 
  


Reply


Thread Tools Search this Thread
Search this Thread:

Advanced Search

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is Off
HTML code is Off



Similar Threads
Thread Thread Starter Forum Replies Last Post
I need help finding out last 4 digits s_b Linux - Newbie 1 10-16-2008 08:16 AM
BASH - convert single digits to double digits. rickenbacherus Programming 7 05-07-2008 06:53 AM
The wrong way to answer a question. rblampain LQ Suggestions & Feedback 9 11-11-2007 05:01 AM
Getting the wrong answer DavidMcCann LQ Suggestions & Feedback 9 05-09-2007 04:22 AM

LinuxQuestions.org > Forums > Non-*NIX Forums > Programming

All times are GMT -5. The time now is 05:23 AM.

Main Menu
Advertisement
My LQ
Write for LQ
LinuxQuestions.org is looking for people interested in writing Editorials, Articles, Reviews, and more. If you'd like to contribute content, let us know.
Main Menu
Syndicate
RSS1  Latest Threads
RSS1  LQ News
Twitter: @linuxquestions
Open Source Consulting | Domain Registration