factorial function - parallel processing [closed]

Question

i need to write factorial function(n!) in parallel computing on EREW PRAM system. assume that we have n proccessors. the complexity should be log n. how can i do this?

Answer 1

we have n proccessors. the complexity should be log n.

The question makes no sense, since you're looking for an algorithm whose complexity (log n) increases as you add processors (i.e. increase n).

I am guessing that what you're meant to do is split the product 1*2*3*...*k into n blocks of equal size, compute each sub-product on a separate processor, and then multiply the n results together.

Answer 2

In general you can divide the work N times for N processors and compute each independently. You can combine the results by multiplying the answers for each piece of work. e.g. the first task performed m!, the next (2m)!/m!, the third (3m!)/(2m!) etc. When you multiple the results you get n!.

BTW: You wouldn't do this for small values of n e.g less than 1000 because the overhead of starting new threads/task can be greater than the time it takes to do this in a single thread.

---

I suspect pseudo code won't be enough so here is an example

public enum CalcFactorial {;

    public static BigInteger factorial(long n) {
        BigInteger result = BigInteger.ONE;
        for (long i = 2; i <= n; i++)
            result = result.multiply(BigInteger.valueOf(i));
        return result;
    }

    public static BigInteger pfactorial(long n) {
        int processors = Runtime.getRuntime().availableProcessors();
        if (n < processors * 2)
            return factorial(n);
        long batchSize = (n + processors - 1) / processors;
        ExecutorService service = Executors.newFixedThreadPool(processors);
        try {
            List<Future<BigInteger>> results = new ArrayList<Future<BigInteger>>();
            for (long i = 1; i <= n; i += batchSize) {
                final long start = i;
                final long end = Math.min(n + 1, i + batchSize);
                results.add(service.submit(new Callable<BigInteger>() {
                    @Override
                    public BigInteger call() throws Exception {
                        BigInteger n = BigInteger.valueOf(start);
                        for (long j = start + 1; j < end; j++)
                            n = n.multiply(BigInteger.valueOf(j));
                        return n;
                    }
                }));
            }
            BigInteger result = BigInteger.ONE;
            for (Future<BigInteger> future : results) {
                result = result.multiply(future.get());
            }
            return result;
        } catch (Exception e) {
            throw new AssertionError(e);
        } finally {
            service.shutdown();
        }
    }
}

public class CalcFactorialTest {
    @Test
    public void testFactorial() {
        final int tests = 200;
        for (int i = 1; i <= tests; i++) {
            BigInteger f1 = factorial(i * i);
            BigInteger f2 = pfactorial(i * i);
            assertEquals(f1, f2);
        }
        long start = System.nanoTime();
        for (int i = 1; i <= tests; i++) {
            BigInteger f1 = factorial(i * i);
        }
        long mid = System.nanoTime();
        for (int i = 1; i <= tests; i++) {
            BigInteger f2 = pfactorial(i * i);
        }
        long end = System.nanoTime();
        System.out.printf("Single threaded took %.3f sec, multi-thread took %.3f%n",
                (mid - start) / 1e9, (end - mid) / 1e9);
    }
}

on an 3.72 GHz i7 prints

Single threaded took 58.702 sec, multi-thread took 11.391