# Algorithm Help

• 08-07-2003
golfinguy4
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.

• 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.
• 08-08-2003
xizor
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.
• 08-08-2003
...
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...
• 08-08-2003
xizor
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!
• 08-08-2003
golfinguy4
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.
• 08-08-2003
FillYourBrain
xizor. Is that Xizor as in "Shadows of the Empire"?
• 08-08-2003
confuted
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.
• 08-08-2003
xizor
Quote:

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 :D
• 08-08-2003
FillYourBrain
yeah, well they don't usually admit to it.
• 08-08-2003
golfinguy4
Yep, I see what you mean. Very good thinking blackrat.