File Coverage

blib/lib/Math/NumSeq/DigitLengthCumulative.pm
Criterion Covered Total %
statement 118 127 92.9
branch 28 32 87.5
condition n/a
subroutine 20 21 95.2
pod 8 8 100.0
total 174 188 92.5


line stmt bran cond sub pod time code
1             # Copyright 2010, 2011, 2012, 2013, 2014 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 .
17              
18             package Math::NumSeq::DigitLengthCumulative;
19 1     1   1063 use 5.004;
  1         2  
20 1     1   4 use strict;
  1         1  
  1         21  
21              
22 1     1   4 use vars '$VERSION', '@ISA';
  1         1  
  1         53  
23             $VERSION = 72;
24 1     1   4 use Math::NumSeq;
  1         1  
  1         29  
25             @ISA = ('Math::NumSeq');
26             *_is_infinite = \&Math::NumSeq::_is_infinite;
27              
28 1     1   3 use Math::NumSeq::Fibonacci;
  1         2  
  1         25  
29             *_blog2_estimate = \&Math::NumSeq::Fibonacci::_blog2_estimate;
30              
31             use Math::NumSeq::Base::Digits
32 1     1   3 'parameter_info_array'; # radix parameter
  1         1  
  1         44  
33              
34             # uncomment this to run the ### lines
35             #use Smart::Comments;
36              
37              
38 1     1   4 use vars '$VERSION';
  1         1  
  1         46  
39             $VERSION = 72;
40              
41             # use constant name => Math::NumSeq::__('Digit Length Cumulative');
42 1     1   4 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.');
  1         2  
  1         6  
43 1     1   7 use constant i_start => 0;
  1         3  
  1         71  
44 1     1   5 use constant values_min => 1;
  1         1  
  1         37  
45 1     1   4 use constant characteristic_increasing => 1;
  1         2  
  1         31  
46 1     1   4 use constant characteristic_integer => 1;
  1         1  
  1         616  
