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;