Factorial, the direct way

exercise No. 107

Q:

Compute the factorial of a given integer value, for example:

4 ! = 4 × 3 × 2 × 1

Implement the following method:

/**
 * Computing the factorial of a given argument.
 *
 * @param n
 *  Zero or any positive integer
 *
 * @return
 *  The product 1 x 2 x 3 x ... x n or 1 in case of n == 0. In case of an
 *  arithmetic overflow a value of {@link Long#MAX_VALUE} is being returned.
 */
static public long factorial(int n) {
  // TODO: implement me!
}
  1. The method's signature looks slightly weird: It does expect an argument of type int but returns a long value. Explain the underlying ratio.

  2. Mind the above Javadoc passage concerning integer overflow related problems with respect to your own implementation.

  3. Provide adequate unit tests. Do not forget special values and handling of arithmetic overflow problems.

A:

We address all three questions individually:

  1. Returning a long is sensible since even small argument values in return yield large factorials. long is the best (largest) choice among the Java built-in integer types. Consider the following example code:

    public static void main(String[] args) {
    
      System.out.println("Max long value:" + Long.MAX_VALUE + "\n");
      for (int i = 15; i < 23; i++) {
        System.out.println(i + ":" + factorial(i));
      }
    }
    
    static public long factorial(int n) {
    
      long ret = 1;
      for (int i = n; 1 < i; i--) {
        ret *= i;
      }
      return ret;
    }

    This yields:

    Max long value:9223372036854775807
    
    15:1307674368000
    16:20922789888000
    17:355687428096000
    18:6402373705728000
    19:121645100408832000
    20:2432902008176640000
    21:-4249290049419214848
    22:-1250660718674968576

    So starting from 21 ! we already see long overflow related errors. Thus allowing for even larger long arguments instead of int does not make sense at all.

    Since 21 is pretty small we might favour short (or even char) as argument type:

    static public long factorial(short n) { ... }

    This however is a bad idea: Even simple expressions would be flagged as compile time errors since both integer literals and arithmetic expressions in Java evaluate to the data type int:

    // Compile time error:
    // The method factorial(short) in the type
    // App is not applicable for the arguments (int)
    System.out.println(factorial(3));

    BTW: If we choose static public int factorial(short n) (int return type) the first overflow error happens already when trying to calculate 13 ! .

  2. We have to handle:

    • Argument value 0.

    • Overflow related results.

  3. Tests must address regular, special and overflow related argument values.