The factorial function is a special case of Pochhammer's polynomial and of the gamma function (aka Euler's integral of the second kind). The conventional mathematical notation for the factorial of n is
so statements containing a factorial expression always look surprising or important.
The factorial function is used in the study of permutations. For example, the number of possible sequences of a deck of 52 cards is 52! which is a really huge 68-digit number. To graph the factorial function, start with your pencil at (1,1) moving northeast, then real sudden-like, go north. The factorial function is explosive: the largest factorial that can fit in a Java int is 12!.
The most important application of the factorial function is a pedagogical one: it is one of the classic exercises in first semester programming. It is often one of the first examples presented of iteration or recursion. It produces precise results, so it is easy to verify. It is an integer function, so most number theory issues can be avoided.
Part of mastery of E is knowing when to use the optimistic computation features of E, and when to use the pessimistic computation features of Java. The factorial function does not benefit from an optimistic implementation, and so should not be written in E. It can be implemented more efficiently in Java. There are many applications that benefit significantly from E's optimistic computation features. The factorial function is not one of them.
We will now present six implementations of the factorial function, all written in E.
All of the implementations of Factorial below can be called with this sequence:
EInteger result;
new Factorial <- factorial (n, &result);
ewhen result (int fac) {
// fac contains n!
}
result is an EInteger which will receive the result. The distributor of result is sent to the Factorial eobject. When the result has been computed, its value will be assigned to fac.
The examples are presented in order of decreasing practicality.
We will first examine three mostly-Java implementations. The first one is very efficient, the remaining two are instructive. All three are Java functions in E wrappers. This use of E can be beneficial in the case where there is a math server available that could compute the function while the requester goes on doing other useful work.
If the goal is to compute the factorial function quickly, then the best method is a table look up. The table doesn't even need to be very large. This form of the factorial function is rarely seen in programming texts, because the purpose of the factorial function in general is didactic, not mathematical.
// Act 1a: E wrapper table look up
eclass Factorial {
final static int factorialTable [ ] = {1, 1, 2, 6, 24, 120, 720,
5040, 40320, 362880, 3628800, 39916800, 479001600};
emethod factorial (int n, EDistributor result) {
result <- forward (new EInteger (factorialTable [n]));
}
}
The next example uses iteration to produce the product of all of the counting numbers up to n. This is textbook stuff.
// Act 1b: E wrapper iteration
eclass Factorial {
emethod factorial (int n, EDistributor result) {
int product = 1;
while (n > 1) {
product *= n;
n -= 1;
}
result <- forward (new EInteger (product));
}
}
The other classic textbook implementation of the factorial function demonstrates recursion, defining a function in terms of itself. This version makes use of a private Java method within an E class.
// Act 1c: E wrapper recursion
eclass Factorial {
private int factorialStep (int n) {
if (n > 1) {
return (n * factorialStep (n - 1));
} else {
return (1);
}
}
emethod factorial (int n, EDistributor result) {
result <- forward (new EInteger (factorialStep (n));
}
}
The three remaining implementations of the factorial function make more extensive (if inappropriate) use of E's messaging semantics.
The first implementation uses the message sending semantics of E to perform iteration without using a loop. It iterates by sending factorialStep messages (containing a decreasing n and an increasing product) to itself. When n goes down to one, the product is forwarded to the result.
// Act 2a: message iteration (eteration)
eclass Factorial {
emethod factorialStep (int n, int product, EDistributor result) {
if (n > 1) {
this <- factorialStep (n - 1, n * product, result);
} else {
result <- forward (new EInteger (product));
}
}
emethod factorial (int n, EDistributor result) {
this <- factorialStep (n, 1, result);
}
}
This next implementation performs recursion without using a stack. A chain of linked intermediate results will trigger a cascade of ewhens which will produce the result.
// Act 2b: message recursion (ecursion)
eclass Factorial {
emethod factorial (int n, EDistributor result) {
if (n > 1) {
EInteger intermediate;
this <- factorial (n - 1, &intermediate);
ewhen intermediate (int product) {
result <- forward (new EInteger (n * product));
}
} else {
result <- forward (new EInteger (1));
}
}
}
Finally, we show a factorial function implementation using a pure data flow computation model. All of the computation is expressed in the form of messages.
// Act 2c: dataflow
eclass Factorial {
final static EInteger EOne = new EInteger (1);
emethod factorialStep (EInteger n, EInteger product,
EDistributor result) {
EBoolean nGreaterThanOne;
n <- gt (EOne, &nGreaterThanOne);
eif (nGreaterThanOne) {
EInteger nMinusOne;
EInteger nTimesProduct;
n <- sub (EOne, &nMinusOne);
n <- mul (product, &nTimesProduct);
this <- factorialStep (nMinusOne, nTimesProduct, result);
} else {
result <- forward (product);
}
}
emethod factorial (int n, EDistributor result) {
this <- factorialStep (new EInteger (n), EOne, result);
}
}
This implements the same algorthm as the message iteration (2a) example above. The difference is that every statement is an E statement and every object is an EObject. So, for example, instead of sending (n-1) in factorialStep, it sends a channel (nMinusOne) that will eventually point an EObject having that value. This style of dataflow programming can be quite effective in highly distributed or massively parallel environments.