in reply to Re: Re: Hypergeometric Probability Calculation
in thread Hypergeometric Probability Calculation
Two points. I found that if I used Math::BigFloat in the
choose function, I got round off errors; errors I didn't
get when using Math::BigInt.
Second, I got a much better performance for the choose function if I didn't calculate 3 factorials, but just one, and did some multiplication myself. The further the second argument is away from half of the first argument, the bigger the advantage. Here's a benchmark:
#!/usr/bin/perl use strict; use warnings; use Math::BigFloat; use Benchmark qw /timethese cmpthese/; # # choose (n, k) == n! / ((n - k)! * k!) == n! / (n - k)! / k! # == n * (n - 1) * ... * (n - k + 1) / k! sub choose_fac { my ($n, $k) = @_; Math::BigInt -> new ($n) -> bfac / Math::BigInt -> new ($n - $k) -> bfac / Math::BigInt -> new ($k) -> bfac } sub choose_mul { my ($n, $k) = @_; $k = $n - $k if $k > $n - $k; # Make the loop smaller; # we can do this because # choose (n, k) == choose (n, n - k +). my $p = Math::BigInt -> new (1); my $start = $n - $k + 1; for (my $i = $start; $i <= $n; $i ++) { $p *= $i; } $p / Math::BigInt -> new ($k) -> bfac; } our (@r1, @r2); our @pairs = map {[/(\d+)\s+(\d+)/]} <DATA>; cmpthese -10 => { fac => '@r1 = map {choose_fac @$_} @pairs', mul => '@r2 = map {choose_mul @$_} @pairs', }; die "Unequal" unless "@r1" eq "@r2"; __DATA__ 1000 0 1000 100 1000 500 1000 1000 s/iter fac mul fac 2.08 -- -89% mul 0.226 824% --
Abigail
|
---|
Replies are listed 'Best First'. | |
---|---|
Re: Re: Hypergeometric Probability Calculation (speeding up 'choose' )
by tilly (Archbishop) on Dec 05, 2003 at 16:50 UTC | |
by Itatsumaki (Friar) on Mar 22, 2004 at 05:28 UTC | |
by tilly (Archbishop) on Mar 23, 2004 at 02:42 UTC | |
by Itatsumaki (Friar) on Mar 29, 2004 at 17:45 UTC | |
by QM (Parson) on Mar 22, 2004 at 05:44 UTC | |
Re: Re: Hypergeometric Probability Calculation (speeding up 'choose' )
by Itatsumaki (Friar) on Dec 05, 2003 at 17:12 UTC |
In Section
Seekers of Perl Wisdom