Karatsuba Algorithm - Not Fully Understand and Don't Know how to Implement It

 DevX Home Today's Headlines   Articles Archive   Tip Bank   Forums

# Thread: Karatsuba Algorithm - Not Fully Understand and Don't Know how to Implement It

1. Registered User
Join Date
May 2007
Posts
843

## Karatsuba Algorithm - Not Fully Understand and Don't Know how to Implement It

Hello to all C++ expect programmer, i would like to create a function that multiply two integer which stored in char * or string.

1. compute x1y1, call the result A
2. compute x2y2, call the result B
3. compute (x1 + x2)(y1 + y2), call the result C
4. compute C - A - B; this number is equal to x1y2 + x2y1.

BigInteger multiply(BigInteger a, BigInteger b) {
int n = max(number of digits in a, number of digits in b)
if(n == 1) {
return a.intValue() * b.intValue();
} else {
BigInteger aR = bottom n/2 digits of a;
BigInteger aL = top remaining digits of a;
BigInteger bR = bottom n/2 digits of b;
BigInteger bL = top remaining digits of b;
BigInteger x1 = Multiply(aL, bL);
BigInteger x2 = Multiply(aR, bR);
BigInteger x3 = Multiply(aL + bL, aR + bR);
return x1 * pow(10, n) + (x3 - x1 - x2) * pow(10, n / 2) + x2;
}
}
As far as i know, 1234 * 4567 will be split into two parts which are
A(1) = 12, A(2) = 34, B(1) = 45, B(2) - 67;

First, A = A(1) * B(1), then
B= B(1), B(2), then
C=( A(1) + B(1) * B(1) + B(2) );

The question is i don't understand the last statement.
Code:
` return x1 * pow(10, n) + (x3 - x1 - x2) * pow(10, n / 2) + x2;`
What this does ?

This is my code so far :

Code:
```/*
Polynomial is a expression with non negative
integer power, 1 or more variable and costant(coefficient)

Polynomial is important for signal processing,
crytography and coding theory. Polynomial is core
of multiplication algorithm in computing

Karatsuba algorithm consits of many branches
and optmization such as

1. KA for Degree-1 Polynomials - x ^ 1
2. Recursive KA for Polynomials of Degree 2i ¡ 1
- Efficient for coeficient power of 2
3. One-Iteration KA for Polynomials of Arbitrary Degree
4. KA for Degree-2 Polynomials - X ^ 2
5. KA for Polynomials of Arbitrary(Any) Degree

Ratio between long multiplication and karatsuba > 3, then
use KA for Degree-2 Polynomials

Improvement of KA with dummy coefficient = 0

2.

1. compute x1y1, call the result A
2. compute x2y2, call the result B
3. compute (x1 + x2)(y1 + y2), call the result C
4. compute C - A - B;
this number is equal to x1y2 + x2y1.

BigInteger multiply(BigInteger a, BigInteger b)
{
int n = max(number of digits in a,
number of digits in b)
if(n == 1)
{
return a.intValue() * b.intValue();
}
else
{
BigInteger aR = bottom n/2 digits of a;
BigInteger aL = top remaining digits of a;

BigInteger bR = bottom n/2 digits of b;
BigInteger bL = top remaining digits of b;

BigInteger x1 = Multiply(aL, bL);
BigInteger x2 = Multiply(aR, bR);
BigInteger x3 = Multiply(aL + bL, aR + bR);

return x1 * pow(10, n) + (x3 - x1 - x2) * pow(10, n / 2) + x2;
}
}

*/

/*
MS Calling Convention
__cdecl, __fastcall, __stdcall;

*/

#include <iostream>
#include <string>
#include <sstream>
#include <vector>

using std::cout;
using std::cin;
using std::string;
using std::stringstream;
using std::vector;

#define SIZE 50

// ------------------------------------------------

void MultiplyBigInteger(char *, char *);
int length(char *);
void divide(int, int *, int *);

// ------------------------------------------------
int main(int argc, char *argv[])
{
char *firstNumber = "99999",
*secondNumber = "99999";

MultiplyBigInteger(firstNumber, secondNumber);

return 0;
}
// ------------------------------------------------
void MultiplyBigInteger(char *firstNumber, char *secondNumber)
{
int firstLength = length(firstNumber);
int secondLength = length(secondNumber);
int *firstLeftLength = 0, *firstRightLength = 0,
*secondLeftLength = 0, *secondRightLength = 0;

char *firstRight = 0, *firstLeft =0,
*secondRight = 0, *secondLeft = 0;

divide(firstLength, firstLeftLength, firstRightLength);
divide(secondLength, secondLeftLength, secondRightLength);

if (firstLength == 1 && secondLength == 1)
{
}
else
{
//		MultiplyBigInteger(
}
}
// ------------------------------------------------
int length(char *number)
{
int length = 0;
for (int loop=0;number[loop] != '\0';loop++)
{
*(number + loop);
length++;
}
return length;
}
// ------------------------------------------------
void divide(int length, int *leftLength,
int *rightLength)
{
if (length % 2 != 0)
{
*leftLength = (length % 2) + 1;
*leftLength = (length % 2);
}
else
{
*leftLength = length / 2;
*rightLength = length / 2;
}
}```
I not asking you all do for me but explanation and guideline is more than enough.

