| 1 | package Bio::Phylo::Util::Math; | ||||||||||
| 2 | 34 | ▶ | use strict; | ||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||
| 3 | 34 | ▶ | use warnings; | ||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||
| 4 | 34 | ▶ | use base 'Exporter'; | ||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||
| 5 | |||||||||||
| 6 | 34 | ▶ | BEGIN { | ||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||
| 7 | 34 | our ( @EXPORT_OK, %EXPORT_TAGS ); | |||||||||
| 8 | 34 | @EXPORT_OK = qw(nchoose gcd gcd_divide); | |||||||||
| 9 | 34 | %EXPORT_TAGS = ( | |||||||||
| 10 | 'all' => [@EXPORT_OK], | ||||||||||
| 11 | ); | ||||||||||
| 12 | } | ||||||||||
| 13 | |||||||||||
| 14 | =head1 NAME | ||||||||||
| 15 | |||||||||||
| 16 | Bio::Phylo::Util::Math - Utility math functions | ||||||||||
| 17 | |||||||||||
| 18 | =head1 EXPORTED FUNCTIONS | ||||||||||
| 19 | |||||||||||
| 20 | =over | ||||||||||
| 21 | |||||||||||
| 22 | =item nchoose_static | ||||||||||
| 23 | |||||||||||
| 24 | Calculation 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 | ||||||||||
| 37 | 34 | my @nc_matrix; #stores the values of nchoose(n,j) | |||||||||
| 38 | # -- note: order of indices is reversed | ||||||||||
| 39 | 1020 | ▶ | sub nchoose_static { | ||||||||
|
Subroutine
nchoose_static: called CC=8 SCAR=21.1
Pod
documented
| |||||||||||
| 40 | 1020 | my ( $n, $j, @nc_matrix ) = @_; | |||||||||
| 41 | 1020 | ▶ | return 0 if $j > $n; | ||||||||
|
Branch: 1 branch
| |||||||||||
| 42 | 1020 | ▶ | if ( @nc_matrix < $j + 1 ) { | ||||||||
|
Branch: 1 branch
| |||||||||||
| 43 | 1020 | push @nc_matrix, [] for @nc_matrix .. $j; | |||||||||
| 44 | } | ||||||||||
| 45 | 1020 | ▶ | if ( @{ $nc_matrix[$j] } < $n + 1 ) { | ||||||||
|
Branch: 1 branch
| |||||||||||
| 46 | 1020 | push @{ $nc_matrix[$j] }, 0 for @{ $nc_matrix[$j] } .. $j - 1; | |||||||||
| 47 | } | ||||||||||
| 48 | 1020 | ▶ | push @{ $nc_matrix[$j] }, 1 if @{ $nc_matrix[$j] } == $j; | ||||||||
|
Branch: 1 branch
| |||||||||||
| 49 | 1020 | for my $i ( @{ $nc_matrix[$j] } .. $n ) { | |||||||||
| 50 | 1073 | push @{ $nc_matrix[$j] }, $nc_matrix[$j]->[$i-1] * $i / ( $i - $j ); | |||||||||
| 51 | } | ||||||||||
| 52 | 1020 | return $nc_matrix[$j]->[$n]; | |||||||||
| 53 | } | ||||||||||
| 54 | |||||||||||
| 55 | =item nchoose | ||||||||||
| 56 | |||||||||||
| 57 | Calculation 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 | ||||||||||
| 69 | 1020 | ▶ | sub nchoose { | ||||||||
|
Subroutine
nchoose: called CC=1 SCAR=0.0
Pod
documented
| |||||||||||
| 70 | 1020 | my ( $n, $j ) = @_; | |||||||||
| 71 | 1020 | return nchoose_static($n,$j,@nc_matrix); | |||||||||
| 72 | } | ||||||||||
| 73 | |||||||||||
| 74 | =item gcd | ||||||||||
| 75 | |||||||||||
| 76 | Greatest 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)) | ||||||||||
| 89 | 0 | ▶ | sub gcd { | ||||||||
|
Subroutine
gcd: not called CC=4 SCAR=30.0
Pod
documented
| |||||||||||
| 90 | 0 | my ( $n, $m ) = @_; | |||||||||
| 91 | 0 | ▶ | return $n if $n == $m; | ||||||||
|
Branch: 1 branch
| |||||||||||
| 92 | 0 | ▶ | ( $n, $m ) = ( $m, $n ) if $m > $n; | ||||||||
|
Branch: 1 branch
| |||||||||||
| 93 | 0 | my $i = int($n / $m); | |||||||||
| 94 | 0 | $n = $n - $m * $i; | |||||||||
| 95 | 0 | ▶ | return $m if $n == 0; | ||||||||
|
Branch: 1 branch
| |||||||||||
| 96 | |||||||||||
| 97 | # recurse | ||||||||||
| 98 | 0 | return gcd($m,$n); | |||||||||
| 99 | } | ||||||||||
| 100 | |||||||||||
| 101 | =item gcd_divide | ||||||||||
| 102 | |||||||||||
| 103 | Takes two large integers and attempts to divide them and give | ||||||||||
| 104 | the 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 | ||||||||||
| 119 | 0 | ▶ | sub gcd_divide { | ||||||||
|
Subroutine
gcd_divide: not called CC=1 SCAR=6.9
Pod
documented
| |||||||||||
| 120 | 0 | my ( $n, $m ) = @_; | |||||||||
| 121 | 0 | my $x = gcd($n,$m); | |||||||||
| 122 | 0 | $n /= $x; | |||||||||
| 123 | 0 | $m /= $x; | |||||||||
| 124 | 0 | return $n/$m; | |||||||||
| 125 | } | ||||||||||
| 126 | |||||||||||
| 127 | =back | ||||||||||
| 128 | |||||||||||
| 129 | =head1 SEE ALSO | ||||||||||
| 130 | |||||||||||
| 131 | There is a mailing list at L<https://groups.google.com/forum/#!forum/bio-phylo> | ||||||||||
| 132 | for any user or developer questions and discussions. | ||||||||||
| 133 | |||||||||||
| 134 | =over | ||||||||||
| 135 | |||||||||||
| 136 | =item L<Bio::Phylo::Manual> | ||||||||||
| 137 | |||||||||||
| 138 | Also see the manual: L<Bio::Phylo::Manual> and L<http://rutgervos.blogspot.com>. | ||||||||||
| 139 | |||||||||||
| 140 | =back | ||||||||||
| 141 | |||||||||||
| 142 | =head1 CITATION | ||||||||||
| 143 | |||||||||||
| 144 | If you use Bio::Phylo in published research, please cite it: | ||||||||||
| 145 | |||||||||||
| 146 | B<Rutger A Vos>, B<Jason Caravas>, B<Klaas Hartmann>, B<Mark A Jensen> | ||||||||||
| 147 | and B<Chase Miller>, 2011. Bio::Phylo - phyloinformatic analysis using Perl. | ||||||||||
| 148 | I<BMC Bioinformatics> B<12>:63. | ||||||||||
| 149 | L<http://dx.doi.org/10.1186/1471-2105-12-63> | ||||||||||
| 150 | |||||||||||
| 151 | =cut | ||||||||||
| 152 | |||||||||||
| 153 | 34 | 1; | |||||||||