NumSeq/Factorials.pm

filter: Statementstmt 87.5% 119 / 136 Branchbran 73.8% 31 / 42 Conditioncond 72.7% 8 / 11 MC/DCmcdc 42.8% 3 / 7 Subroutinesub 91.6% 22 / 24 Podpod 100% 8 / 8 totaltotal 83.7% 191 / 228 CC 26 SCAR 13.9
CC
26
Cov
84%
_UNTESTED__value_to_i_ceil
12.0
value_to_i_floor
6.4
value_to_i
6.1
CRAP 4.0
« NumSeq/Polygonal.pm ↑ Summary NumSeq/NumAronson.pm »
1 # Copyright 2010, 2011, 2012, 2013, 2014, 2016, 2019, 2020 Kevin Ryde
2  
3 # This file is part of Math-NumSeq.
4 #
5 # Math-NumSeq is free software; you can redistribute it and/or modify
6 # it under the terms of the GNU General Public License as published by the
7 # Free Software Foundation; either version 3, or (at your option) any later
8 # version.
9 #
10 # Math-NumSeq is distributed in the hope that it will be useful, but
11 # WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
12 # or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
13 # for more details.
14 #
15 # You should have received a copy of the GNU General Public License along
16 # with Math-NumSeq. If not, see <http://www.gnu.org/licenses/>.
17  
18  
19 # http://www.luschny.de/math/factorial/approx/SimpleCases.html
20 #
21  
22  
23 package Math::NumSeq::Factorials;
24 2 ▶use 5.004;
Subroutine BEGIN: called CC=1 SCAR=0.0
25 2 ▶use strict;
Subroutine BEGIN: called CC=1 SCAR=0.0
26  
27 2 ▶use vars '$VERSION','@ISA';
Subroutine BEGIN: called CC=1 SCAR=0.0
28 2 $VERSION = 75;
29  
30 2 ▶use Math::NumSeq;
Subroutine BEGIN: called CC=1 SCAR=0.0
31 2 @ISA = ('Math::NumSeq');
32 2 *_is_infinite = \&Math::NumSeq::_is_infinite;
33  
34 2 ▶use Math::NumSeq::Fibonacci;
Subroutine BEGIN: called CC=1 SCAR=0.0
35 2 *_blog2_estimate = \&Math::NumSeq::Fibonacci::_blog2_estimate;
36  
37 # uncomment this to run the ### lines
38 #use Smart::Comments;
39  
40  
41 # use constant name => Math::NumSeq::__('Factorials');
42 2 ▶use constant description => Math::NumSeq::__('The factorials 1, 2, 6, 24, 120, etc, 1*2*...*N.');
Subroutine BEGIN: called CC=1 SCAR=0.0
43 2 ▶use constant values_min => 1;
Subroutine BEGIN: called CC=1 SCAR=0.0
44 2 ▶use constant i_start => 0;
Subroutine BEGIN: called CC=1 SCAR=0.0
45 2 ▶use constant characteristic_increasing => 1;
Subroutine BEGIN: called CC=1 SCAR=0.0
46 2 ▶use constant characteristic_integer => 1;
Subroutine BEGIN: called CC=1 SCAR=0.0
47  
48 #------------------------------------------------------------------------------
49 # cf A006882 double a(n)=n*a(n-2), n*(n-2)*(n-4)*...*3*1 or *4*2
50 # A001147 double factorial 1*3*5*...*(2n-1) odd numbers, bisection
51 # A000165 double factorial 2*4*6*...*2n even numbers, bisection
52 #
53 # A007661 triple a(n)=n*a(n-3)
54 # A007662 quadruple a(n)=n*a(n-4)
55 # A047053 quad 4^n*n! quad on multiples of 4
56 # A007696 quad n=4k+1 products
57 # A001813 quad (2*n)!/n!
58 # A008545 quad n=4k+1 products
59 # A080500 squares n*(n-1)*(n-4)*(n-9)*(n-16)*(n-25)*...*1
60 #
61 # A001013 Jordan-Polya products of factorials
62 #
63 # A008906 n! num digits excl trailing zeros
64 # A027868 n! num trailing zeros, is power of 5
65 # A000966 n! never ends these 0s
66 #
67 # A008904 n! low non-zero
68 # A136690 base 3
69 # A136691 base 4
70 # A136692 base 5
71 # A136693 base 6
72 # A136694 base 7
73 # A136695 base 8
74 # A136696 base 9
75 # A136697 base 11
76 # A136698 base 12
77 # A136699 base 13
78 # A136700 base 14
79 # A136701 base 15
80 # A136702 base 16
81 #
82 # A008905 n! leading digit
83 # A136754 base 3
84 # A136755 base 4
85 # A136756 base 5
86 # A136757 base 6
87 # A136758 base 7
88 # A136759 base 8
89 # A136760 base 9
90 # A136761 base 11
91 # A136762 base 12
92 # A136763 base 13
93 # A136764 base 14
94 # A136765 base 15
95 # A136766 base 16
96  
97 2 ▶use constant oeis_anum => 'A000142'; # factorials 1,1,2,6,24, including 0!==1
Subroutine BEGIN: called CC=1 SCAR=0.0
98  
99 #------------------------------------------------------------------------------
100  
101  
102 2 ▶use constant 1.02; # for leading underscore
Subroutine BEGIN: called CC=1 SCAR=0.0
103 2 ▶use constant _UV_I_LIMIT => do {
Subroutine BEGIN: called CC=3 SCAR=11.0
104 2 my $u = ~0 >> 1;
105 2 my $limit = 1;
106 2 my $i = 2;
107 2 ▶ for (; $i++; ) {
Branch: 1 branch
BranchTrueFalseTotal
if ($i++) 38 0 38
108 38 ▶ if ($u < $i) {
Branch: 1 branch
BranchTrueFalseTotal
if ($u < $i) 2 36 38
109 ### _UV_LIMIT stop before: "i=$i"
110 2 last;
111 }
112 36 $u -= ($u % $i);
113 36 $u /= $i;
114 36 $limit *= $i;
115 }
116 ### $limit
117 ### $i
118 2 $i
119 2 };
120 ### _UV_I_LIMIT: _UV_I_LIMIT()
121  
122 2 ▶use constant _NV_LIMIT => do {
Subroutine BEGIN: called CC=3 SCAR=11.0
123 2 my $f = 1.0;
124 2 my $max;
125 2 for (;;) {
126 106 $max = $f;
127 106 my $l = 2.0*$f;
128 106 my $h = 2.0*$f+2.0;
129 106 $f = 2.0*$f + 1.0;
130 106 $f = sprintf '%.0f', $f;
131 106 ▶ last unless ($f < $h && $f > $l);
Branch: 1 branch
BranchTrueFalseTotal
unless $f < $h and $f > $l 2 104 106
Condition66%2/3
$f < $h and $f > $l
!ll&&!rl&&r
20104
MC/DC50%1/2
$f < $h and $f > $l
$f < $h $f > $l
Truth table66%2/3
A and B
A= $f < $hB= $f > $l
ABresult
0X0
100
111
132 }
133 ### uv : ~0
134 ### 53 : 1<<53
135 ### $max
136 2 $max
137 2 };
138  
139  
140  
141 7 ▶sub rewind {
Subroutine rewind: called CC=1 SCAR=0.0
Pod documented
142 7 my ($self) = @_;
143 ### Factorials rewind()
144 7 $self->{'i'} = $self->i_start;
145 7 $self->{'f'} = 1;
146 }
147 20 ▶sub seek_to_i {
Subroutine seek_to_i: called CC=1 SCAR=0.0
Pod documented
148 20 my ($self, $i) = @_;
149 20 $self->{'i'} = $i;
150 20 $self->{'f'} = $self->ith($i-1);
151 }
152 0 ▶sub _UNTESTED__seek_to_value {
Subroutine _UNTESTED__seek_to_value: not called CC=1 SCAR=6.9
153 0 my ($self, $value) = @_;
154 0 my $i = $self->{'i'} = $self->value_to_i_ceil($value);
155 0 $self->{'f'} = $self->ith($i);
156 }
157 55 ▶sub next {
Subroutine next: called CC=3 SCAR=11.3
Pod documented
158 55 my ($self) = @_;
159 ### Factorials next() ...
160  
161 55 my $i = $self->{'i'}++;
162 55 ▶ if ($i == _UV_I_LIMIT) {
Branch: 1 branch
BranchTrueFalseTotal
if ($i == 21) 0 55 55
163 0 $self->{'f'} = Math::NumSeq::_to_bigint($self->{'f'});
164 }
165 55 ▶ return ($i, $self->{'f'} *= ($i||1));
Condition100%2/2
$i || 1
l!l
514
MC/DC100%1/1
$i || 1
$i
Truth table100%2/2
A
A= $i
Aresult
11
00
166 }
167  
168 57 ▶sub ith {
Subroutine ith: called CC=5 SCAR=16.3
Pod documented
169 57 my ($self, $i) = @_;
170 ### Factorials ith() ...
171  
172 57 ▶ if (_is_infinite($i)) {
Branch: 1 branch
BranchTrueFalseTotal
if (_is_infinite($i)) 0 57 57
173 0 return $i;
174 }
175  
176 57 ▶ if (! ref $i && $i >= _UV_I_LIMIT) {
Branch: 1 branch
BranchTrueFalseTotal
if (not ref $i and $i >= 21) 3 54 57
Condition66%2/3
not ref $i and $i >= 21
!ll&&!rl&&r
0543
MC/DC50%1/2
not ref $i and $i >= 21
not ref $i $i >= 21
Truth table66%2/3
not(A) and B
A= not ref $iB= $i >= 21
ABresult
0X0
100
111
177 # Plain index $i automatically use Math::BigInt when UV limit reached.
178 # Maybe should check if BigInt new enough to have bfac(), circa vers 1.60
179 3 return Math::NumSeq::_bigint()->bfac($i);
180 }
181  
182 54 my $value = ($i*0) + 1; # inherit bignum 1
183 54 ▶ while ($i >= 2) {
Branch: 1 branch
BranchTrueFalseTotal
if ($i >= 2) 168 54 222
184 168 $value *= $i;
185 168 $i -= 1;
186 }
187 54 return $value;
188 }
189  
190 1463 ▶sub pred {
Subroutine pred: called CC=1 SCAR=0.0
Pod documented
191 1463 my ($self, $value) = @_;
192 1463 return defined($self->value_to_i($value));
193 }
194 1495 ▶sub value_to_i {
Subroutine value_to_i: called CC=6 SCAR=18.0
Pod documented
195 1495 my ($self, $value) = @_;
196  
197 # NV inf or nan gets $value%$i=nan and nan==0 is false,
198 # but Math::BigInt binf()%$i=0 so would go into infinite loop
199 # hence explicit check against _is_infinite()
200 #
201 1495 ▶ if (_is_infinite($value)) {
Branch: 1 branch
BranchTrueFalseTotal
if (_is_infinite($value)) 0 1495 1495
202 0 return undef;
203 }
204  
205 1495 ▶ if ($value == 1) {
Branch: 1 branch
BranchTrueFalseTotal
if ($value == 1) 8 1487 1495
206 8 return 0;
207 }
208  
209 1487 my $i = 1;
210 1487 for (;;) {
211 2589 ▶ if ($value <= 1) {
Branch: 1 branch
BranchTrueFalseTotal
if ($value <= 1) 31 2558 2589
212 31 ▶ return ($value == 1 ? $i : undef);
Branch: 1 branch
BranchTrueFalseTotal
$value == 1 ? : 24 7 31
213 }
214 2558 $i++;
215 2558 ▶ if (($value % $i) == 0) {
Branch: 1 branch
BranchTrueFalseTotal
if ($value % $i == 0) { } 1102 1456 2558
216 1102 $value /= $i;
217 } else {
218 1456 return undef;
219 }
220 }
221 0 return $i;
222 }
223  
224 52 ▶sub value_to_i_floor {
Subroutine value_to_i_floor: called CC=6 SCAR=18.5
Pod documented
225 52 my ($self, $value) = @_;
226 52 ▶ if (_is_infinite($value)) {
Branch: 1 branch
BranchTrueFalseTotal
if (_is_infinite($value)) 0 52 52
227 0 return $value;
228 }
229 52 ▶ if ($value < 2) {
Branch: 1 branch
BranchTrueFalseTotal
if ($value < 2) 14 38 52
230 14 return $self->i_start;
231 }
232  
233 # "/" operator converts 64-bit UV to an NV and so loses bits, making the
234 # result come out 1 too small sometimes. Experimental switch to BigInt to
235 # keep precision. ENHANCE-ME: Maybe better _divrem().
236 #
237 38 ▶ if (! ref $value && $value > _NV_LIMIT) {
Branch: 1 branch
BranchTrueFalseTotal
if (not ref $value and $value > '9007199254740991') 0 38 38
Condition66%2/3
not ref $value and $value > '9007199254740991'
!ll&&!rl&&r
5330
MC/DC0%0/2
not ref $value and $value > '9007199254740991'
not ref $value $value > '9007199254740991'
Truth table66%2/3
not(A) and B
A= not ref $valueB= $value > '9007199254740991'
ABresult
0X0
100
111
238 0 $value = Math::NumSeq::_to_bigint($value);
239 }
240  
241 38 my $i = 2;
242 38 for (;; $i++) {
243 ### $value
244 ### $i
245  
246 137 ▶ if ($value < $i) {
Branch: 1 branch
BranchTrueFalseTotal
if ($value < $i) 38 99 137
247 38 return $i-1;
248 }
249 99 $value = int($value/$i);
250 }
251 }
252  
253 # ENHANCE-ME: should be able to notice rounding in $value/$i divisions of
254 # value_to_i_floor(), rather than multiplying back.
255 #
256 0 ▶sub _UNTESTED__value_to_i_ceil {
Subroutine _UNTESTED__value_to_i_ceil: not called CC=3 SCAR=24.8
257 0 my ($self, $value) = @_;
258 0 ▶ if ($value < 0) { return 0; }
Branch: 1 branch
BranchTrueFalseTotal
if ($value < 0) 0 0 0
259 0 my $i = $self->value_to_i_floor($value);
260 0 ▶ if ($self->ith($i) < $value) {
Branch: 1 branch
BranchTrueFalseTotal
if ($self->ith($i) < $value) 0 0 0
261 0 $i += 1;
262 }
263 0 return $i;
264 }
265  
266  
267 #--------
268 # Stirling
269 # n! ~= sqrt(2pi*n) * binomial(n,e)^n
270 # n! ~= sqrt(2*Pi) * n^(n+1/2) / e^n
271 # log(i!) ~= i*log(i) - i
272 #
273 # f(x) = x*log(x) - x - t
274 # f'(x) = log(x)
275 # sub = f(x) / f'(x)
276 # = (x*log(x) - x - t) / log(x)
277 # = x - (x+t)/log(x)
278 # new = x - sub
279 # = x - (x - (x+t)/log(x))
280 # = (x+t)/log(x)
281 #
282 # start x=t
283 # new1 = 2t/log(t)
284 # new2 = (2t/log(t) + t) / log(2t/log(t))
285 # = (2t/log(t) + t) / (log(2t) - log(log(t)))
286 #
287 # log2(i!) = log(i!)/log(2)
288 # ~= (i*log(i) - i)/log(2)
289 # log2(i!)*log(2) ~= i*log(i) - i
290 #
291 #--------
292 # Gosper, approximating terms of Stirling series
293 #
294 # n! ~= sqrt((2n+1/3)pi) * n^n * e^-n
295 #
296 16 ▶sub value_to_i_estimate {
Subroutine value_to_i_estimate: called CC=4 SCAR=13.9
Pod documented
297 16 my ($self, $value) = @_;
298 ### value_to_i_estimate: $value
299  
300 16 ▶ if ($value <= 1) {
Branch: 1 branch
BranchTrueFalseTotal
if ($value <= 1) 10 6 16
301 10 return 0;
302 }
303 6 ▶ if ($value <= 3) {
Branch: 1 branch
BranchTrueFalseTotal
if ($value <= 3) 0 6 6
304 0 return 1;
305 }
306  
307 6 my $t;
308 6 ▶ if (defined (my $blog2 = _blog2_estimate($value))) {
Branch: 1 branch
BranchTrueFalseTotal
if (defined(my $blog2 = _blog2_estimate($value))) { } 1 5 6
309 1 $t = $blog2 * log(2);
310 } else {
311 5 $t = log($value);
312 }
313  
314 # two steps of Newton's method
315 6 my $x = 2*$t/log($t);
316 6 return int(($x+$t)/log($x));
317  
318  
319 # # single step of Newton's method starting x=t
320 # # x-1 is a touch under the true i, so just int() down
321 # return int(2*$t/log($t));
322 #
323 # multiple steps
324 # my $x = $t;
325 # for (1 .. 10) {
326 # ### $x
327 # ### log: log($x)
328 # ### f: ($x*log($x)-$x - $t)
329 # ### fd: log($x)
330 # ### sub: ($x*log($x) - $x - $t)/log($x)
331 # ### new: ($x+$t)/log($x)
332 #
333 # $x = ($x+$t)/log($x);
334 # }
335 # return int($x)-1;
336 }
337  
338 2 1;
339 __END__
« NumSeq/Polygonal.pm ↑ Summary NumSeq/NumAronson.pm »