Implementation of Java's BigInteger.multiply()

In this forum members can discuss topics about specific programming languages.
Post Reply
User avatar
PurpleBlu3s
Posts: 73
Joined: Mon Sep 19, 2011 5:49 pm

Implementation of Java's BigInteger.multiply()

Post by PurpleBlu3s » Mon Sep 19, 2011 5:53 pm

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.
Image

winnipegfr
Posts: 1
Joined: Tue Sep 20, 2011 10:04 pm

Re: Implementation of Java's BigInteger.multiply()

Post by winnipegfr » Tue Sep 20, 2011 10:27 pm

Hi,
I am having to multiply very large BigIntegers, and it's taking many seconds to achieve.
It depends on how big are your big integers, and the "power" of your computer...
So I was wondering whether I would need to implement my own more efficient algorithm - i.e Karatsuba's.
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.

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...
Or does BigInteger already do this?
Thanks.
That's the point. You should search what exactly this class is doing in its documentation.
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

TripleM
Posts: 382
Joined: Fri Sep 12, 2008 2:31 am

Re: Implementation of Java's BigInteger.multiply()

Post by TripleM » Tue Sep 20, 2011 10:55 pm

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.

thundre
Posts: 356
Joined: Sun Mar 27, 2011 9:01 am

Re: Implementation of Java's BigInteger.multiply()

Post by thundre » Wed Sep 21, 2011 6:33 pm

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.
True for the Sun/Oracle implementation of Java. I have not checked others.

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 = xstart-1; 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;
    }
The use of LONG_MASK is interesting.
Image

Post Reply