The stupid question is the question not asked PerlMonks

### Re: Re: Hypergeometric Probability Calculation (speeding up 'choose' )

by tilly (Archbishop)
 on Dec 05, 2003 at 16:50 UTC ( #312553=note: print w/replies, xml ) Need Help??

I just peeked in Math::Big. The factorial implementation is very slow.

You should find a significant performance improvement with:

```#
# 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.

Replies are listed 'Best First'.
Re: Re: Re: Hypergeometric Probability Calculation (speeding up 'choose' )
by Itatsumaki (Friar) on Mar 22, 2004 at 05:28 UTC

Just looking back at this now and saw your updates. I wonder Math::Big couldn't/shouldn't be rewritten to use C-code for large integer operations. My thought is that even if Perl itself isn't good for numerical calculations, when using a CPAN module for it, an XS implementation for processing would be a big performance win, without much of a complexity increase for module-users.

-Tats
Install Math::BigInt::GMP and use Math::BigInt lib => 'GMP'; and things get much faster. You can distribute code in with that use, without the module locally installed everything still works, it just falls back on a slow Perl version. (Some may prefer Math::BigInt::Pari.)

Math::Big is meant to be a convenient wrapper around other modules. Use a faster one and it gets faster. Use a slower one, and it isn't.

sweet, this works great! Thanks tilly

-Tats
There is a module that uses XS instead of pure Perl (but I forget the name, and can't find it quickly - perhaps someone will enlighten us?).

However, pure Perl solutions are useful for users and situations where XS is not available, even though it's slower.

As stated earlier, pure Perl is not always the best choice when number crunching speed is of critical importance.

-QM
--
Quantum Mechanics: The dreams stuff is made of

Create A New User
Node Status?
node history
Node Type: note [id://312553]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others making s'mores by the fire in the courtyard of the Monastery: (6)
As of 2020-12-04 01:53 GMT
Sections?
Information?
Find Nodes?
Leftovers?
Voting Booth?
How often do you use taint mode?

Results (58 votes). Check out past polls.

Notices?