| 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
| |||||||||||||||||||||||||||||
| 108 | 38 | ▶ | if ($u < $i) { | ||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||
| 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
Condition66%2/3
$f < $h and $f > $l
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
| |||||||||||||||||||||||||||||
| 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
| |||||||||||||||||||||||||||||
| 163 | 0 | $self->{'f'} = Math::NumSeq::_to_bigint($self->{'f'}); | |||||||||||||||||||||||||||
| 164 | } | ||||||||||||||||||||||||||||
| 165 | 55 | ▶ | return ($i, $self->{'f'} *= ($i||1)); | ||||||||||||||||||||||||||
|
Condition100%2/2
$i || 1
MC/DC100%1/1
$i || 1
$i
Truth table100%2/2
A
A= $i
| |||||||||||||||||||||||||||||
| 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
| |||||||||||||||||||||||||||||
| 173 | 0 | return $i; | |||||||||||||||||||||||||||
| 174 | } | ||||||||||||||||||||||||||||
| 175 | |||||||||||||||||||||||||||||
| 176 | 57 | ▶ | if (! ref $i && $i >= _UV_I_LIMIT) { | ||||||||||||||||||||||||||
|
Branch: 1 branch
Condition66%2/3
not ref $i and $i >= 21
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
| |||||||||||||||||||||||||||||
| 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
| |||||||||||||||||||||||||||||
| 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
| |||||||||||||||||||||||||||||
| 202 | 0 | return undef; | |||||||||||||||||||||||||||
| 203 | } | ||||||||||||||||||||||||||||
| 204 | |||||||||||||||||||||||||||||
| 205 | 1495 | ▶ | if ($value == 1) { | ||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||
| 206 | 8 | return 0; | |||||||||||||||||||||||||||
| 207 | } | ||||||||||||||||||||||||||||
| 208 | |||||||||||||||||||||||||||||
| 209 | 1487 | my $i = 1; | |||||||||||||||||||||||||||
| 210 | 1487 | for (;;) { | |||||||||||||||||||||||||||
| 211 | 2589 | ▶ | if ($value <= 1) { | ||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||
| 212 | 31 | ▶ | return ($value == 1 ? $i : undef); | ||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||
| 213 | } | ||||||||||||||||||||||||||||
| 214 | 2558 | $i++; | |||||||||||||||||||||||||||
| 215 | 2558 | ▶ | if (($value % $i) == 0) { | ||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||
| 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
| |||||||||||||||||||||||||||||
| 227 | 0 | return $value; | |||||||||||||||||||||||||||
| 228 | } | ||||||||||||||||||||||||||||
| 229 | 52 | ▶ | if ($value < 2) { | ||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||
| 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
Condition66%2/3
not ref $value and $value > '9007199254740991'
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'
| |||||||||||||||||||||||||||||
| 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
| |||||||||||||||||||||||||||||
| 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
| |||||||||||||||||||||||||||||
| 259 | 0 | my $i = $self->value_to_i_floor($value); | |||||||||||||||||||||||||||
| 260 | 0 | ▶ | if ($self->ith($i) < $value) { | ||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||
| 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
| |||||||||||||||||||||||||||||
| 301 | 10 | return 0; | |||||||||||||||||||||||||||
| 302 | } | ||||||||||||||||||||||||||||
| 303 | 6 | ▶ | if ($value <= 3) { | ||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||
| 304 | 0 | return 1; | |||||||||||||||||||||||||||
| 305 | } | ||||||||||||||||||||||||||||
| 306 | |||||||||||||||||||||||||||||
| 307 | 6 | my $t; | |||||||||||||||||||||||||||
| 308 | 6 | ▶ | if (defined (my $blog2 = _blog2_estimate($value))) { | ||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||
| 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__ | ||||||||||||||||||||||||||||