`#
# 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. |
Comment onRe: Hypergeometric Probability Calculation (speeding up 'choose' )DownloadCode