File Coverage

blib/lib/Math/NumSeq/ReRound.pm
Criterion Covered Total %
statement 70 74 94.5
branch 12 16 75.0
condition 3 3 100.0
subroutine 18 18 100.0
pod 4 4 100.0
total 107 115 93.0


line stmt bran cond sub pod time code
1             # Copyright 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::ReRound;
19 2     2   6880 use 5.004;
  2         6  
20 2     2   7 use strict;
  2         2  
  2         37  
21 2     2   380 use POSIX 'ceil';
  2         4638  
  2         12  
22 2     2   824 use List::Util 'max';
  2         3  
  2         114  
23              
24 2     2   7 use vars '$VERSION','@ISA';
  2         2  
  2         88  
25             $VERSION = 72;
26              
27 2     2   359 use Math::NumSeq;
  2         2  
  2         32  
28 2     2   346 use Math::NumSeq::Base::IterateIth;
  2         3  
  2         83  
29             @ISA = ('Math::NumSeq::Base::IterateIth',
30             'Math::NumSeq');
31             *_is_infinite = \&Math::NumSeq::_is_infinite;
32              
33             # uncomment this to run the ### lines
34             #use Smart::Comments;
35              
36             # use constant name => Math::NumSeq::__('Repeated Rounding');
37 2     2   7 use constant description => Math::NumSeq::__('Repeated rounding up to multiple of N, N-1, ..., 1.');
  2         1  
  2         6  
38 2     2   7 use constant values_min => 1; # at i=1
  2         2  
  2         64  
39 2     2   6 use constant i_start => 1;
  2         2  
  2         69  
40 2     2   6 use constant characteristic_increasing => 1;
  2         2  
  2         67  
41 2     2   6 use constant characteristic_integer => 1;
  2         2  
  2         114  
42              
43 2         5 use constant parameter_info_array =>
44             [
45             { name => 'extra_multiples',
46             display => Math::NumSeq::__('Extra Multiples'),
47             type => 'integer',
48             default => '0',
49             minimum => 0,
50             width => 2,
51             description => Math::NumSeq::__('Extra multiples to round up at each stage.'),
52             },
53 2     2   6 ];
  2         3  
54              
55             #------------------------------------------------------------------------------
56             # cf A007952 sieve+1
57             # A099361 sieve by primes
58             # A099204 sieve by primes
59             # A099207 sieve by primes
60             # A099243 sieve by primes
61             # A002960 square sieve
62             #
63             # A056533 sieve out even every 2nd,4th,6th,etc
64             # A039672 sieve fibonacci style i+j prev terms
65             # A056530 Flavius Josephus after 2nd round
66             # A056531 Flavius Josephus after 4th round
67             # A119446 cf A100461
68             #
69             # A113749 k multiples
70             #
71             my @oeis_anum
72             = (
73             # OEIS-Catalogue array begin
74             'A002491', # # Mancala stones
75             'A000960', # extra_multiples=1 # Flavius Josephus
76             'A112557', # extra_multiples=2 # more Mancala stones ...
77             'A112558', # extra_multiples=3 # more Mancala stones ...
78             'A113742', # extra_multiples=4 # more Mancala stones ...
79             'A113743', # extra_multiples=5 # more Mancala stones ...
80             'A113744', # extra_multiples=6 # more Mancala stones ...
81             'A113745', # extra_multiples=7 # more Mancala stones ...
82             'A113746', # extra_multiples=8 # more Mancala stones ...
83             'A113747', # extra_multiples=9 # more Mancala stones ...
84             'A113748', # extra_multiples=10 # more Mancala stones ...
85             # OEIS-Catalogue array end
86             );
87             sub oeis_anum {
88 1     1 1 3 my ($self) = @_;
89 1         2 return $oeis_anum[$self->{'extra_multiples'}];
90             }
91              
92             #------------------------------------------------------------------------------
93              
94              
95             sub ith {
96 180     180 1 18931 my ($self, $i) = @_;
97             ### ReRound ith(): $i
98              
99 180 50       277 if (_is_infinite($i)) {
100 0         0 return $i; # don't loop forever if $i is +infinity
101             }
102              
103 180         174 my $extra_multiples = $self->{'extra_multiples'};
104             ### $extra_multiples
105              
106 180         294 for (my $m = $i-1; $m >= 1; $m--) {
107             ### add: (-$i % $m) + $extra_multiples*$m
108              
109 5489         6618 $i += (-$i % $m) + $extra_multiples*$m;
110             }
111 180         239 return $i;
112             }
113              
114             # 1,3,7,13,19
115             # 2->2+1=3
116             # 3->4+2=6->6+1=7
117             # 4->6+m3=9->10+m2=12->12+m1=13
118             #
119             # next = prev + (-prev mod m) + k*m
120             # next-k*m = prev + (-prev mod m)
121              
122             sub pred {
123 29     29 1 94 my ($self, $value) = @_;
124             ### ReRound pred(): $value
125              
126 29         25 my $extra_multiples = $self->{'extra_multiples'};
127              
128 29 50       37 if (_is_infinite($value)) {
129 0         0 return undef;
130             }
131 29 100 100     77 if ($value <= 1 || $value != int($value)) {
132 13         16 return ($value == 1);
133             }
134              
135             # special case m=1 stepping down to an even number
136 16 100       22 if (($value -= $extra_multiples) % 2) {
137 5         6 return 0;
138             }
139              
140 11         9 my $m = 2;
141 11         14 while ($value > $m) {
142             ### at: "value=$value m=$m"
143              
144 21 50       25 if (($value -= $extra_multiples*$m) <= 0) {
145             ### no, negative: $value
146 0         0 return 0;
147             }
148             ### subtract to: "value=$value"
149              
150             ### rem: "modulus=".($m+1)." rem ".($value%($m+1))
151 21         14 my $rem;
152 21 100       28 if (($rem = ($value % ($m+1))) == $m) {
153             ### no, remainder: "rem=$rem modulus=".($m+1)
154 1         2 return 0;
155             }
156              
157 20         14 $value -= $rem;
158 20         23 $m++;
159             }
160              
161             ### final ...
162             ### $value
163             ### $m
164              
165 10         14 return ($value == $m);
166             }
167              
168             # # v1.02 for leading underscore
169 2     2   7 use constant 1.02 _PI => 4*atan2(1,1); # similar to Math::Complex pi()
  2         25  
  2         230  
