The recursive algorithm multiplies smallest to largest, so most of the multiplications take place with the smallest number. The iterative algorithm multiplies largest to smallest so you are multiplying against a very, very big number a lot. Try this iterative implementation that mimics the order of operations in the recursive solution and see if it isn't faster:
sub fact4{
#no recursion at all
my $n = Math::BigInt->new(1);
foreach my $i (map Math::BigInt->new($_), 1..shift) {
$n = Math::BigInt->new($i->bmul($n));
}
return $n;
}
Also the order of the terms seems to matter. This version is not quite as fast:
sub fact5{
#no recursion at all
my $n = Math::BigInt->new(1);
foreach my $i (1..shift) {
$n = Math::BigInt->new($n->bmul($i));
}
return $n;
}
And since most of the time is spent dealing with multiplying big numbers, perhaps you want to divide fewer big numbers? The following is much faster than any other approach given because it limits multiplications with big numbers, but you have to pass it the raw number because Math::BigInt objects do not play well with the averaging manipulation it does:
sub fact6{
#divide and conquer
my $m = shift;
my $n = @_ ? shift : $m;
if ($m < $n) {
my $k = int($m/2 + $n/2);
return Math::BigInt->new(fact6($m, $k))->bmul(fact6($k+1,$n));
}
else {
return Math::BigInt->new($m);
}
}
