NumSeq/DigitLengthCumulative.pm

filter: Statementstmt 93.3% 126 / 135 Branchbran 87.5% 28 / 32 Conditioncond n/a MC/DCmcdc n/a Subroutinesub 95.2% 20 / 21 Podpod 100% 8 / 8 totaltotal 92.8% 182 / 196 CC 17 SCAR 10.9
CC
17
Cov
92%
pred
6.1
value_to_i_floor
5.0
value_to_i_estimate
4.0
CRAP 3.0
« NumSeq/DigitSumModulo.pm ↑ Summary NumSeq/UlamSequence.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 package Math::NumSeq::DigitLengthCumulative;
19 1 ▶use 5.004;
Subroutine BEGIN: called CC=1 SCAR=0.0
20 1 ▶use strict;
Subroutine BEGIN: called CC=1 SCAR=0.0
21  
22 1 ▶use vars '$VERSION', '@ISA';
Subroutine BEGIN: called CC=1 SCAR=0.0
23 1 $VERSION = 75;
24 1 ▶use Math::NumSeq;
Subroutine BEGIN: called CC=1 SCAR=0.0
25 1 @ISA = ('Math::NumSeq');
26 1 *_is_infinite = \&Math::NumSeq::_is_infinite;
27  
28 1 ▶use Math::NumSeq::Fibonacci;
Subroutine BEGIN: called CC=1 SCAR=0.0
29 1 *_blog2_estimate = \&Math::NumSeq::Fibonacci::_blog2_estimate;
30  
31 use Math::NumSeq::Base::Digits
32 1 ▶ 'parameter_info_array'; # radix parameter
Subroutine BEGIN: called CC=1 SCAR=0.0
33  
34 # uncomment this to run the ### lines
35 #use Smart::Comments;
36  
37  
38 1 ▶use vars '$VERSION';
Subroutine BEGIN: called CC=1 SCAR=0.0
39 1 $VERSION = 75;
40  
41 # use constant name => Math::NumSeq::__('Digit Length Cumulative');
42 1 ▶use constant description => Math::NumSeq::__('Cumulative length of numbers 0,1,2,3,etc written out in the given radix. For example binary 1,2,4,6,9,12,15,18,22,etc, 2 steps by 2, then 4 steps by 3, then 8 steps by 4, then 16 steps by 5, etc.');
Subroutine BEGIN: called CC=1 SCAR=0.0
43 1 ▶use constant i_start => 0;
Subroutine BEGIN: called CC=1 SCAR=0.0
44 1 ▶use constant values_min => 1;
Subroutine BEGIN: called CC=1 SCAR=0.0
45 1 ▶use constant characteristic_increasing => 1;
Subroutine BEGIN: called CC=1 SCAR=0.0
46 1 ▶use constant characteristic_integer => 1;
Subroutine BEGIN: called CC=1 SCAR=0.0
47  
48 #------------------------------------------------------------------------------
49 # cf A117804 - natural position of n in 012345678910111213
50 # A061168
51 #
52 1 my @oeis_anum;
53 1 $oeis_anum[2] = 'A083652'; # 2 binary
54 # OEIS-Catalogue: A083652 radix=2
55  
56 1 ▶sub oeis_anum {
Subroutine oeis_anum: called CC=1 SCAR=0.0
Pod documented
57 1 my ($self) = @_;
58 1 return $oeis_anum[$self->{'radix'}];
59 }
60  
61 #------------------------------------------------------------------------------
62  
63 3 ▶sub rewind {
Subroutine rewind: called CC=1 SCAR=0.0
Pod documented
64 3 my ($self) = @_;
65 ### DigitLengthCumulative rewind(): $self
66  
67 3 $self->{'i'} = $self->i_start;
68 3 $self->{'length'} = 1;
69 3 $self->{'limit'} = $self->{'radix'};
70 3 $self->{'total'} = 0;
71  
72 3 $self->{'logR'} = log($self->{'radix'});
73 }
74 0 ▶sub _UNTESTED__seek_to_i {
Subroutine _UNTESTED__seek_to_i: not called CC=1 SCAR=6.9
75 0 my ($self, $i) = @_;
76 0 $self->{'i'} = $i;
77 0 my $length = $self->{'length'} = $self->Math::NumSeq::DigitLength::ith($i);
78 0 $self->{'limit'} = $self->{'radix'} ** ($length+1);
79 0 $self->{'total'} = $self->ith($i);
80 }
81 118 ▶sub next {
Subroutine next: called CC=2 SCAR=6.9
Pod documented
82 118 my ($self) = @_;
83 ### DigitLengthCumulative next(): $self
84 ### count: $self->{'count'}
85 ### bits: $self->{'bits'}
86  
87 118 my $i = $self->{'i'}++;
88 118 ▶ if ($i >= $self->{'limit'}) {
Branch: 1 branch
BranchTrueFalseTotal
if ($i >= $self->{"limit"}) 10 108 118
89 10 $self->{'limit'} *= $self->{'radix'};
90 10 $self->{'length'}++;
91 ### step to
92 ### length: $self->{'length'}
93 ### remaining: $self->{'limit'}
94 }
95 118 return ($i, ($self->{'total'} += $self->{'length'}));
96 }
97  
98 # 0 to 9 is 10 of
99 475 ▶sub ith {
Subroutine ith: called CC=3 SCAR=11.0
Pod documented
100 475 my ($self, $i) = @_;
101 ### DigitLengthCumulative ith(): $i
102  
103 475 ▶ if (_is_infinite($i)) {
Branch: 1 branch
BranchTrueFalseTotal
if (_is_infinite($i)) 0 475 475
104 0 return $i; # don't loop forever if $i is +infinity
105 }
106 475 my $ret = 1;
107 475 my $length = 1;
108 475 my $radix = $self->{'radix'};
109 475 my $power = ($i*0)+1; # inherit bignum 1
110 475 for (;;) {
111 ### $ret
112 ### $length
113 ### $power
114 2329 my $next_power = $power * $radix;
115 2329 ▶ if ($i < $next_power) {
Branch: 1 branch
BranchTrueFalseTotal
if ($i < $next_power) 475 1854 2329
116 ### final extra: $length * ($i - $power + 1)
117 475 return $ret + $length * ($i - $power + 1);
118 }
119 ### add: $length * $next_power
120 1854 $ret += $length++ * ($next_power - $power);
121 1854 $power = $next_power;
122 }
123 }
124  
125 642 ▶sub pred {
Subroutine pred: called CC=6 SCAR=18.0
Pod documented
126 642 my ($self, $value) = @_;
127  
128 642 ▶ if (_is_infinite($value)) {
Branch: 1 branch
BranchTrueFalseTotal
if (_is_infinite($value)) 0 642 642
129 0 return undef;
130 }
131 {
132 642 my $int = int($value);
133 642 ▶ if ($value != $int) {
Branch: 1 branch
BranchTrueFalseTotal
if ($value != $int) 291 351 642
134 291 return 0;
135 }
136 351 $value = $int;
137 }
138 351 ▶ if ($value == 0) {
Branch: 1 branch
BranchTrueFalseTotal
if ($value == 0) 0 351 351
139 0 return 0;
140 }
141  
142 351 my $radix = $self->{'radix'};
143  
144 # length=1
145 # values 0,1,2,...,9
146 # cumulative 1,2,3,...,10
147 351 ▶ if ($value <= $radix) {
Branch: 1 branch
BranchTrueFalseTotal
if ($value <= $radix) 4 347 351
148 4 return 1;
149 }
150 347 $value -= $radix;
151  
152 # initial 10 to 99 = 90 values R*(R-1)
153 # later 1000 to 9999 = 9000 values R*R*R*(R-1)
154 # eg length=3
155 # values 1000 to 9999
156 # cumulative 3,6,...,
157 347 my $length = 2;
158 347 my $count = ($value*0) # inherit bignum $value
159 + $radix*($radix-1);
160  
161 347 for (;;) {
162 1487 my $limit = $count*$length;
163  
164 ### $length
165 ### $count
166 ### remainder: $value
167 ### $limit
168  
169 1487 ▶ if ($value <= $limit) {
Branch: 1 branch
BranchTrueFalseTotal
if ($value <= $limit) 347 1140 1487
170 347 return ($value % $length) == 0;
171 }
172 1140 $value -= $limit;
173 1140 $length++;
174 1140 $count *= $radix;
175 }
176 }
177  
178 295 ▶sub value_to_i {
Subroutine value_to_i: called CC=2 SCAR=6.9
Pod documented
179 295 my ($self, $value) = @_;
180 295 my $i = $self->value_to_i_floor($value);
181 295 ▶ if ($value == $self->ith($i)) {
Branch: 1 branch
BranchTrueFalseTotal
if ($value == $self->ith($i)) 118 177 295
182 118 return $i;
183 }
184 177 return undef;
185 }
186 648 ▶sub value_to_i_floor {
Subroutine value_to_i_floor: called CC=5 SCAR=16.1
Pod documented
187 648 my ($self, $value) = @_;
188  
189 648 ▶ if (_is_infinite($value)) {
Branch: 1 branch
BranchTrueFalseTotal
if (_is_infinite($value)) 0 648 648
190 0 return $value;
191 }
192 648 $value = int($value);
193  
194 648 ▶ if ($value < 1) {
Branch: 1 branch
BranchTrueFalseTotal
if ($value < 1) 11 637 648
195 11 return 0;
196 }
197  
198 # length=1
199 # values 0,1,2,...,9
200 # cumulative 1,2,3,...,10
201 #
202 637 my $radix = $self->{'radix'};
203 637 ▶ if ($value <= $radix) {
Branch: 1 branch
BranchTrueFalseTotal
if ($value <= $radix) 10 627 637
204 10 return $value-1;
205 }
206 627 $value -= $radix;
207  
208 # initial 10 to 99 = 90 values R*(R-1)
209 # later 1000 to 9999 = 9000 values R*R*R*(R-1)
210 # eg length=3
211 # values 1000 to 9999
212 # cumulative 3,6,...,
213 627 my $length = 2;
214 627 my $count = ($value*0) # inherit bignum $value
215 + $radix*($radix-1);
216 627 my $i = $radix-1;
217  
218 627 for (;;) {
219 2561 my $limit = $count*$length;
220  
221 ### $length
222 ### $count
223 ### remainder: $value
224 ### $limit
225  
226 2561 ▶ if ($value <= $limit) {
Branch: 1 branch
BranchTrueFalseTotal
if ($value <= $limit) 627 1934 2561
227 627 return $i + int($value/$length);
228 }
229 1934 $value -= $limit;
230 1934 $i += $count;
231 1934 $length++;
232 1934 $count *= $radix;
233 }
234 }
235  
236 # OR: estimate
237 # value = 1 + (R-1) + 2*R*(R-1) + 3*R*R*(R-1) + ... + k*R^(k-1)*(R-1)
238 # = 1+ (R-1) * [ 1 + R + R^2 + R^3 + ... + R^(k-1)
239 # + R + R^2 + R^3 + ... + R^(k-1)
240 # + R^2 + R^3 + ... + R^(k-1)
241 # ... + R^(k-1) ]
242 # = 1+ (R-1) * [ (R^k - 1) / (R-1)
243 # + R *(R^(k-1) - 1) / (R-1)
244 # + R^2 *(R^(k-2) - 1) / (R-1)
245 # ... + R^(k-1) *(R - 1) / (R-1) ]
246 # = 1+ [ (R^k - 1)
247 # + R *(R^(k-1) - 1)
248 # + R^2 *(R^(k-2) - 1)
249 # ... + R^(k-1) *(R - 1) ]
250 # ~= (R^k)
251 # + R *(R^(k-1))
252 # + R^2 *(R^(k-2))
253 # ... + R^(k-1) *(R)
254 # = k*R^k at i=R^k
255 #
256 # log(k*R^k) = log(k) + k*log(R)
257 # target t=log(value)
258 # f(x) = x*log(R) + log(x) - t
259 # f'(x) = log(R) + log(x)
260 # next_x = x - f(x)/f'(x)
261 # = x - (x*log(R) + log(x) - t)/(log(R) + log(x))
262 # = (x*(log(R) + log(x)) - (x*log(R) + log(x) - t))
263 # / (log(R) + log(x))
264 # = (x*log(R) + x*log(x) - x*log(R) - log(x) + t)
265 # / (log(R) + log(x))
266 # = (x*log(x) - log(x) + t) / (log(R) + log(x))
267 # = ((x-1)*log(x) + t) / (log(R) + log(x))
268 #
269 # For i=R^k value=k*R^k estimate k as kest=logR(value), which is only a bit
270 # bigger than it should be, and divide that out value/kest~=R^k=i
271  
272 68 ▶sub value_to_i_estimate {
Subroutine value_to_i_estimate: called CC=4 SCAR=13.9
Pod documented
273 68 my ($self, $value) = @_;
274  
275 68 ▶ if ($value <= 1) {
Branch: 1 branch
BranchTrueFalseTotal
if ($value <= 1) 9 59 68
276 9 return 0;
277 }
278  
279 59 my $t;
280 59 ▶ if (defined (my $blog2 = _blog2_estimate($value))) {
Branch: 1 branch
BranchTrueFalseTotal
if (defined(my $blog2 = _blog2_estimate($value))) { } 1 58 59
281 1 $t = $blog2 * log(2);
282 } else {
283 58 $t = log($value);
284 }
285  
286 # integer divisor to help Math::BigInt $value
287 59 my $div = int($t/$self->{'logR'});
288 59 ▶ if ($div > 1) {
Branch: 1 branch
BranchTrueFalseTotal
if ($div > 1) 58 1 59
289 58 $value /= $div;
290 }
291 59 return int($value);
292 }
293  
294 1 1;
295 __END__
« NumSeq/DigitSumModulo.pm ↑ Summary NumSeq/UlamSequence.pm »