The lost art (Was: The VAX is running
Eric J Korpela
korpela at ssl.berkeley.edu
Tue Apr 7 17:21:54 CDT 2009
On Tue, Apr 7, 2009 at 1:41 PM, <arcarlini at iee.org> wrote:
> cctalk-bounces at classiccmp.org wrote:
>> If I ask "How would you write a program to calculate the
>> natural log of 147 factorial?" and the answer doesn't involve
>> looking up an algorithm for the gamma function (or someone
>> who actually remembers the functional form of the Stirling
>> approximation) I shout "next!" Factorials should never be
>> used as an example of recursion in intro programming courses.
> Couldn't the answer be "loop from 2 to N=147, sum += ln(N)"?
> Or do I need another coffee?
It could be, if you only need to do it once. That's 146 calls to
log(). It's also O(N) IIRC, the usual (double precision) algorithm
is an O(0) using 17 FLOP (of which 6 are division)+2 calls to log().
The five of the divisions are division by integers for factorials, so
you might be able to replace them with a reciprocal table for small
integers. Unless, of course you want the full gamma function, which
is defined for all positive real numbers and all negative numbers that
More information about the cctalk