Factorial, the direct way

exercise No. 114

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 yield large factorials. long (currently!) is the best (largest) choice among all 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.

Prev  Up  Next
Maximum and absolute value  Home  Factorial, the recursive way