2. Registered User
Join Date
Jan 2005
Location
UK
Posts
604
Code:
` return x1 * pow(10, n) + (x3 - x1 - x2) * pow(10, n / 2) + x2;`
pow(10,n) is the n-th power of ten, basially a 1 with n 0-s
pow(10,n) for n==4 equals 10*10*10*10 = 10000

in a similar fashion:
pow(2,n) == 2*2*2*...*2 (n-times)
pow(2,8) = 256
you can do pow(x,n) for any x a real number in much the same way,
pow(sqrt(2),3) = sqrt(2)*sqrt(2)*sqrt(2)
you can also do pow(x,y) for y real numbers. but that can not be written as a simple product

The rest of your formula in the return statement is pretty straight forward, so I don't think you asked about that.

3. Senior Member
Join Date
Dec 2003
Posts
3,366
pow is terribly slow by the way, use a lookup table of the powers of 10. Since this is a simple set of values, it can be exploited that a floating point number can store exponents efficiently to take you well into the 10^200 or more range (I forget how far you can go off the top of my head).

Also, the big int thing can be vastly improved if you extend normal binary math instead of trying to do base 10 math on chars. IE a 100 byte integer in the format of FA124.... 054AF hex is much smaller (fewer operations) to multiply etc than 1233456...................................555690 as text... you can see this even with a byte (FF is less to process than 255 in a loop, and the difference bettwen base 10 and base 16 in number of bytes grows very fast (8 bytes becomes over 20 bytes, more than double the size).

Just some thoughts if you plan do do a LOT of numbers or very, very large ones.

4. Registered User
Join Date
May 2007
Posts
843
The rest of your formula in the return statement is pretty straight forward, so I don't think you asked about that.

I understand what is pow() function and i dont' know why need to to x1 * pow(10, n) ? I looking for the logic behind formula.

I not interest in doing math with base 16 since jonnin is memory consumption is high.

5. Registered User
Join Date
May 2007
Posts
843
I think i understand how it works under formula but not under coding since recursion is easy to implement but difficult to understand.

Let me explain this to others as well:

a1a0 - Divide into two parts
b1b0 - Divide into two parts

q_0 = a_0b_0 (p0)
q_1 = (a_0+a_1)(b_0+b_1) (p1) Human calculation
q_2 = a_1b_1. (p2)

Reassign to another variable q0, q1 and q2;
Then rewrite above statement as below:

q_1 = p_1+p_0+p_2.
= a0b0 + a0b1 + a1b0 + a1b1;
= p0 + p2 + p2

-p1 = -q1 + p0 + p2
-p1 = -q1 + q0 + q2
p1 = q1 - q0 - q2;

Therefore, it only needs three multiplication only which are

q_0 = a_0b_0 (p0)
q_1 = (a_0+a_1)(b_0+b_1) (p1)
q_2 = a_1b_1. (p2)
rather than

a1a0
b1b0

b0 * a0

b0 * a1
b1 * a0
b1 * a1

and minus the over multiplication of q0 and q2;

Finally, this form the formula like this:

return x1 * pow(10, n) + (x3 - x1 - x2) * pow(10, n / 2) + x2;

My concern is how it works under code(recursion). I cannot see how it works unless i went through debugging process.

I hope GOD will bless you all.

6. Registered User
Join Date
May 2007
Posts
843
I have coded some code so far as below :

Code:
```/*
Polynomial is a expression with non negative
integer power, 1 or more variable and costant(coefficient)

Polynomial is important for signal processing,
crytography and coding theory. Polynomial is core
of multiplication algorithm in computing

Karatsuba algorithm consits of many branches
and optmization such as

1. KA for Degree-1 Polynomials - x ^ 1
2. Recursive KA for Polynomials of Degree 2i &#161; 1
- Efficient for coeficient power of 2
3. One-Iteration KA for Polynomials of Arbitrary Degree
4. KA for Degree-2 Polynomials - X ^ 2
5. KA for Polynomials of Arbitrary(Any) Degree

Ratio between long multiplication and karatsuba > 3, then
use KA for Degree-2 Polynomials

Improvement of KA with dummy coefficient = 0

2.

1. compute x1y1, call the result A
2. compute x2y2, call the result B
3. compute (x1 + x2)(y1 + y2), call the result C
4. compute C - A - B;
this number is equal to x1y2 + x2y1.

BigInteger multiply(BigInteger a, BigInteger b)
{
int n = max(number of digits in a,
number of digits in b)
if(n == 1)
{
return a.intValue() * b.intValue();
}
else
{
BigInteger aR = bottom n/2 digits of a;
BigInteger aL = top remaining digits of a;

BigInteger bR = bottom n/2 digits of b;
BigInteger bL = top remaining digits of b;

BigInteger x1 = Multiply(aL, bL);
BigInteger x2 = Multiply(aR, bR);
BigInteger x3 = Multiply(aL + bL, aR + bR);

return x1 * pow(10, n) + (x3 - x1 - x2) * pow(10, n / 2) + x2;
}
}

*/

/*
MS Calling Convention
__cdecl, __fastcall, __stdcall, __thiscall;

*/

#include <iostream>
#include <string>
#include <sstream>
#include <vector>

using std::cout;
using std::cin;
using std::string;
using std::stringstream;
using std::vector;

#define SIZE 50

// ------------------------------------------------

void MultiplyBigInteger(char *, char *);
int length(char *);
void divide(int, int *, int *);

// ------------------------------------------------
int main(int argc, char *argv[])
{
char *firstNumber = "1",
*secondNumber = "2";

MultiplyBigInteger(firstNumber, secondNumber);

return 0;
}
// ------------------------------------------------
void MultiplyBigInteger(char *firstNumber, char *secondNumber)
{
int firstLength = length(firstNumber);
int secondLength = length(secondNumber);

int *firstLeftLength = &firstLength,
*firstRightLength = &firstLength,

*secondLeftLength = &secondLength,
*secondRightLength = &secondLength;

char *firstRight = 0, *firstLeft =0,
*secondRight = 0, *secondLeft = 0;

divide(firstLength, firstLeftLength, firstRightLength);
divide(secondLength, secondLeftLength, secondRightLength);

if (firstLength == 1 && secondLength == 1)
{
int oneDigitResult = /*static_cast<int>*/(firstNumber + 0)
* /*static_cast<int>*/(secondNumber + 0);
cout << oneDigitResult;
}
else
{
//		MultiplyBigInteger(
}
}
// ------------------------------------------------
int length(char *number)
{
int length = 0;
for (int loop=0;number[loop] != '\0';loop++)
{
*(number + loop);
length++;
}
return length;
}
// ------------------------------------------------
void divide(int length, int *leftLength,
int *rightLength)
{
if (length % 2 != 0)
{
*leftLength = (length % 2) + 1;
*rightLength = (length % 2);
}
else
{
*leftLength = length / 2;
*rightLength = length / 2;
}
}```
In multiplication function,

Code:
```void MultiplyBigInteger(char *firstNumber, char *secondNumber)
{
int firstLength = length(firstNumber);
int secondLength = length(secondNumber);

int *firstLeftLength = &firstLength,
*firstRightLength = &firstLength,

*secondLeftLength = &secondLength,
*secondRightLength = &secondLength;

char *firstRight = 0, *firstLeft =0,
*secondRight = 0, *secondLeft = 0;

divide(firstLength, firstLeftLength, firstRightLength);
divide(secondLength, secondLeftLength, secondRightLength);

if (firstLength == 1 && secondLength == 1)
{
int oneDigitResult = /*static_cast<int>*/(firstNumber + 0)
* /*static_cast<int>*/(secondNumber + 0);
cout << oneDigitResult;
}
else
{
//		MultiplyBigInteger(
}
}```
Code:
```if (firstLength == 1 && secondLength == 1)
{
int oneDigitResult = /*static_cast<int>*/(firstNumber + 0)
* /*static_cast<int>*/(secondNumber + 0);
cout << oneDigitResult;
}```

If the value is single digit then i want to multiply by ANSI table which is 1(49) * 2(50) but how do i achieve his ?

I don't want convert this to int array due to higher memory consumption and i want better solution.

7. Registered User
Join Date
May 2007
Posts
843

8. Registered User
Join Date
May 2007
Posts
843
Any one.

Thanks.

9. Senior Member
Join Date
Dec 2004
Location
San Bernardino County, California
Posts
1,468
I worked on this a couple of years ago. I have my notes and code at home. I'll try to respond this evening (west coast USA time).

10. Registered User
Join Date
May 2007
Posts
843
I worked on this a couple of years ago. I have my notes and code at home. I'll try to respond this evening (west coast USA time).
Happy to hear that.

11. Registered User
Join Date
May 2007
Posts
843
I really have hard time to understand this algorithm and look forward nsplis's help.

12. Registered User
Join Date
May 2007
Posts
843
Recursion is not my strong part of programming.

I look forward for any help.

Thanks.

13. Registered User
Join Date
Dec 2007
Posts
401
you really can't keep requesting someone else to explain from first principles every algorithm that you encounter.

learn to take one small baby step at a time before you attempt to sprint.

first, understand simple recursion by working through a beginner's tutorial; something like http://cse.unl.edu/~dsadofs/RecursionTutorial/index.php

once this much has been well-understood, go on to learn more about recursion: tail-recursion, tree-recursion and how to convert between recursive and iterative implementations of algorithms. http://www.cc.gatech.edu/classes/AY2...ion_gallis.htm

next, understand the karatsuba algorithm for multiplying small (say two-digit) numbers. http://mathworld.wolfram.com/Karatsu...plication.html

once that is clear, study how to extend the algorithm to the general N-digit case by using a divide-and-conquer approach. http://www.student.cs.uwaterloo.ca/~cs341/lecture5.html

and then you would be able to write either a recursive or an iterative implementation of the karatsuba algorithm.

14. Registered User
Join Date
May 2007
Posts
843

I want to learn them in hand first then i need to write the recursion tree and recurrence relation.

Thanks.

15. Senior Member
Join Date
Dec 2004
Location
San Bernardino County, California
Posts
1,468
Peter:

Take a look at Chapter 2 of this book, "Algorithms" by S. Dagupta, C H Papadimitriu, and U. V. Vazirani. Their explanation of the recursive approach to this Karatsuba multiplication process is very precise while not being thick. So much better written than I ever could produce.

The book is also available through e-booksdirectory.com, which has a plethora of ebooks, mostly in PDF format, on many different subjects all available for free download. You can get to the book directly at:

http://www.cs.berkeley.edu/~vazirani/algorithms/all.pdf

#### Posting Permissions

• You may not post new threads
• You may not post replies
• You may not post attachments
• You may not edit your posts
•

 FAQ Latest Articles Java .NET XML Database Enterprise