Thread: Algorithm Help

  1. #1
    ¡Amo fútbol!
    Join Date
    Dec 2001
    Posts
    2,138

    Algorithm Help

    I need some help with algorithms in my BigNum class (integers only). Currently, I have a fully functional BigNum class. However, multiplication and division are done by using the long division/multiplication taught to children in elementary school. I am looking for a better algorithm that is more efficient. The same is true of my pow function. It only accepts BigNum arguments and loops using *=. Again, this is inefficient with large exponents. Any suggestions in either case would be greatly appreciated.

    Here's a little more info on the class:
    • the sign is stored in a bool w/true representing negative
    • the abs of the function is stored in a string
    • I defined the the 4 basic operators to call the Add, Multiply, Subtract, and Divide functions passing the two values and the sign of the resulting value.

  2. #2
    Registered User
    Join Date
    Jul 2003
    Posts
    12
    I looked around a little bit and found that most bignum libraries are using a multiplication algorithm called Karatsuba Multiplication.

    I found the theory behind on
    MathWorld.

    An implementation (and a nice comparison of Karatsuba and "school" division)
    here.
    I wouldn't code the Karatsuba algorithm this way, but I hope it can give you some good hints.

    I'll get back if I find anything about a good division algorithm.

  3. #3
    Registered User
    Join Date
    Feb 2002
    Posts
    465
    the way i normally do powers is with a recursive function...

    Code:
    int power( int x, int y )
    {
    	y--;
    
    	if ( y >= 1 )
    	{
    		x *= power(x, y);
    
    	}
    
    	return x;
    	
    }

    it still uses the *=, but the loop is a bit faster...
    I came up with a cool phrase to put down here, but i forgot it...

  4. #4
    Registered User
    Join Date
    Jul 2003
    Posts
    12
    Now I'm starting to remember something from my computer science course...

    Division is not very easy to make quick, there are several algorithms used (look for "division algorithm" on google).

    The main type of algorithms used are the radix division algorithms (2, 4, 8... radix).
    All of them are quite complex, but I found a simple radix-2 algorithm implemented in c++
    here

    Good luck!

  5. #5
    ¡Amo fútbol!
    Join Date
    Dec 2001
    Posts
    2,138
    The thing is bit-shifting won't be efficient as the numbers are being stored in strings to allow (almost) unlimited digits.

    As for the power algorithm, that would crash very fast with a big number.

  6. #6
    pronounced 'fib' FillYourBrain's Avatar
    Join Date
    Aug 2002
    Posts
    2,297
    xizor. Is that Xizor as in "Shadows of the Empire"?
    "You are stupid! You are stupid! Oh, and don't forget, you are STUPID!" - Dexter

  7. #7
    Pursuing knowledge confuted's Avatar
    Join Date
    Jun 2002
    Posts
    1,916
    For powers:

    a^(m+n) = a^m * a^n

    Suppose you're trying to compute a^20

    a^20 = a^10* a^10
    a^10 = a^5 * a^5
    a^5 = a^2 * a^2 * a
    a^2 = a * a

    If you could make your program do that, you could compute a^2, store it in a variable, and work your way up from there, storing each needed power in a variable. It might not seem more efficient, but in the example above, it changes 19 multiplications into a mere 5 (assuming I counted correctly) Cuts down on overhead incurred from using recursion, too. Just an idea, but it seems like it would help a lot.

    edit:
    This becomes much more useful as the exponents get bigger. It doesn't give any benefit for exponents of 2 and 3. The number of multiplications needed after this method / the number needed to "brute force" it seems to be approximated fairly well by
    Y=2X^(-2/3) for even powers (x represents the power, y represents the return of my method)
    For odd powers it doesn't perform quite as well (because of the extra *a) and it's better represented by
    Y=1.5X^(-.4)

    I feel like a geek now.
    Last edited by confuted; 08-08-2003 at 08:48 AM.
    Away.

  8. #8
    Registered User
    Join Date
    Jul 2003
    Posts
    12
    Originally posted by FillYourBrain
    xizor. Is that Xizor as in "Shadows of the Empire"?
    Yup, you're right. Except that I don't run an evil mafia empire

  9. #9
    pronounced 'fib' FillYourBrain's Avatar
    Join Date
    Aug 2002
    Posts
    2,297
    yeah, well they don't usually admit to it.
    "You are stupid! You are stupid! Oh, and don't forget, you are STUPID!" - Dexter

  10. #10
    ¡Amo fútbol!
    Join Date
    Dec 2001
    Posts
    2,138
    Yep, I see what you mean. Very good thinking blackrat.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Implement of a Fast Time Series Evaluation Algorithm
    By BiGreat in forum C Programming
    Replies: 7
    Last Post: 12-04-2007, 02:30 AM
  2. Replies: 4
    Last Post: 12-10-2006, 07:08 PM
  3. Binary Search Trees Part III
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 16
    Last Post: 10-02-2004, 03:00 PM
  4. Request for comments
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 15
    Last Post: 01-02-2004, 10:33 AM