2
\$\begingroup\$

I am looking for feedback for the implementation for calculating factorial of a number. I have tried to do with a loop, recursion and in a mutlithreaded way.

package org.spituk.study.programs;

import java.util.ArrayList;
import java.util.List;
import java.util.concurrent.*;

/**
 * Class for calculating factorial of a number.
 *
 * @author Karan Khanna
 * @version 1.0
 * @since 12/8/2018
 */
public class Factorial {

    private final static int JOB_SIZE = 10;

    private final static int AVAILABLE_PROCESSORS = Runtime.getRuntime().availableProcessors();

    /**
     * Calculates the factorial of the number with loop.
     *
     * @param number whose factorial is to be calculated.
     * @return calculated factorial of the number
     */
    public long getFactorialWithLoop(final int number) {
        long factorial = 1;
        for (int index = 2; index <= number; index++) {
            factorial = factorial * index;
        }
        return factorial;
    }


    /**
     * Calculates the factorial of the number with recursion.
     *
     * @param number whose factorial is to be calculated.
     * @return calculated factorial of the number
     */
    public long getFactorialWithRecursion(final int number) {
        return factorialRecursion(number);
    }


    /**
     * Calculates the factorial of the number with multiple threads.
     *
     * @param number whose factorial is to be calculated.
     * @return calculated factorial of the number
     */
    public long getFactorialMultiThreaded(final int number) throws Exception {
        ExecutorService executor = Executors.newFixedThreadPool(AVAILABLE_PROCESSORS);
        List<PartialFactorialJob> partialFactorialJobs = new ArrayList<PartialFactorialJob>();

        int startIndex = 1;
        int pivot = JOB_SIZE;

        while(pivot <= number) {
            if(pivot + JOB_SIZE > number) {
                pivot = number;
            }
            partialFactorialJobs.add(new PartialFactorialJob(startIndex, pivot));
            startIndex = pivot + 1;
            pivot = pivot + JOB_SIZE;
        }

        try {
            long factorial = 1;
            final List<Future<Long>> futureList = executor.invokeAll(partialFactorialJobs);
            for (Future<Long> future : futureList) {
                factorial = factorial * future.get();
            }
            executor.shutdown();
            return factorial;
        } catch (InterruptedException | ExecutionException e) {
            throw new Exception("Factorial couldn't be calculated.");
        }
    }


    private long factorialRecursion(final int number) {
        if (number <= 0) {
            return 1;
        }
        return number * factorialRecursion(number - 1);
    }

    private class PartialFactorialJob implements Callable<Long> {

        private final int startIndex;
        private final int endIndex;

        PartialFactorialJob(final int startIndex, final int endIndex) {
            this.startIndex = startIndex;
            this.endIndex = endIndex;
        }

        public Long call() {
            long partialFactorial = 1;
            int temp = startIndex;
            while (temp <= endIndex) {
                partialFactorial = partialFactorial * temp;
                temp++;
            }
            return partialFactorial;
        }
    }
}
\$\endgroup\$
  • \$\begingroup\$ What's the problem you are asking for? (I don't understand) \$\endgroup\$ – Sir Jo Black Dec 8 '18 at 17:54
  • \$\begingroup\$ A review for the code. \$\endgroup\$ – Karan Khanna Dec 8 '18 at 17:55
  • \$\begingroup\$ Ok! I thought to be in stackoverflow, excuse me! \$\endgroup\$ – Sir Jo Black Dec 8 '18 at 18:05
  • \$\begingroup\$ What is the purpose of the multi-threaded version? Keep in mind that for number >= 66 the result is always zero \$\endgroup\$ – harold Dec 8 '18 at 18:19
4
\$\begingroup\$

A few comments:


import java.util.concurrent.*;

Never do wildcard imports unless you're doing a one-time, throw-away program. Maybe, in Java 20 or so, they introduce a class java.util.concurrent.Factorial (contrived example), and then you have a name collision with one of your classes. Better stick to individual imports (or have your IDE organize the imports).


Thumbs up for attaching javadoc to all public elements.


public long getFactorialWithRecursion(final int number) {
    return factorialRecursion(number);
}

