Hi,
I am having to multiply very large BigIntegers, and it's taking many seconds to achieve. So I was wondering whether I would need to implement my own more efficient algorithm  i.e Karatsuba's. Or does BigInteger already do this?
Thanks.
Implementation of Java's BigInteger.multiply()
 PurpleBlu3s
 Posts: 73
 Joined: Mon Sep 19, 2011 5:49 pm

 Posts: 1
 Joined: Tue Sep 20, 2011 10:04 pm
Re: Implementation of Java's BigInteger.multiply()
Hi,
BUT, implementing your own algorithm will provide you a great pride. You'll gain
proficiency in Java and a deeper understanding in the algorithm you've coded.
Nonetheless, running your program will 99%, not to say always, take more time than
if you use an appropriate library...
I think that as Karatsuba's algo is quite old, the BigInteger class may
implement such an algorithm, even a better one...
Hope that helps.
Nico
It depends on how big are your big integers, and the "power" of your computer...I am having to multiply very large BigIntegers, and it's taking many seconds to achieve.
Most of the time, it's a bad idea to do this unless you are an expert in your favorite programming language or you are implementing a brand new algorithm (It implies that you are an expert in the field)... Use the right library to archive your goal.So I was wondering whether I would need to implement my own more efficient algorithm  i.e Karatsuba's.
BUT, implementing your own algorithm will provide you a great pride. You'll gain
proficiency in Java and a deeper understanding in the algorithm you've coded.
Nonetheless, running your program will 99%, not to say always, take more time than
if you use an appropriate library...
That's the point. You should search what exactly this class is doing in its documentation.Or does BigInteger already do this?
Thanks.
I think that as Karatsuba's algo is quite old, the BigInteger class may
implement such an algorithm, even a better one...
Hope that helps.
Nico
Re: Implementation of Java's BigInteger.multiply()
BigInteger multiply uses the naive O(mn) algorithm, which works better than Karatsuba's when the numbers are at most a few thousand digits long each due to the amount of overhead.
If you want to multiply bigger numbers than that quickly, then you will definitely want to code up your own method.
If you want to multiply bigger numbers than that quickly, then you will definitely want to code up your own method.
Re: Implementation of Java's BigInteger.multiply()
True for the Sun/Oracle implementation of Java. I have not checked others.TripleM wrote:BigInteger multiply uses the naive O(mn) algorithm, which works better than Karatsuba's when the numbers are at most a few thousand digits long each due to the amount of overhead.
If you want to multiply bigger numbers than that quickly, then you will definitely want to code up your own method.
Code: Select all
/**
* This mask is used to obtain the value of an int as if it were unsigned.
*/
final static long LONG_MASK = 0xffffffffL;
/**
* Multiplies int arrays x and y to the specified lengths and places
* the result into z. There will be no leading zeros in the resultant array.
*/
private int[] multiplyToLen(int[] x, int xlen, int[] y, int ylen, int[] z) {
int xstart = xlen  1;
int ystart = ylen  1;
if (z == null  z.length < (xlen+ ylen))
z = new int[xlen+ylen];
long carry = 0;
for (int j=ystart, k=ystart+1+xstart; j>=0; j, k) {
long product = (y[j] & LONG_MASK) *
(x[xstart] & LONG_MASK) + carry;
z[k] = (int)product;
carry = product >>> 32;
}
z[xstart] = (int)carry;
for (int i = xstart1; i >= 0; i) {
carry = 0;
for (int j=ystart, k=ystart+1+i; j>=0; j, k) {
long product = (y[j] & LONG_MASK) *
(x[i] & LONG_MASK) +
(z[k] & LONG_MASK) + carry;
z[k] = (int)product;
carry = product >>> 32;
}
z[i] = (int)carry;
}
return z;
}