## Sunday, July 3, 2011

Update: the follow up post gives another version, that lacks the drawback of unequal load on processor cores.

There is a very good blog post about how to write the factorial method in Java (really it is not about righting factorial). However, even in this master peace;-) there is no multi-threaded factorial. So here it is.
There are some problems with it. The most significant is that multiplying all the BigIntegers from 1 to 50000 is much less heavy job for the computer, than multiplying all BigIntegers from 50001 to 100000. So the the amount of work that is done by each worker-thread is not equal. But investigation on how this may be resolved in a common way is much harder problem, than just writing what I am publishing here. Maybe I'll do it in the other post.
``````

import java.math.BigDecimal;
import java.util.concurrent.TimeUnit;

import junit.framework.Assert;

import org.junit.Test;

public class FactorialTest {

private static final int INPUT = 203457;

@Test
public void test() throws InterruptedException {
BigDecimal fact1, fact2;
{
long start = System.nanoTime();
fact1 = fact(INPUT);
long end = System.nanoTime();
System.out.println(TimeUnit.SECONDS.convert(end - start,
TimeUnit.NANOSECONDS) + " seconds for 1 thread");
}
{
long start = System.nanoTime();
fact2 = factMt(INPUT, 4);
long end = System.nanoTime();
System.out.println(TimeUnit.SECONDS.convert(end - start,
TimeUnit.NANOSECONDS) + " seconds for 4 threads");
}
Assert.assertEquals(fact1, fact2);

}

private static BigDecimal fact(int input) {
BigDecimal result = BigDecimal.valueOf(1);
for (int i = 1; i <= input; i++) {
result = result.multiply(BigDecimal.valueOf(i));
}
return result;
}

private static BigDecimal factMt(int input, int numThreads)
throws InterruptedException {
BigDecimal result = BigDecimal.valueOf(1);
for (int i = 1; i <= numThreads; i++) {
int start = i == 1 ? 1 : (input / numThreads * (i - 1)) + 1;
int end = i == numThreads ? input : input / numThreads * i;
workers[i - 1] = new FactComputer(start, end);
}

for (int i = 0; i < numThreads; i++) {
}

for (int i = 0; i < numThreads; i++) {
}
for (int i = 0; i < numThreads; i++) {
result = result.multiply(workers[i].result);
}
return result;
}

private static class FactComputer implements Runnable {
BigDecimal result;
private final int from;
private final int to;

public FactComputer(int from, int to) {
this.from = from;
this.to = to;
}

public void run() {
result = BigDecimal.valueOf(from);
for (int i = from + 1; i <= to; i++) {
result = result.multiply(BigDecimal.valueOf(i));
}

}
}
}
``````
Here is the result in System.out: