NumSeq/ReverseAdd.pm

filter: Statementstmt 61.3% 103 / 168 Branchbran 22.0% 11 / 50 Conditioncond 21.4% 6 / 28 MC/DCmcdc 0.0% 0 / 17 Subroutinesub 54.1% 13 / 24 Podpod 90.0% 9 / 10 totaltotal 47.8% 142 / 297 CC 24 SCAR 29.2
CC
24
Cov
49%
pred
72.0
ith
20.0
_reverse_in_radix
14.8
CRAP 18.6
« NumSeq/PisanoPeriod.pm ↑ Summary NumSeq/Fibonacci.pm »
1 # Copyright 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::ReverseAdd;
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 # uncomment this to run the ### lines
29 #use Smart::Comments;
30  
31  
32 1 ▶use constant i_start => 0;
Subroutine BEGIN: called CC=1 SCAR=0.0
33  
34 1 ▶use constant characteristic_integer => 1;
Subroutine BEGIN: called CC=1 SCAR=0.0
35 1 ▶sub characteristic_increasing {
Subroutine characteristic_increasing: called CC=1 SCAR=0.0
Pod undocumented
36 1 my ($self) = @_;
37 # any non-zero start always increases
38 1 return ($self->{'start'} != 0);
39 }
40 0 ▶sub values_min {
Subroutine values_min: not called CC=1 SCAR=6.9
Pod documented
41 0 my ($self) = @_;
42 0 return $self->{'start'};
43 }
44 0 ▶sub values_max {
Subroutine values_max: not called CC=2 SCAR=17.9
Pod documented
45 0 my ($self) = @_;
46 # starting from zero never changes, otherwise unbounded
47 0 ▶ return ($self->{'start'} ? undef : 0);
Branch: 1 branch
BranchTrueFalseTotal
$self->{'start'} ? : 0 0 0
48 }
49  
50 1 ▶use Math::NumSeq::Base::Digits;
Subroutine BEGIN: called CC=1 SCAR=0.0
51 1 ▶use constant parameter_info_array =>
Subroutine BEGIN: called CC=1 SCAR=0.0
52 [
53 {
54 name => 'start',
55 display => Math::NumSeq::__('Start'),
56 type => 'integer',
57 default => 1,
58 minimum => 0,
59 width => 5,
60 description => Math::NumSeq::__('Starting value for the sequence.'),
61 },
62 Math::NumSeq::Base::Digits->parameter_info_list(),
63 1 ];
64  
65 0 ▶sub description {
Subroutine description: not called CC=2 SCAR=17.9
Pod documented
66 0 my ($self) = @_;
67 0 my $ret = Math::NumSeq::__('Reverse-add sequence, reverse the digits and add.');
68 0 ▶ if (ref $self) { # object method
Branch: 1 branch
BranchTrueFalseTotal
if (ref $self) 0 0 0
69 0 $ret .= "\nStarting from $self->{'start'}, in radix $self->{'radix'}.";
70 }
71 0 return $ret;
72 }
73  
74 #------------------------------------------------------------------------------
75 1 my %oeis_anum;
76  
77 # cf A058042 written out in binary
78 # ~/OEIS/a058042.txt on reaching binary palindromes
79 # A033908 sort-add
80  
81 1 $oeis_anum{'2'}->{'1'} = 'A035522';
82 1 $oeis_anum{'2'}->{'22'} = 'A061561';
83 1 $oeis_anum{'2'}->{'77'} = 'A075253';
84 1 $oeis_anum{'2'}->{'442'} = 'A075268';
85 1 $oeis_anum{'2'}->{'537'} = 'A077076';
86 1 $oeis_anum{'2'}->{'775'} = 'A077077';
87 # OEIS-Catalogue: A035522 radix=2 start=1
88 # OEIS-Catalogue: A061561 radix=2 start=22
89 # OEIS-Catalogue: A075253 radix=2 start=77
90 # OEIS-Catalogue: A075268 radix=2 start=442
91 # OEIS-Catalogue: A077076 radix=2 start=537
92 # OEIS-Catalogue: A077077 radix=2 start=775
93  
94 1 $oeis_anum{'3'}->{'1'} = 'A035523';
95 # OEIS-Catalogue: A035523 radix=3 start=1
96  
97 1 $oeis_anum{'4'}->{'1'} = 'A035524';
98 1 $oeis_anum{'4'}->{'290'} = 'A075299';
99 1 $oeis_anum{'4'}->{'318'} = 'A075153';
100 1 $oeis_anum{'4'}->{'266718'} = 'A075466';
101 1 $oeis_anum{'4'}->{'270798'} = 'A075467';
102 1 $oeis_anum{'4'}->{'1059774'} = 'A076247';
103 1 $oeis_anum{'4'}->{'1059831'} = 'A076248';
104 # OEIS-Catalogue: A035524 radix=4 start=1
105 # OEIS-Catalogue: A075299 radix=4 start=290
106 # OEIS-Catalogue: A075153 radix=4 start=318
107 # OEIS-Catalogue: A075466 radix=4 start=266718
108 # OEIS-Catalogue: A075467 radix=4 start=270798
109 # OEIS-Catalogue: A076247 radix=4 start=1059774
110 # OEIS-Catalogue: A076248 radix=4 start=1059831
111  
112 1 $oeis_anum{'10'}->{'1'} = 'A001127';
113 1 $oeis_anum{'10'}->{'3'} = 'A033648';
114 1 $oeis_anum{'10'}->{'5'} = 'A033649';
115 1 $oeis_anum{'10'}->{'7'} = 'A033650';
116 1 $oeis_anum{'10'}->{'9'} = 'A033651';
117 1 $oeis_anum{'10'}->{'89'} = 'A033670';
118 1 $oeis_anum{'10'}->{'196'} = 'A006960';
119 # OEIS-Catalogue: A001127 start=1
120 # OEIS-Catalogue: A033648 start=3
121 # OEIS-Catalogue: A033649 start=5
122 # OEIS-Catalogue: A033650 start=7
123 # OEIS-Catalogue: A033651 start=9
124 # OEIS-Catalogue: A033670 start=89
125 # OEIS-Catalogue: A006960 start=196
126  
127 0 ▶sub oeis_anum {
Subroutine oeis_anum: not called CC=2 SCAR=17.9
Pod documented
128 0 my ($self) = @_;
129 0 my $start = $self->{'start'};
130  
131 0 ▶ if ($start == 0) { return 'A000004'; } # all zeros
Branch: 1 branch
BranchTrueFalseTotal
if ($start == 0) 0 0 0
132 # some sample zeros to exercise
133 # OEIS-Other: A000004 radix=2 start=0
134 # OEIS-Other: A000004 radix=9 start=0
135  
136 0 return $oeis_anum{$self->{'radix'}}->{$start};
137 }
138  
139 #------------------------------------------------------------------------------
140  
141 1 my $max = do {
142 1 my $m = 1;
143 1 foreach (1 .. 256) {
144 53 my $double = 2*$m;
145 53 my $next = 2*$m + 1;
146 53 ▶ if ($next <= 2*$m || $next >= 2*$m+2) {
Branch: 1 branch
BranchTrueFalseTotal
if ($next <= 2 * $m or $next >= 2 * $m + 2) 0 53 53
Condition33%1/3
$next <= 2 * $m or $next >= 2 * $m + 2
l!l&&r!l&&!r
0053
MC/DC0%0/2
$next <= 2 * $m or $next >= 2 * $m + 2
$next <= 2 * $m $next >= 2 * $m + 2
Truth table33%1/3
A or B
A= $next <= 2 * $mB= $next >= 2 * $m + 2
ABresult
1X1
011
000
147 0 last;
148 }
149 # must be able to divide for _reverse_in_radix()
150 53 ▶ if (int($next/2) != $m) {
Branch: 1 branch
BranchTrueFalseTotal
if (int $next / 2 != $m) 1 52 53
151 1 last;
152 }
153 52 $m = $next;
154 }
155 1 $m = int($m/2);
156 ### $m
157 ### m hex: sprintf '%X', $m
158 1 $m
159 };
160  
161 1 ▶sub rewind {
Subroutine rewind: called CC=1 SCAR=0.0
Pod documented
162 1 my ($self) = @_;
163 1 $self->{'i'} = $self->i_start;
164 1 $self->{'value'} = $self->{'start'};
165 1 $self->{'uv_limit'} = int ($max / $self->{'radix'});
166 }
167 0 ▶sub next {
Subroutine next: not called CC=3 SCAR=24.8
Pod documented
168 0 my ($self) = @_;
169 ### ReverseAdd next(): "i=$self->{'i'} ".(ref $self->{'value'})." $self->{'value'}"
170 ### reverse: _reverse_in_radix($self->{'value'}, $self->{'radix'})
171  
172 0 my $ret = $self->{'value'};
173 0 ▶ if (! ref $ret && $ret >= $self->{'uv_limit'}) {
Branch: 1 branch
BranchTrueFalseTotal
if (not ref $ret and $ret >= $self->{"uv_limit"}) 0 0 0
Condition0%0/3
not ref $ret and $ret >= $self->{"uv_limit"}
!ll&&!rl&&r
000
MC/DC0%0/2
not ref $ret and $ret >= $self->{"uv_limit"}
not ref $ret $ret >= $self->{"uv_limit"}
Truth table0%0/3
not(A) and B
A= not ref $retB= $ret >= $self->{"uv_limit"}
ABresult
0X0
100
111
174 ### go to bigint ...
175 0 $self->{'value'} = Math::NumSeq::_to_bigint($ret);
176 }
177 0 $self->{'value'} += _reverse_in_radix($ret, $self->{'radix'});
178 0 return ($self->{'i'}++,
179 $ret);
180 }
181  
182 0 ▶sub ith {
Subroutine ith: not called CC=4 SCAR=30.0
Pod documented
183 0 my ($self, $i) = @_;
184 ### ReverseAdd ith(): $i
185  
186 0 ▶ if (_is_infinite($i)) {
Branch: 1 branch
BranchTrueFalseTotal
if (_is_infinite($i)) 0 0 0
187 0 return undef;
188 }
189  
190 0 my $radix = $self->{'radix'};
191 0 ▶ my $start = $self->{'start'} || return 0; # start 0 gives 0
Condition0%0/2
$self->{'start'} || (return 0)
l!l
00
MC/DC0%0/1
$self->{'start'} || (return 0)
$self->{'start'}
Truth table0%0/2
A
A= $self->{'start'}
Aresult
11
00
192 0 my $value = ($i*0) + $start; # inherit bignum from $i
193  
194 0 ▶ while ($i-- > 0) {
Branch: 1 branch
BranchTrueFalseTotal
if ($i-- > 0) 0 0 0
195 0 $value += _reverse_in_radix($value, $radix);
196 }
197 0 return $value;
198 }
199 # if ($value >= $self->{'uv_limit'}) {
200 # ### go to bigint ...
201 # $value = Math::NumSeq::_to_bigint($value);
202 # while ($i-- > 0) {
203 # $value += _reverse_in_radix($value, $radix);
204 # }
205 # last;
206 # }
207  
208 0 ▶sub pred {
Subroutine pred: not called CC=8 SCAR=42.8
Pod documented
209 0 my ($self, $value) = @_;
210 ### ReverseAdd pred(): $value
211  
212 0 ▶ my $start = $self->{'start'} || return ($value == 0); # start 0 gives 0
Condition0%0/2
$self->{'start'} || (return $value == 0)
l!l
00
MC/DC0%0/1
$self->{'start'} || (return $value == 0)
$self->{'start'}
Truth table0%0/2
A
A= $self->{'start'}
Aresult
11
00
213 0 ▶ if ($value < $start || _is_infinite($value)) {
Branch: 1 branch
BranchTrueFalseTotal
if ($value < $start or _is_infinite($value)) 0 0 0
Condition0%0/3
$value < $start or _is_infinite($value)
l!l&&r!l&&!r
000
MC/DC0%0/2
$value < $start or _is_infinite($value)
$value < $start _is_infinite($value)
Truth table0%0/3
A or B
A= $value < $startB= _is_infinite($value)
ABresult
1X1
011
000
214 0 return 0;
215 }
216  
217 {
218 0 my $int = int($value);
219 0 ▶ if ($value != $int) {
Branch: 1 branch
BranchTrueFalseTotal
if ($value != $int) 0 0 0
220 0 return 0;
221 }
222 0 $value = $int;
223 }
224  
225 0 my $radix = $self->{'radix'};
226 0 my $k = ($value*0) + $start;
227 0 ▶ while ($k < $self->{'uv_limit'}) {
Branch: 1 branch
BranchTrueFalseTotal
if ($k < $self->{"uv_limit"}) 0 0 0
228 0 ▶ unless ($value > $k) {
Branch: 1 branch
BranchTrueFalseTotal
unless ($value > $k) 0 0 0
229 0 return ($value == $k);
230 }
231 0 $k += _reverse_in_radix($k, $radix);
232 }
233  
234 ### go to bigint ...
235 0 for (;;) {
236 0 ▶ unless ($value > $k) {
Branch: 1 branch
BranchTrueFalseTotal
unless ($value > $k) 0 0 0
237 0 return ($value == $k);
238 }
239 0 $k += _reverse_in_radix($k, $radix);
240 }
241 }
242  
243 # if ($value >= $self->{'uv_limit'}) {
244 # ### go to bigint ...
245 # $value = Math::NumSeq::_to_bigint($value);
246 # while ($i-- > 0) {
247 # $value += _reverse_in_radix($value, $radix);
248 # }
249 # last;
250 # }
251  
252 # FIXME: smaller than this
253 0 ▶sub value_to_i_estimate {
Subroutine value_to_i_estimate: not called CC=3 SCAR=24.8
Pod documented
254 0 my ($self, $value) = @_;
255 0 ▶ if (_is_infinite($value)) {
Branch: 1 branch
BranchTrueFalseTotal
if (_is_infinite($value)) 0 0 0
256 0 return $value;
257 }
258 0 my $i = 1;
259 0 for (;; $i++) {
260 0 $value = int($value/2);
261 0 ▶ if ($value <= 1) {
Branch: 1 branch
BranchTrueFalseTotal
if ($value <= 1) 0 0 0
262 0 return $i;
263 }
264 }
265 }
266  
267 1 my %binary_to_base4 = (# '0b' => '',
268 '00' => '0',
269 '01' => '1',
270 '10' => '2',
271 '11' => '3');
272 1 ▶sub _bigint_as_base4 {
Subroutine _bigint_as_base4: called CC=2 SCAR=7.0
273 1 my ($big) = @_;
274 1 my $str = $big->as_bin;
275 1 $str =~ s/^0b//;
276 1 ▶ if (length($str) & 1) {
Branch: 1 branch
BranchTrueFalseTotal
if (length $str & 1) 1 0 1
277 1 $str = "0$str";
278 }
279 1 $str =~ s/(..)/$binary_to_base4{$1}/ge;
280 1 return $str;
281 }
282 1 my @base4_to_binary = ('00','01','10','11');
283 1 ▶sub _bigint_from_base4 {
Subroutine _bigint_from_base4: called CC=1 SCAR=0.0
284 1 my ($class, $str) = @_;
285 ### _bigint_from_base4(): $str
286 1 $str =~ s/(.)/$base4_to_binary[$1]/ge;
287 1 return $class->from_bin("0b$str");
288 }
289  
290 0 ▶sub _bigint_from_bin_with_0b {
Subroutine _bigint_from_bin_with_0b: not called CC=1 SCAR=0.0
291 }
292  
293 1 my @radix_to_stringize_method;
294 my @string_to_bigint_method;
295 1 my $bigint = Math::NumSeq::_bigint();
296 {
297 1 ▶ if ($bigint->can('as_bin') && $bigint->can('from_bin')) {
Branch: 1 branch
BranchTrueFalseTotal
if ($bigint->can("as_bin") and $bigint->can("from_bin")) 1 0 1
Condition33%1/3
$bigint->can("as_bin") and $bigint->can("from_bin")
!ll&&!rl&&r
001
MC/DC0%0/2
$bigint->can("as_bin") and $bigint->can("from_bin")
$bigint->can("as_bin") $bigint->can("from_bin")
Truth table33%1/3
A and B
A= $bigint->can("as_bin")B= $bigint->can("from_bin")
ABresult
0X0
100
111
298 1 $radix_to_stringize_method[2] = 'as_bin';
299 # in past BigInt must have 0b prefix for from_bin()
300 $string_to_bigint_method[2]
301 = ($bigint->from_bin('0') == 0
302 ? 'from_bin'
303 0 ▶ : sub {
Subroutine __ANON__: not called CC=1 SCAR=6.9
304 ### from_bin with 0b: "0b$_[1]"
305 0 $_[0]->from_bin("0b$_[1]");
306 1 ▶ });
Branch: 1 branch
BranchTrueFalseTotal
$bigint->from_bin('0') == 0 ? : 1 0 1
307  
308 1 $radix_to_stringize_method[4] = \&_bigint_as_base4;
309 1 $string_to_bigint_method[4] = \&_bigint_from_base4;
310 }
311 1 ▶ if ($bigint->can('as_oct') && $bigint->can('from_oct')) {
Branch: 1 branch
BranchTrueFalseTotal
if ($bigint->can("as_oct") and $bigint->can("from_oct")) 1 0 1
Condition33%1/3
$bigint->can("as_oct") and $bigint->can("from_oct")
!ll&&!rl&&r
001
MC/DC0%0/2
$bigint->can("as_oct") and $bigint->can("from_oct")
$bigint->can("as_oct") $bigint->can("from_oct")
Truth table33%1/3
A and B
A= $bigint->can("as_oct")B= $bigint->can("from_oct")
ABresult
0X0
100
111
312 1 $radix_to_stringize_method[8] = 'as_oct';
313 1 $string_to_bigint_method[8] = 'from_oct';
314 }
315 1 ▶ if ($bigint->can('as_hex') && $bigint->can('from_hex')) {
Branch: 1 branch
BranchTrueFalseTotal
if ($bigint->can("as_hex") and $bigint->can("from_hex")) 1 0 1
Condition33%1/3
$bigint->can("as_hex") and $bigint->can("from_hex")
!ll&&!rl&&r
001
MC/DC0%0/2
$bigint->can("as_hex") and $bigint->can("from_hex")
$bigint->can("as_hex") $bigint->can("from_hex")
Truth table33%1/3
A and B
A= $bigint->can("as_hex")B= $bigint->can("from_hex")
ABresult
0X0
100
111
316 1 $radix_to_stringize_method[16] = 'as_hex';
317 # in past BigInt must have 0x prefix for from_hex()
318 $string_to_bigint_method[16]
319 = ($bigint->from_hex('0') == 0
320 ? 'from_hex'
321 0 ▶ : sub {
Subroutine __ANON__: not called CC=1 SCAR=6.9
322 ### from_hex with 0x: "0x$_[1]"
323 0 $_[0]->from_hex("0x$_[1]");
324 1 ▶ });
Branch: 1 branch
BranchTrueFalseTotal
$bigint->from_hex('0') == 0 ? : 1 0 1
325 }
326 1 ▶ if ($bigint->can('bstr')) {
Branch: 1 branch
BranchTrueFalseTotal
if ($bigint->can("bstr")) 1 0 1
327 1 $radix_to_stringize_method[10] = 'bstr';
328 1 $string_to_bigint_method[10] = 'new';
329 }
330 }
331 ### @radix_to_stringize_method
332 ### @string_to_bigint_method
333  
334 # return $n reversed in $radix
335 5 ▶sub _reverse_in_radix {
Subroutine _reverse_in_radix: called CC=6 SCAR=26.9
336 5 my ($n, $radix) = @_;
337  
338 # prefer bstr() over plain stringize "$n" since BigInt in 5.8 and 5.10
339 # seems to do something dubious in "$n" which rounds off
340 5 ▶ if (ref $n
Branch: 1 branch
BranchTrueFalseTotal
if (ref $n and $n->isa("Math::BigInt") and my $method = $radix_to_stringize_method[$radix]) 5 0 5
Condition33%2/6
ref $n and $n->isa("Math::BigInt") and my $method = $radix_to_stringize_method[$radix]
!ll&&!rl&&r
005
ref $n and $n->isa("Math::BigInt")
!ll&&!rl&&r
005
MC/DC0%0/3
ref $n and $n->isa("Math::BigInt") and my $method = $radix_to_stringize_method[$radix]
ref $n $n->isa("Math::BigInt") my $method = $radix_to_stringize_method[$radix]
Truth table25%1/4
A and B and C
A= ref $nB= $n->isa("Math::BigInt")C= my $method = $radix_to_stringize_method[$radix]
ABCresult
0XX0
10X0
1100
1111
341 && $n->isa('Math::BigInt')
342 && (my $method = $radix_to_stringize_method[$radix])) {
343 5 my $from = $string_to_bigint_method[$radix];
344 5 my $str = $n->$method();
345 5 $str =~ s/^0[bx]?//;
346 ### $str
347 ### $from
348 ### reverse: scalar(reverse($str))
349 ### result: $bigint->$from(scalar(reverse($str))).''
350 5 return $bigint->$from(scalar(reverse($str)));
351 }
352  
353 0 ▶ if ($radix == 10) {
Branch: 1 branch
BranchTrueFalseTotal
if ($radix == 10) 0 0 0
354 0 return scalar(reverse("$n"));
355 }
356  
357 # ### _reverse_in_radix(): sprintf '%#X %d', $n, $n
358  
359 0 my $ret = $n*0; # inherit bignum 0
360 0 ▶ do {
Branch: 1 branch
BranchTrueFalseTotal
$n = int $n / $radix and do { do { $ret = $ret * $radix + $n % $radix } } 0 0 0
361 0 $ret = $ret * $radix + ($n % $radix);
362 } while ($n = int($n/$radix));
363  
364 # ### ret: sprintf '%#X %d', $ret, $ret
365 0 return $ret;
366 }
367  
368 1 1;
369 __END__
« NumSeq/PisanoPeriod.pm ↑ Summary NumSeq/Fibonacci.pm »