Since multiplication is commutative, you can limit the size of numbers and thus vastly accelerate this function by multiplying the next biggest with the next smallest factor in turn: rather than calculate 1*(2*(3*(4*5))), you calculate ((1*5)*3)*(2*4):

1 * 2 * 3 * 4 * 5 =
|   |       |   |
|   +-------+   |
+---------------+

5 * 8 * 3 =
|       |
+-------+

15 * 8 =

120

See fact7.

#!/usr/bin/perl -w
use strict;
use Benchmark;
use Math::BigInt;

sub fact1 {
    my $n = Math::BigInt->new(shift);
    return 1 unless $n->bcmp(0);
    return $n->bmul(fact1($n->bsub(1)));
}

sub fact4 {
    my $n = Math::BigInt->new(1);
    foreach my $i (map Math::BigInt->new($_), 1..shift) {
        $n = Math::BigInt->new($i->bmul($n));
    }
    return $n;
}

sub fact7 {
    my @factor = map Math::BigInt->new($_), (1 .. shift);
    while(@factor > 1) {
        my @pair = splice @factor, 1 + $#factor / 2;
        $_ = $_ * pop @pair for @factor[0..$#pair];
    }
    return shift @factor;
}

my $fact = shift || 100;

my ($f1, $f4, $f7) = (fact1($fact), fact4($fact), fact7($fact));

die "something's broke" if grep $_ != $f1, ($f4, $f7);

timethese(shift || 10, {
    f1 => sub { fact1($fact) },
    f4 => sub { fact4($fact) },
    f7 => sub { fact7($fact) },
});
__END__

$ fact 600 5
Deep recursion on subroutine "main::fact1" at fact line 9.
Benchmark: timing 5 iterations of f1, f4, f7...
Deep recursion on subroutine "main::fact1" at fact line 9.
Deep recursion on subroutine "main::fact1" at fact line 9.
Deep recursion on subroutine "main::fact1" at fact line 9.
Deep recursion on subroutine "main::fact1" at fact line 9.
Deep recursion on subroutine "main::fact1" at fact line 9.
        f1: 17 wallclock secs (17.09 usr +  0.10 sys = 17.19 CPU) @  0
+.29/s (n=5)
        f4: 15 wallclock secs (15.09 usr +  0.06 sys = 15.15 CPU) @  0
+.33/s (n=5)
        f7:  4 wallclock secs ( 3.99 usr +  0.04 sys =  4.03 CPU) @  1
+.24/s (n=5)
[download]

The difference is negligible for small numbers, but quickly grows to significant magnitude.

Makeshifts last the longest.

---

---

• Are you posting in the right place? Check out Where do I post X? to know for sure.
• Posts may use any of the Perl Monks Approved HTML tags. Currently these include the following:

  <code> <a> <b> <big> <blockquote> <br /> <dd> <dl> <dt> <em> <font> <h1> <h2> <h3> <h4> <h5> <h6> <hr /> <i> <li> <nbsp> <ol> <p> <small> <strike> <strong> <sub> <sup> <table> <td> <th> <tr> <tt> <u> <ul>

• Snippets of code should be wrapped in <code> tags not <pre> tags. In fact, <pre> tags should generally be avoided. If they must be used, extreme care should be taken to ensure that their contents do not have long lines (<70 chars), in order to prevent horizontal scrolling (and possible janitor intervention).
• Want more info? How to link or How to display code and escape characters are good places to start.