47              
48             #------------------------------------------------------------------------------
49             # cf A117804 - natural position of n in 012345678910111213
50             # A061168
51             #
52             my @oeis_anum;
53             $oeis_anum[2] = 'A083652'; # 2 binary
54             # OEIS-Catalogue: A083652 radix=2
55              
56             sub oeis_anum {
57 1     1 1 4 my ($self) = @_;
58 1         2 return $oeis_anum[$self->{'radix'}];
59             }
60              
61             #------------------------------------------------------------------------------
62              
63             sub rewind {
64 3     3 1 710 my ($self) = @_;
65             ### DigitLengthCumulative rewind(): $self
66              
67 3         17 $self->{'i'} = $self->i_start;
68 3         3 $self->{'length'} = 1;
69 3         5 $self->{'limit'} = $self->{'radix'};
70 3         2 $self->{'total'} = 0;
71              
72 3         14 $self->{'logR'} = log($self->{'radix'});
73             }
74             sub _UNTESTED__seek_to_i {
75 0     0   0 my ($self, $i) = @_;
76 0         0 $self->{'i'} = $i;
77 0         0 my $length = $self->{'length'} = $self->Math::NumSeq::DigitLength::ith($i);
78 0         0 $self->{'limit'} = $self->{'radix'} ** ($length+1);
79 0         0 $self->{'total'} = $self->ith($i);
80             }
81             sub next {
82 118     118 1 550 my ($self) = @_;
83             ### DigitLengthCumulative next(): $self
84             ### count: $self->{'count'}
85             ### bits: $self->{'bits'}
86              
87 118         78 my $i = $self->{'i'}++;
88 118 100       142 if ($i >= $self->{'limit'}) {
89 10         8 $self->{'limit'} *= $self->{'radix'};
90 10         7 $self->{'length'}++;
91             ### step to
92             ### length: $self->{'length'}
93             ### remaining: $self->{'limit'}
94             }
95 118         110 return ($i, ($self->{'total'} += $self->{'length'}));
96             }
97              
98             # 0 to 9 is 10 of
99             sub ith {
100 475     475 1 470 my ($self, $i) = @_;
101             ### DigitLengthCumulative ith(): $i
102              
103 475 50       685 if (_is_infinite($i)) {
104 0         0 return $i; # don't loop forever if $i is +infinity
105             }
106 475         12873 my $ret = 1;
107 475         324 my $length = 1;
108 475         435 my $radix = $self->{'radix'};
109 475         457 my $power = ($i*0)+1; # inherit bignum 1
110 475         12250 for (;;) {
111             ### $ret
112             ### $length
113             ### $power
114 2329         1828 my $next_power = $power * $radix;
115 2329 100       25527 if ($i < $next_power) {
116             ### final extra: $length * ($i - $power + 1)
117 475         1929 return $ret + $length * ($i - $power + 1);
118             }
119             ### add: $length * $next_power
120 1854         5355 $ret += $length++ * ($next_power - $power);
121 1854         44839 $power = $next_power;
122             }
123             }
124              
125             sub pred {
126 642     642 1 1622 my ($self, $value) = @_;
127              
128 642 50       774 if (_is_infinite($value)) {
129 0         0 return undef;
130             }
131             {
132 642         425 my $int = int($value);
  642         441  
133 642 100       748 if ($value != $int) {
134 291         293 return 0;
135             }
136 351         232 $value = $int;
137             }
138 351 50       388 if ($value == 0) {
139 0         0 return 0;
140             }
141              
142 351         283 my $radix = $self->{'radix'};
143              
144             # length=1
145             # values 0,1,2,...,9
146             # cumulative 1,2,3,...,10
147 351 100       391 if ($value <= $radix) {
148 4         6 return 1;
149             }
150 347         226 $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         205 my $length = 2;
158 347         254 my $count = ($value*0) # inherit bignum $value
159             + $radix*($radix-1);
160              
161 347         211 for (;;) {
162 1487         858 my $limit = $count*$length;
163              
164             ### $length
165             ### $count
166             ### remainder: $value
167             ### $limit
168              
169 1487 100       1483 if ($value <= $limit) {
170 347         444 return ($value % $length) == 0;
171             }
172 1140         635 $value -= $limit;
173 1140         630 $length++;
174 1140         696 $count *= $radix;
175             }
176             }
177              
178             sub value_to_i {
179 295     295 1 785 my ($self, $value) = @_;
180 295         366 my $i = $self->value_to_i_floor($value);
181 295 100       8921 if ($value == $self->ith($i)) {
182 118         17361 return $i;
183             }
184 177         231 return undef;
185             }
186             sub value_to_i_floor {
187 648     648 1 1241 my ($self, $value) = @_;
188              
189 648 50       945 if (_is_infinite($value)) {
190 0         0 return $value;
191             }
192 648         25943 $value = int($value);
193              
194 648 100       1992 if ($value < 1) {
195 11         12 return 0;
196             }
197              
198             # length=1
199             # values 0,1,2,...,9
200             # cumulative 1,2,3,...,10
201             #
202 637         7111 my $radix = $self->{'radix'};
203 637 100       918 if ($value <= $radix) {
204 10         313 return $value-1;
205             }
206 627         6669 $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         11618 my $length = 2;
214 627         671 my $count = ($value*0) # inherit bignum $value
215             + $radix*($radix-1);
216 627         22873 my $i = $radix-1;
217              
218 627         443 for (;;) {
219 2561         26993 my $limit = $count*$length;
220              
221             ### $length
222             ### $count
223             ### remainder: $value
224             ### $limit
225              
226 2561 100       38520 if ($value <= $limit) {
227 627         2962 return $i + int($value/$length);
228             }
229 1934         7108 $value -= $limit;
230 1934         20504 $i += $count;
231 1934         17779 $length++;
232 1934         1536 $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             sub value_to_i_estimate {
273 68     68 1 338 my ($self, $value) = @_;
274              
275 68 100       83 if ($value <= 1) {
276 9         11 return 0;
277             }
278              
279 59         89 my $t;
280 59 100       73 if (defined (my $blog2 = _blog2_estimate($value))) {
281 1         214 $t = $blog2 * log(2);
282             } else {
283 58         50 $t = log($value);
284             }
285              
286             # integer divisor to help Math::BigInt $value
287 59         55 my $div = int($t/$self->{'logR'});
288 59 100       63 if ($div > 1) {
289 58         42 $value /= $div;
290             }
291 59         143 return int($value);
292             }
293              
294             1;
295             __END__