#
# Usage:
# factorial($n) = 1*2*...*$n
# factorial($m, $n) = $m*($m+1)*...*$n
#
sub factorial {
#divide and conquer
unshift @_, 1 if 2 != @_;
my ($m, $n) = @_;
if ($m < $n) {
my $k = int($m/2 + $n/2);
return factorial($m, $k) * factorial($k+1, $n);
}
else {
return Math::BigInt->new($m);
}
}
(Incremental improvements over that are easily achieved as well.)
I'll submit the suggestion to the maintainer.
UPDATE: I remember the overload interface being slower on old Perl's, but on my machine (5.8.0) it seems marginally faster. So I replaced:
return Math::BigInt->new(factorial($m, $k))->bmul(factorial($k+1,$
+n));
with
return factorial($m, $k) * factorial($k+1, $n);
UPDATE 2: Out of curiousity I wondered how the above Perl would compare with Ruby:
#
# Usage:
# factorial(n) = n*(n-1)*...*1
# factorial(n, m) = n*(n-1)*...*m
def factorial (n, m=1)
if m < n then
k=(m+n)/2;
factorial(k, m) * factorial(n, k+1);
else
m
end
end
This ran about 10x faster than Perl. Of course a naive factorial implementation in Ruby runs several times as fast as the smart one does in Perl.
The difference is mainly what we get for all of the layers of getting around variables autoconverting themselves inappropriately for large integers. If you want to work with large integers, Perl is not the language to do it with. |