Example - Factorial
Posted on: July 26, 2006 at 12:00 AM
Posted on: July 26, 2006 at 12:00 AM
Factorial n (usually written n!) is the product of all integers up to and including n (1 * 2 * 3 * ... * n).
Solution with
The proper solution is to use
Java Notes
Example - Factorial
Factorial n (usually written n!) is the product of all integers up to and including n (1 * 2 * 3 * ... * n). This problem is often (inappropriately) used as a programming example, especially to show how to write recursive functions.Recursive solution is a bad example
Writing a recursive factorial function is a mistake because- The recursive solution's memory usage is O(N) instead of O(1).
- It's more complicated for students.
- It's inappropriate when the iterative solution is better.
Range and precision problems
Even the iterative solution has problems because the large numbers that factorial generates cannot be represented in the limited range of integers, or limited precision of floating-point numbers. Programs using these primitive types are very dangerous because they will produce garbage results without comment.Solution with java.math.BigInteger
The proper solution is to use java.Math.BigInteger.
Here is a program with int and BigInteger solutions.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 |
// numbers/Factorial.java - Computes factorial
// Fred Swartz - 2003-11-02
import java.math.BigInteger;
public class Factorial {
public static void main(String[] args) {
//-- BigInteger solution.
BigInteger n = BigInteger.ONE;
for (int i=1; i<=20; i++) {
n = n.multiply(BigInteger.valueOf(i));
System.out.println(i + "! = " + n);
}
//-- int solution (BAD IDEA BECAUSE ONLY WORKS TO 12).
int fact = 1;
for (int i=1; i<=20; i++) {
fact = fact * i;
System.out.println(i + "! = " + fact);
}
}
}
|
Sample output
An int produces pure garbage after 12, and long
only makes it to 20. The shame of integer arithmetic is that it
doesn't stop when the values are bad -- it just produces garbage by
throwing away bits in the result that don't fit in an int (32 bits)
or long (64-bits).
BigInteger values are limited only
by the amount of memory.
|
|