2
\$\begingroup\$

This class is my attempt at creating a re-usable class that simplifies the parallel calculation of products. I would appreciate hints on all aspects especially the value of the threshold for which the best performance is obtained.

import java.math.BigInteger;
import java.util.concurrent.RecursiveTask;

import static java.math.BigInteger.ONE;

/**
 * Utility class that uses recursion and multi-threading to compute the
 * product of all the (Big)Integers from a given lower limit (inclusive) to a
 * given upper limit (exclusive). This is useful in calculating the factorial
 * of numbers, or the number of combinations and permutations.
 *
 * @author Subhomoy Haldar
 * @version 1.0
 */
public class ParallelMultiplier extends RecursiveTask<BigInteger> {

    /**
     * The threshold beyond which recursion and multithreading starts.
     */
    private static final BigInteger THRESHOLD = BigInteger.valueOf(500);

    private final BigInteger upper;
    private final BigInteger lower;

    /**
     * Creates a new instance of ParallelMultiplier with the desired limits.
     *
     * @param lowerLimit The inclusive lower limit.
     * @param upperLimit The exclusive upper limit.
     */
    public ParallelMultiplier(final BigInteger lowerLimit,
                              final BigInteger upperLimit) {
        if (lowerLimit.compareTo(upperLimit) >= 0) {
            throw new IllegalArgumentException("Lower limit >= upper limit : "
                    + upperLimit + " >= " + lowerLimit);
        }
        upper = upperLimit;
        lower = lowerLimit;
    }

    /**
     * Returns the required product.
     *
     * @return The required product.
     */
    @Override
    protected BigInteger compute() {
        if (upper.subtract(lower).compareTo(THRESHOLD) <= 0) {
            // perform sequential multiplication
            BigInteger product = ONE;
            for (BigInteger i = lower; i.compareTo(upper) < 0; i = i.add(ONE))
                product = product.multiply(i);
            return product;
        }
        BigInteger mid = upper.add(lower).shiftRight(1);

        ParallelMultiplier multiplier1 = new ParallelMultiplier(lower, mid);
        ParallelMultiplier multiplier2 = new ParallelMultiplier(mid, upper);

        multiplier1.fork(); // On a (hopefully) separate thread

        // combine and return result
        return multiplier2.compute().multiply(multiplier1.join());
    }
}

Just to show that my approach actually has some benefits:

I have a Dual Core, Intel Pentium B950 processor of frequency 2.10 GHz. I have tested this on a 64-bit Ubuntu system. I realized that the threshold value was too low, so it set it to 10_000. After that, I wrote some test code to time the sequential and the parallel approaches to calculate the factorial of 100_000.

The sequential approach:

// ... The limit defined, timer set up...
BigInteger i = ONE, product = ONE;
for (; i.compareTo(limit) <= 0; i = i.add(ONE))
    product = product.multiply(i);
System.out.println(product.toString().length());

The parallel approach:

// ... The limit defined, timer set up...
ParallelMultiplier multiplier = new ParallelMultiplier(ONE, limit.add(ONE));
BigInteger product = multiplier.compute();
System.out.println(product.toString().length());

The number of digits produced in each case is same (=456574), therefore, verifying that the code for the ParallelMultiplier works correctly. But there was a major difference in the time interval:

Sequential: ~5.9 seconds (average)
Parallel  : ~1.2 seconds (average)

Any suggestions to further improve the performance are welcome.

\$\endgroup\$
  • \$\begingroup\$ Out of curiosity, have you measured speedups when resorting to parallel processing? \$\endgroup\$ – coderodde Nov 4 '15 at 17:30
  • \$\begingroup\$ I suggest you mention that in your post. May attract more performance-oriented people. \$\endgroup\$ – coderodde Nov 4 '15 at 17:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.