NumSeq/NumAronson.pm

filter: Statementstmt 94.7% 72 / 76 Branchbran 90.9% 20 / 22 Conditioncond 66.6% 6 / 9 MC/DCmcdc 60.0% 3 / 5 Subroutinesub 100% 15 / 15 Podpod 100% 4 / 4 totaltotal 91.6% 120 / 131 CC 15 SCAR 13.5
CC
15
Cov
92%
_round_down_pow
8.6
next
4.0
pred
4.0
CRAP 3.9
« NumSeq/Factorials.pm ↑ Summary NumSeq/Fibbinary.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::NumAronson;
19 8 ▶use 5.004;
Subroutine BEGIN: called CC=1 SCAR=0.0
20 8 ▶use strict;
Subroutine BEGIN: called CC=1 SCAR=0.0
21  
22 8 ▶use vars '$VERSION', '@ISA';
Subroutine BEGIN: called CC=1 SCAR=0.0
23 8 $VERSION = 75;
24 8 ▶use Math::NumSeq;
Subroutine BEGIN: called CC=1 SCAR=0.0
25 8 @ISA = ('Math::NumSeq');
26  
27 # uncomment this to run the ### lines
28 #use Devel::Comments;
29  
30  
31 # use constant name => Math::NumSeq::__('Numerical Aronson');
32 8 ▶use constant description => Math::NumSeq::__('Numerical version of Aronson\'s sequence');
Subroutine BEGIN: called CC=1 SCAR=0.0
33 8 ▶use constant values_min => 1;
Subroutine BEGIN: called CC=1 SCAR=0.0
34 8 ▶use constant characteristic_increasing => 1;
Subroutine BEGIN: called CC=1 SCAR=0.0
35 8 ▶use constant characteristic_integer => 1;
Subroutine BEGIN: called CC=1 SCAR=0.0
36 8 ▶use constant i_start => 1;
Subroutine BEGIN: called CC=1 SCAR=0.0
37  
38 # cf A080596 - a(1)=1
39 # A079253 - even
40 # A081023 - lying
41 # A014132 - lying opposite parity
42 8 ▶use constant oeis_anum => 'A079000';
Subroutine BEGIN: called CC=1 SCAR=0.0
43  
44 # a(9*2^k - 3 + j) = 12*2^k - 3 + (3/2)*j + (1/2)*abs(j)
45 # where k>=0 and -3*2^k <= j < 3*2^k
46 # step
47 # a(n+1) - 2*a(n) + a(n-1) = 1 if n=9*2^k-3, k>=0
48 # = -1 if n = 2 and 3*2^k-3, k>=1
49 # = 0 otherwise.
50 #
51 # lying
52 # g(3*2^k-1 + j) = 2*2^(k+1)-1 + (3/2)*j + (1/2)*abs(j)
53 # where -2^k <= j < 2^k and k>0
54 #
55 # then lying is d(n)=g(n+1)-1 n>=1
56  
57 3 ▶sub rewind {
Subroutine rewind: called CC=1 SCAR=0.0
Pod documented
58 3 my ($self) = @_;
59 3 $self->{'i'} = $self->i_start;
60 3 $self->{'pow'} = 0;
61 3 $self->{'j'} = -1;
62 }
63  
64 90 ▶sub next {
Subroutine next: called CC=4 SCAR=13.9
Pod documented
65 90 my ($self) = @_;
66 90 my $pow = $self->{'pow'};
67 90 my $j = ++ $self->{'j'};
68  
69 90 ▶ if ($pow == 0) {
Branch: 2 branches
BranchTrueFalseTotal
if ($pow == 0) { } 6 84 90
elsif ($j >= 3 * $pow) { } 6 78 84
70 # low special cases initial 1,4,
71 6 ▶ if ($j < 2) {
Branch: 1 branch
BranchTrueFalseTotal
if ($j < 2) 4 2 6
72 4 return ($self->{'i'}++, $j*3 + 1);
73 }
74 2 $pow = $self->{'pow'} = 1; # 2**k for k=0
75 2 $j = $self->{'j'} = -3; # -3*(2**k) for k=0
76 } elsif ($j >= 3 * $pow) {
77 6 $pow = ($self->{'pow'} *= 2);
78 6 $j = $self->{'j'} = -3 * $pow;
79 }
80  
81 ### assert: -3 * $pow <= $j
82 ### assert: $j < 3 * $pow
83  
84 86 return ($self->{'i'}++, 12*$pow - 3 + (3*$j + abs($j))/2);
85 }
86  
87 # i = 9*2^k - 3 + j
88 # base at j=-3*2^k
89 # is i >= 9*2^k - 3 - 3*2^k
90 # i >= 6*2^k - 3
91 # i+3 >= 6*2^k
92 # (i+3)/6 >= 2^k
93 # 2^k <= (i+3)/6
94 # then i = 9*2^k - 3 + j
95 # j = i - 9*2^k + 3
96 #
97 138 ▶sub ith {
Subroutine ith: called CC=3 SCAR=11.0
Pod documented
98 138 my ($self, $i) = @_;
99 ### NumAronson ith(): $i
100  
101 # special cases ith(1)=1, ith(2)=4
102 138 ▶ if ($i <= 2) {
Branch: 1 branch
BranchTrueFalseTotal
if ($i <= 2) 9 129 138
103 9 ▶ if ($i < 0) {
Branch: 1 branch
BranchTrueFalseTotal
if ($i < 0) { } 3 6 9
104 3 return undef;
105 } else {
106 6 return $i*$i;
107 }
108 }
109  
110 129 my ($pow, $k) = _round_down_pow (int(($i+3)/6), 2);
111 129 my $j = $i - 9*$pow + 3;
112  
113 ### round down for k: ($i+3)/6
114 ### $k
115 ### $pow
116 ### $j
117 ### assert: $k >= 0
118 ### assert: -3 * 2 ** $k <= $j
119 ### assert: $j < 3 * 2 ** $k
120  
121 129 return 12*$pow - 3 + (3*$j + abs($j))/2;
122 }
123  
124 # value = 12*2^k - 3 + (3/2)*j + (1/2)*abs(j)
125 # minimum j=-3*2^k
126 # value = 12*2^k - 3 + (3*j + abs(j))/2
127 # = 12*2^k - 3 + (3*-3*2^k + 3*2^k)/2
128 # = 12*2^k - 3 + (-9 + 3)*2^k/2
129 # = 12*2^k - 3 + -6*2^k/2
130 # = 12*2^k - 3 + -3*2^k
131 # = 9*2^k - 3
132 # value >= 9*2^k - 3
133 # value+3 >= 9*2^k
134 # 9*2^k <= value+3
135 # 2^k <= (value+3)/9
136 #
137 # from which
138 # value = 12*2^k - 3 + (3*j + abs(j))/2
139 # (3*j + abs(j))/2 = value - 12*2^k + 3
140 # 3*j + abs(j) = 2*(value - 12*2^k + 3)
141 #
142 # j>=0 4*j = a, j=a/4
143 # j<0 3*$j-$j = 2*$j = a, j=a/2
144 #
145 182 ▶sub pred {
Subroutine pred: called CC=4 SCAR=13.9
Pod documented
146 182 my ($self, $value) = @_;
147 ### NumAronson pred(): $value
148  
149 # special cases pred(1) true, pred(4) true
150 182 ▶ if ($value < 6) {
Branch: 1 branch
BranchTrueFalseTotal
if ($value < 6) 12 170 182
151 12 ▶ return ($value == 1 || $value == 4);
Condition100%3/3
$value == 1 || $value == 4
l!l&&r!l&&!r
228
MC/DC100%2/2
$value == 1 || $value == 4
$value == 1 $value == 4
Truth table100%3/3
A || B
A= $value == 1B= $value == 4
ABresult
1X1
011
000
152 }
153  
154 170 my $k = _round_down_pow (int(($value+3)/9), 2);
155 170 my $pow = 2**$k;
156 170 my $aj = 2*($value - 12*$pow + 3);
157 170 ▶ return ($aj % ($aj < 0 ? 2 : 4)) == 0;
Branch: 1 branch
BranchTrueFalseTotal
$aj < 0 ? : 65 105 170
158 }
159  
160 #------------------------------------------------------------------------------
161 # generic
162  
163 # return ($pow, $exp) with $pow = $base**$exp <= $n,
164 # the next power of $base at or below $n
165 #
166 2859 ▶sub _round_down_pow {
Subroutine _round_down_pow: called CC=7 SCAR=21.5
167 2859 my ($n, $base) = @_;
168 ### _round_down_pow(): "$n base $base"
169  
170 2859 ▶ if ($n < $base) {
Branch: 1 branch
BranchTrueFalseTotal
if ($n < $base) 644 2215 2859
171 644 return (1, 0);
172 }
173  
174 # Math::BigInt and Math::BigRat overloaded log() return NaN, use integer
175 # based blog()
176 2215 ▶ if (ref $n && ($n->isa('Math::BigInt') || $n->isa('Math::BigRat'))) {
Branch: 1 branch
BranchTrueFalseTotal
if (ref $n and $n->isa("Math::BigInt") || $n->isa("Math::BigRat")) 13 2202 2215
Condition50%3/6
ref $n and $n->isa("Math::BigInt") || $n->isa("Math::BigRat")
!ll&&!rl&&r
2202013
$n->isa("Math::BigInt") or $n->isa("Math::BigRat")
l!l&&r!l&&!r
1300
MC/DC33%1/3
ref $n and $n->isa("Math::BigInt") || $n->isa("Math::BigRat")
ref $n $n->isa("Math::BigInt") $n->isa("Math::BigRat")
Truth table50%2/4
A and B or C
A= ref $nB= $n->isa("Math::BigInt")C= $n->isa("Math::BigRat")
ABCresult
0XX0
1000
11X1
1011
177 13 my $exp = $n->copy->blog($base);
178 13 return (Math::BigInt->new(1)->blsft($exp,$base),
179 $exp);
180 }
181  
182 2202 my $exp = int(log($n)/log($base));
183 2202 my $pow = $base**$exp;
184  
185 ### n: ref($n)." $n"
186 ### exp: ref($exp)." $exp"
187 ### pow: ref($pow)." $pow"
188  
189 # check how $pow actually falls against $n, not sure should trust float
190 # rounding in log()/log($base)
191 # Crib: $n as first arg in case $n==BigFloat and $pow==BigInt
192 2202 ▶ if ($n < $pow) {
Branch: 2 branches
BranchTrueFalseTotal
if ($n < $pow) { } 0 2202 2202
elsif ($n >= $base * $pow) { } 0 2202 2202
193 ### hmm, int(log) too big, decrease...
194 0 $exp -= 1;
195 0 $pow = $base**$exp;
196 } elsif ($n >= $base*$pow) {
197 ### hmm, int(log) too small, increase...
198 0 $exp += 1;
199 0 $pow *= $base;
200 }
201 2202 return ($pow, $exp);
202 }
203  
204 8 1;
205 __END__
« NumSeq/Factorials.pm ↑ Summary NumSeq/Fibbinary.pm »