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;
}
[download]

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;
}
[download]

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);
  }
}
[download]

---

---

• 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.