# Parallel Multiplier: an implementation of RecursiveTask<V>

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 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;
}

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.

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