in reply to Factorial algorithm execution time

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]

Replies are listed 'Best First'.
Re: Re: Factorial algorithm execution time
by gri6507 (Deacon) on Oct 18, 2002 at 14:05 UTC
    I don't think I understand your algorithm here. When trying to calculate, say 100!, what should the second argument be?

    I thought about this method, but I opted to try out a different method. You are correct in saying that much time is spent multiplying numbers. So what we can do is get rid of that multiplication and turn it into addition. This can be easily done by first taking logs of all integers in the factorial calculation, summing those values and finally raising e to that power. For example, 5!=e^(ln(2)*ln(2)*ln(4)*ln(5)). There is only one problem with that. Since Math::BigFloat does not contain a log or exp function, the limited precision of the built in functions creates a rounded answer (try doing 200!)

[reply]
      Try print fact6(1, 100); It multiplies everything from the first to the last arguments inclusive. But it will not work if you pass it a Math::BigInt object.

      It works by calculating fact6(1,100) as fact6(1,50)*fact6(51,100). Break those up likewise until you have a range of one number, and you know how to calculate that. So there are very few multiplications with very large numbers.

[reply]
[d/l]
        Ah. That won't work as well as the next greatest with next smallest pairing I cooked up in keeping factors small, though, and it's recursive and more complicated as well.

        Makeshifts last the longest.

[reply]

      You need not pass a second parameter to that function - or so it appears. A quick test shows it being broken. I'm not sure I'm following the algorithm either, so I'll leave it at that. (I misunderstood the parameter handling.)

      Also summing the logarithms will be fast, but calculating the logarithms in the first place is going to take much longer than straight multiplication would have.

      Makeshifts last the longest.

[reply]
      Thanks to zigdon for pointing out my mistakes. The example above should be 5!=e^(ln(2)+ln(3)+ln(4)+ln(5))
[reply]

In Section Seekers of Perl Wisdom