1package Bio::Phylo::Util::Math; 2use strict; 3use warnings; 4use base 'Exporter'; 5 6BEGIN { 7 our ( @EXPORT_OK, %EXPORT_TAGS ); 8 @EXPORT_OK = qw(nchoose gcd gcd_divide); 9 %EXPORT_TAGS = ( 10 'all' => [@EXPORT_OK], 11 ); 12} 13 14=head1 NAME 15 16Bio::Phylo::Util::Math - Utility math functions 17 18=head1 EXPORTED FUNCTIONS 19 20=over 21 22=item nchoose_static 23 24Calculation of n choose j. This version saves partial results for use later. 25 26 Type : Exported function 27 Title : nchoose_static 28 Usage : $c = nchoose_static( $n, $j ) 29 Function: Calculation of n choose j. 30 Returns : n-choose 31 Args : $n, $j 32 33=cut 34 35# Calculation of n choose j 36# This version saves partial results for use later 37my @nc_matrix; #stores the values of nchoose(n,j) 38# -- note: order of indices is reversed 39sub nchoose_static { 40 my ( $n, $j, @nc_matrix ) = @_; 41 return 0 if $j > $n; 42 if ( @nc_matrix < $j + 1 ) { 43 push @nc_matrix, [] for @nc_matrix .. $j; 44 } 45 if ( @{ $nc_matrix[$j] } < $n + 1 ) { 46 push @{ $nc_matrix[$j] }, 0 for @{ $nc_matrix[$j] } .. $j - 1; 47 } 48 push @{ $nc_matrix[$j] }, 1 if @{ $nc_matrix[$j] } == $j; 49 for my $i ( @{ $nc_matrix[$j] } .. $n ) { 50 push @{ $nc_matrix[$j] }, $nc_matrix[$j]->[$i-1] * $i / ( $i - $j ); 51 } 52 return $nc_matrix[$j]->[$n]; 53} 54 55=item nchoose 56 57Calculation of n choose j. Dynamic version. 58 59 Type : Exported function 60 Title : nchoose 61 Usage : $c = nchoose( $n, $j ) 62 Function: Calculation of n choose j. 63 Returns : n-choose 64 Args : $n, $j 65 66=cut 67 68# dynamic programming version 69sub nchoose { 70 my ( $n, $j ) = @_; 71 return nchoose_static($n,$j,@nc_matrix); 72} 73 74=item gcd 75 76Greatest common denominator - assumes positive integers as input 77 78 Type : Exported function 79 Title : gcd 80 Usage : $gcd = gcd( $n, $m ) 81 Function: Greatest common denominator 82 Returns : $gcd 83 Args : $n, $m 84 85=cut 86 87# GCD - assumes positive integers as input 88# (subroutine for compare(t,u,v)) 89sub gcd { 90 my ( $n, $m ) = @_; 91 return $n if $n == $m; 92 ( $n, $m ) = ( $m, $n ) if $m > $n; 93 my $i = int($n / $m); 94 $n = $n - $m * $i; 95 return $m if $n == 0; 96 97 # recurse 98 return gcd($m,$n); 99} 100 101=item gcd_divide 102 103Takes two large integers and attempts to divide them and give 104the float answer without overflowing 105 106 Type : Exported function 107 Title : gcd_divide 108 Usage : $gcd = gcd_divide( $n, $m ) 109 Function: Greatest common denominator 110 Returns : $gcd 111 Args : $n, $m 112 113=cut 114 115# Takes two large integers and attempts to divide them and give 116# the float answer without overflowing 117# (subroutine for compare(t,u,v)) 118# does this by first taking out the greatest common denominator 119sub gcd_divide { 120 my ( $n, $m ) = @_; 121 my $x = gcd($n,$m); 122 $n /= $x; 123 $m /= $x; 124 return $n/$m; 125} 126 127=back 128 129=head1 SEE ALSO 130 131There is a mailing list at L<https://groups.google.com/forum/#!forum/bio-phylo> 132for any user or developer questions and discussions. 133 134=over 135 136=item L<Bio::Phylo::Manual> 137 138Also see the manual: L<Bio::Phylo::Manual> and L<http://rutgervos.blogspot.com>. 139 140=back 141 142=head1 CITATION 143 144If you use Bio::Phylo in published research, please cite it: 145 146B<Rutger A Vos>, B<Jason Caravas>, B<Klaas Hartmann>, B<Mark A Jensen> 147and B<Chase Miller>, 2011. Bio::Phylo - phyloinformatic analysis using Perl. 148I<BMC Bioinformatics> B<12>:63. 149L<http://dx.doi.org/10.1186/1471-2105-12-63> 150 151=cut 152 1531;