I'd skip the indirection from getFactorialWithRecursion() calling factorialRecursion() and write

public long getFactorialWithRecursion(final int number) {
    if (number <= 0) {
        return 1;
    }
    return number * getFactorialWithRecursion(number - 1);
}

Other SO members already commented that computing a factorial with multiple threads might not be a useful application, but I understand that this is for exerecise purposes.

The while loop in getFactorialMultiThreaded makes it hard to read and understand the code, with the two loop variables startIndex and pivot having their operations spread over many lines of code. I'd write something like

for (int startIndex = 1; startIndex <= number; startIndex += JOB_SIZE) {
    int endIndex = Math.min(startIndex + JOB_SIZE - 1, number);
    partialFactorialJobs.add(new PartialFactorialJob(startIndex, endIndex));
}

Similar thing applies to the while loop in your call method, I'd prefer a for loop instead.


As your PartialFactorialJob class doesn't access anything from the enclosing Factorial instance, you should make it static (otherwise it carries around a useless internal reference to its enclosing instance, typically visible in your debugger as this$1 or similar).

\$\endgroup\$
2
\$\begingroup\$

static

The Factorial class doesn't have any non-class data members, so it shouldn't have any non-static methods.

In particular:

  1. getFactorialWithLoop() can be made static.
  2. getFactorialWithRecursion() can be made static if factorialRecursion() is also made static.
  3. getFactorialMultiThreaded() can be made static if you change class PartialFactorialJob to be a static inner class.

getFactorialWithLoop():

Only change I'd make here would be to use the product-assignment operator.

factorial *= index;

Tail-Recursion

getFactorialWithRecusion() / factorialRecursion():

Since the value returned from a recursive call to factorialRecursion() is not directly returned from an outer call, tail-recursion-optimization cannot be performed. This means the stack can overflow if a deep recursive call is made. If the value returned from a recursive call is directly returned, tail-recursion-optimization by the compiler can eliminate recursive calls.

public long getFactorialWithRecursion(final int number) {
    return factorialRecursion(number, 1);
}

private long factorialRecursion(int number, long accumulator) {
    if (number <= 1)
        return accumulator;
    else
        return factorialRecursion(number - 1, accumulator * number);
}

The statement return factorialRecursion(number - 1, accumulator * number); can be translated by the compiler into a jump to the start of the function, with modified arguments.


Job-Size

This loop is a no-op for values of number less than 10!

    int pivot = JOB_SIZE;

    while(pivot <= number) {
        // ...
    }

So the multi-threaded factorial does not calculate the result properly for number < 10!

The size of a PartialFactorialJob can exceed JOB_SIZE. Consider number = 19. pivot equals 10, so pivot + JOB_SIZE > number is true, and pivot is assigned 19, so the first and only job submitted is new PartialFactorialJob(1, 19).

What you want is the while-loop to test for startIndex not greater than number:

int startIndex = 1;

while (startIndex <= number) {
    int endIndex = Math.min(startIndex + JOB_SIZE - 1, number);
    partialFactorialJobs.add(new PartialFactorialJob(startIndex, endIndex));
    startIndex += JOB_SIZE;
}

But now this looks like a for-loop:

for (startIndex = 1; startIndex <= number; startIndex += JOB_SIZE) {
    int endIndex = Math.min(startIndex + JOB_SIZE - 1, number);
    partialFactorialJobs.add(new PartialFactorialJob(startIndex, endIndex));
}

Argument Limits

21! exceeds the size of a long. You might want:

if (number < 0 || number > 20)
    throw new IllegalArgumentException("Factorial out-of-range")

Or you may want to use BigInteger for calculation of larger factorials.


Bonus Methods

You can also use the Stream API to calculate factorials:

long getFactorialWithStream(final int number) {
    return LongStream.rangeClosed(1, number)
                     .reduce(1, (x,y) -> x*y);
}

long getFactorialWithParallelStream(final int number) {
    return LongStream.rangeClosed(1, number)
                     .parallel()
                     .reduce(1, (x,y) -> x*y);
}
\$\endgroup\$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.