170              
171             # value = m*1+m*2+m*3+...+m*i
172             # value = m*i*(i+1)/2
173             # i*i + i - 2v/m = 0
174             # i = (-1 + sqrt(1 + 4*2v/m)) / 2
175             # = -1/2 + sqrt(1 + 4*2v/m)/2
176             # = -1/2 + sqrt(4 + 2v/m)
177             # i -> sqrt(2v/m)
178             #
179             # as extra_multiples dominates the estimate changes from
180             # extra_multiples==0 est = sqrt(pi*value)
181             # up to
182             # extra_multiples==m large est = sqrt(2*value/m)
183             #
184             # What formula that progressively morphs pi to 2/m ?
185             #
186             sub value_to_i_estimate {
187 15     15 1 521 my ($self, $value) = @_;
188 15 100       19 if ($value < 0) { return 0; }
  6         7  
189              
190 9 50       117 if ($self->{'extra_multiples'} == 0) {
191             # use sqrt(pi)~=296/167 to preserve Math::BigInt
192 9         15 return int( (sqrt(int($value)) * 296) / 167);
193             } else {
194 0           return int(sqrt(int (2 * $value / $self->{'extra_multiples'})));
195              
196             # return int(sqrt(int ($value * _PI/($self->{'extra_multiples'}+1)**2))
197             # + ($self->{'extra_multiples'} > 0
198             # ? -0.5 + sqrt(4 + 2*$value/$self->{'extra_multiples'})
199             # : 0));
200             }
201              
202              
203              
204             # # large extra_multiples
205             # return int(sqrt(int (2 * $value
206             # / ($self->{'extra_multiples'}+1))));
207             #
208             # return int(sqrt(int (($value * 355)
209             # / (113 * ($self->{'extra_multiples'}+1)))));
210             #
211             #
212             # # extra_multiples==14
213             # return int(sqrt(int (_PI * $value)) * 429/2048); # 429=13*11*3
214             #
215             # # extra_multiples==12
216             # return int(sqrt(int (_PI * $value)) * 462/2048); # 231/1024) # 11*7*3=231
217             #
218             # # extra_multiples==10
219             # return int(sqrt(int (_PI * $value))) * 126/512; # 63/256; # 7*3*2=126
220             #
221             # # extra_multiples==8
222             # return int(sqrt(int (_PI * $value))) * 35/128; # 7*5=35
223             #
224             # # extra_multiples==6
225             # return int(sqrt(int (_PI * $value))) * 10/32; # 5/16 # 5*2=10
226             #
227             # # extra_multiples==4
228             # return int(sqrt(int (_PI * $value))) * 3/8;
229             #
230             # # extra_multiples==2
231             # return int(sqrt(int (_PI * $value))) * 1/2;
232             #
233             # # extra_multiples==0
234             # return int(sqrt(int (_PI * $value))) * 1/1;
235             #
236             # 2 1
237             # 4 11
238             # 6 1010
239             # 8 100011
240             # 10 1111110
241             # 12 111001110
242             # 14 110101101
243              
244             #
245             #
246             # # extra_multiples==11
247             # return int(sqrt(int (1/_PI * $value)) * 1024/1386); # 512/693);
248             #
249             # # extra_multiples==9
250             # return int(sqrt(int (1/_PI * $value)) * 256/315);
251             #
252             # # extra_multiples==7
253             # return int(sqrt(int (1/_PI * $value)) * 64/70); # 32/35;
254             #
255             # # extra_multiples==5
256             # return int(sqrt(int (1/_PI * $value))) * 16/15;
257             #
258             # # extra_multiples==3
259             # return int(sqrt(int (1/_PI * $value))) * 4/3;
260             #
261             # # extra_multiples==1
262             # return int(sqrt(int (1/_PI * $value ))) * 2/1;
263              
264             }
265              
266             1;
267             __END__