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


DevX Home    Today's Headlines   Articles Archive   Tip Bank   Forums   

Page 1 of 2 12 LastLast
Results 1 to 15 of 25

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

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

    Thanks for your help.
    Share on Google+

  2. #2
    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.
    DKyb
    -------------------------------
    Life is a short warm moment -
    Death is the long cold rest.
    Pink Floyd
    -------------------------------
    Share on Google+

  3. #3
    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.
    Share on Google+

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

    Thanks for your help.
    Share on Google+

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

    Thanks for your help.

    Please help.

    I hope GOD will bless you all.
    Share on Google+

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

    Thanks for your help.
    Share on Google+

  7. #7
    Join Date
    May 2007
    Posts
    843
    Please help me.
    Share on Google+

  8. #8
    Join Date
    May 2007
    Posts
    843
    Any one.

    Thanks.
    Share on Google+

  9. #9
    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).
    Share on Google+

  10. #10
    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.
    Share on Google+

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

    A billion thanks in advance.
    Share on Google+

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

    I look forward for any help.

    Thanks.
    Share on Google+

  13. #13
    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.
    Share on Google+

  14. #14
    Join Date
    May 2007
    Posts
    843
    Thanks for your suggestion.

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

    Thanks.
    Share on Google+

  15. #15
    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
    Share on Google+

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  
HTML5 Development Center
 
 
FAQ
Latest Articles
Java
.NET
XML
Database
Enterprise
Questions? Contact us.
C++
Web Development
Wireless
Latest Tips
Open Source


   Development Centers

   -- Android Development Center
   -- Cloud Development Project Center
   -- HTML5 Development Center
   -- Windows Mobile Development Center