in reply to Re: Factorial algorithm execution time
in thread Factorial algorithm execution time

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!)

  • Comment on Re: Re: Factorial algorithm execution time

Replies are listed 'Best First'.
Re: Re: Re: Factorial algorithm execution time
by Anonymous Monk on Oct 18, 2002 at 23:29 UTC
    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]
        It won't work as well, but it works well enough. My benchmark for 5000 says: 
        Method 6: 14 wallclock secs (14.31 usr +  0.01 sys = 14.32 CPU)
Method 7: 15 wallclock secs (14.28 usr +  0.01 sys = 14.29 CPU)
Method 8: 14 wallclock secs (14.25 usr +  0.01 sys = 14.26 CPU)

        [download]
        I got rid of the Math::BigInt call on the list of 1 then ran it a bunch of times, and there seemed to be some fluctuation. Another run gave me: 
        Method 6: 14 wallclock secs (14.08 usr +  0.02 sys = 14.10 CPU)
Method 7: 14 wallclock secs (14.14 usr +  0.01 sys = 14.15 CPU)
Method 8: 15 wallclock secs (14.12 usr +  0.01 sys = 14.13 CPU)

        [download]
        Not bad for such a stupid approach, huh?

        In truth yours is better by about as much as you lose because you used the overloading interface. If I use the overloading interface, well 

        sub fact6b{
  my ($m, $n) = @_; 

  if ($m < $n) {
    my $k = int($m/2 + $n/2);
    return my $x = fact6b($m, $k) * fact6b($k+1,$n);
  }
  else {
    return Math::BigInt->new($m);
  }
}

        [download]
        is very straightforward to anyone who has seen divide-and-conquer before. And recursive is only bad because Perl penalizes function calls horribly.

        Of course at this point we are both slow mainly because Perl doesn't implement a good algorithm for big integer multiplication.

[reply]
[d/l]
[select]
Re^3: Factorial algorithm execution time
by Aristotle (Chancellor) on Oct 18, 2002 at 14:44 UTC

    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]
Re: Re: Re: Factorial algorithm execution time
by gri6507 (Deacon) on Oct 18, 2002 at 16:42 UTC
    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