Re: Stirling Approx to N! for large Number?

Factorial is a good candidate for memoization. A memoized version of factorial is faster than Stirling's (at least for a naive implementation of Stirling's in the range of arguments that don't cause overflow). Here are the stats:

             Rate     pure stirling     memo
pure      15037/s       --     -89%     -94%
stirling 139183/s     826%       --     -48%
memo     267957/s    1682%      93%       --
[download]

I give the code below. Note that I fixed your Stirling approximation; I used one of the versions given by MathWorld (expression 11). I also made some other small changes.

On my system, all these subroutines overflow for any argument > 170.

Afterthought: Actually, this range is so small that you may as well save yourself the subroutine call: just precompute the whole array, and access $fact[ $n ] directly. On the other hand, retaining the procedural interface is better software engineering.

Update 2: Fixed the handling of invalid arguments in factorial_memo.

the lowliest monk

#!/usr/bin/perl -w
use strict;

use constant C_TERM => 0.5 * log( 8 * atan2 1, 1 );

# my @r = map +(int rand( 171 )), 1..1000;
# my ($p, $m, $s) = (0) x 3;

# use Benchmark 'cmpthese';
# cmpthese( -1, {
#                pure     => sub { factorial_pure($r[$p++%1000]) },
#                memo     => sub { factorial_memo($r[$m++%1000]) },
#                stirling => sub { factorial_stirling($r[$s++%1000]) }
+,
#               }
#          );

my $h = shift;
my $pure     = factorial_pure($h);
my $memo     = factorial_memo($h);
my $stirling = factorial_stirling($h);

print "PURE     : $pure\n";
print "MEMO     : $memo\n";
print "STIRLING : $stirling\n";

#------Subroutines------------

sub factorial_stirling {
  my $n = shift;
  return undef if $n < 0 or $n > int $n;
  return 1 if $n == 0;
  my $log_nfact = ( $n + 0.5 ) * log( $n ) - $n + C_TERM;

  return exp $log_nfact;
}

sub factorial_pure {
  my ($n,$res) =  (shift,1);
  return undef unless $n>=0 and $n == int($n);
  $res *= $n-- while $n>1;
  return $res;
}

{
  my @fact;
  INIT {
    @fact = ( 1 );
  }
  sub factorial_memo {
    my $n = shift;
    die "Invalid arg: $n\n" if $n < 0 or $n > int $n;
    return ( $fact[ $n ] or $fact[ $n ] = $n * factorial_memo( $n - 1 
+) );
  }
}
[download]

Comment on Re: Stirling Approx to N! for large Number? Select or Download Code