NumSeq/WoodallNumbers.pm

filter: Statementstmt 93.5% 102 / 109 Branchbran 80.0% 24 / 30 Conditioncond 77.7% 7 / 9 MC/DCmcdc 66.6% 4 / 6 Subroutinesub 94.7% 18 / 19 Podpod 100% 7 / 7 totaltotal 90.0% 162 / 180 CC 17 SCAR 12.0
CC
17
Cov
90%
pred
7.2
value_to_i_floor
5.1
ith
3.0
CRAP 3.3
« NumSeq/MoranNumbers.pm ↑ Summary NumSeq/Pell.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::WoodallNumbers;
19 2 ▶use 5.004;
Subroutine BEGIN: called CC=1 SCAR=0.0
20 2 ▶use strict;
Subroutine BEGIN: called CC=1 SCAR=0.0
21  
22 2 ▶use vars '$VERSION', '@ISA';
Subroutine BEGIN: called CC=1 SCAR=0.0
23 2 $VERSION = 75;
24  
25 2 ▶use Math::NumSeq;
Subroutine BEGIN: called CC=1 SCAR=0.0
26 2 @ISA = ('Math::NumSeq');
27 2 *_is_infinite = \&Math::NumSeq::_is_infinite;
28  
29 2 ▶use Math::NumSeq::Fibonacci;
Subroutine BEGIN: called CC=1 SCAR=0.0
30 2 *_blog2_estimate = \&Math::NumSeq::Fibonacci::_blog2_estimate;
31  
32 # uncomment this to run the ### lines
33 #use Smart::Comments;
34  
35  
36 # use constant name => Math::NumSeq::__('Woodall Numbers');
37 2 ▶use constant description => Math::NumSeq::__('Woodall numbers i*2^i-1.');
Subroutine BEGIN: called CC=1 SCAR=0.0
38 2 ▶use constant characteristic_increasing => 1;
Subroutine BEGIN: called CC=1 SCAR=0.0
39 2 ▶use constant characteristic_integer => 1;
Subroutine BEGIN: called CC=1 SCAR=0.0
40 2 ▶use constant values_min => 1;
Subroutine BEGIN: called CC=1 SCAR=0.0
41 2 ▶use constant i_start => 1; # from 1*2^1-1==1
Subroutine BEGIN: called CC=1 SCAR=0.0
42  
43 # cf A002234 - n of Woodall primes
44 # A050918 - Woodall primes values
45 # A056821 - totient(woodall)
46 #
47 2 ▶use constant oeis_anum => 'A003261';
Subroutine BEGIN: called CC=1 SCAR=0.0
48  
49 # pow*i+1
50 2 my $uv_i_limit = do {
51 2 my $max = ~0;
52 2 my $limit = 1;
53  
54 2 ▶ for (my $i = 1; $i < 1000; $i++) {
Branch: 1 branch
BranchTrueFalseTotal
if ($i < 1000) 118 0 118
55 118 ▶ if ($i <= (($max>>1)+1) >> ($i-1)) {
Branch: 1 branch
BranchTrueFalseTotal
if ($i <= ($max >> 1) + 1 >> $i - 1) { } 116 2 118
56 116 $limit = $i;
57 } else {
58 2 last;
59 }
60 }
61  
62 ### max : $max
63 ### woodall: (1<<$limit)*$limit+1
64 ### assert: $limit*(1<<$limit)+1 <= $max
65  
66 2 $limit
67 };
68 ### $uv_i_limit
69  
70 4 ▶sub rewind {
Subroutine rewind: called CC=1 SCAR=0.0
Pod documented
71 4 my ($self) = @_;
72 4 my $i = $self->{'i'} = $self->i_start;
73 4 $self->{'power'} = 2 ** $i;
74 }
75 14 ▶sub seek_to_i {
Subroutine seek_to_i: called CC=2 SCAR=6.9
Pod documented
76 14 my ($self, $i) = @_;
77 ### seek_to_i(): $i
78 14 $self->{'i'} = $i;
79 14 ▶ if ($i >= $uv_i_limit) {
Branch: 1 branch
BranchTrueFalseTotal
if ($i >= $uv_i_limit) 2 12 14
80 2 $i = Math::NumSeq::_to_bigint($i);
81 }
82 14 $self->{'power'} = 2 ** $i;
83 }
84 0 ▶sub _UNTESTED__seek_to_value {
Subroutine _UNTESTED__seek_to_value: not called CC=1 SCAR=6.9
85 0 my ($self, $value) = @_;
86 0 $self->seek_to_i($self->value_to_i_ceil($value));
87 }
88  
89 # diff = (i+1)*2^(i+1)-1 - (i*2^i-1)
90 # = i*2^(i+1) + 2^(i+1) - i*2^i
91 # = i*(2^(i+1) - 2^i) + 2^(i+1)
92 # = i*2^i + 2^(i+1)
93 # 2*(i*2^i-1) + 2*2^i + 1
94 # = 2*i*2^i-2 + 2*2^i + 1
95 # = (2*i+2)*2^i - 1
96 # = (i+1)*2^(i+1) - 2
97 #
98 25 ▶sub next {
Subroutine next: called CC=2 SCAR=7.1
Pod documented
99 25 my ($self) = @_;
100 25 my $i = $self->{'i'}++;
101 25 ▶ if ($i == $uv_i_limit) {
Branch: 1 branch
BranchTrueFalseTotal
if ($i == $uv_i_limit) 0 25 25
102 0 $self->{'power'} = Math::NumSeq::_to_bigint($self->{'power'});
103 }
104 25 my $value = $self->{'power'}*$i - 1;
105 25 $self->{'power'} *= 2;
106 25 return ($i, $value);
107 }
108  
109 14 ▶sub ith {
Subroutine ith: called CC=3 SCAR=11.0
Pod documented
110 14 my ($self, $i) = @_;
111 14 my $power;
112 14 ▶ if (! ref $i && $i >= $uv_i_limit) {
Branch: 1 branch
BranchTrueFalseTotal
if (not ref $i and $i >= $uv_i_limit) { } 2 12 14
Condition66%2/3
not ref $i and $i >= $uv_i_limit
!ll&&!rl&&r
0122
MC/DC50%1/2
not ref $i and $i >= $uv_i_limit
not ref $i $i >= $uv_i_limit
Truth table66%2/3
not(A) and B
A= not ref $iB= $i >= $uv_i_limit
ABresult
0X0
100
111
113 2 $power = Math::NumSeq::_to_bigint(1) << $i;
114 } else {
115 12 $power = 2**$i;
116 }
117 14 return $i * $power - 1;
118 }
119  
120 9 ▶sub pred {
Subroutine pred: called CC=7 SCAR=19.7
Pod documented
121 9 my ($self, $value) = @_;
122 ### WoodallNumbers pred(): $value
123  
124 {
125 9 my $int = int($value);
126 0 ▶ if ($value != $int) { return 0; }
Branch: 1 branch
BranchTrueFalseTotal
if ($value != $int) 0 9 9
127 9 $value = $int;
128 }
129 9 ▶ unless ($value >= 1
Branch: 1 branch
BranchTrueFalseTotal
unless ($value >= 1 and $value % 2 == 1) 5 4 9
Condition100%3/3
$value >= 1 and $value % 2 == 1
!ll&&!rl&&r
144
MC/DC100%2/2
$value >= 1 and $value % 2 == 1
$value >= 1 $value % 2 == 1
Truth table100%3/3
A and B
A= $value >= 1B= $value % 2 == 1
ABresult
0X0
100
111
130 && ($value % 2) == 1) {
131 5 return 0;
132 }
133  
134 4 $value += 1; # now seeking $value == $exp * 2**$exp
135 4 ▶ if (_is_infinite($value)) {
Branch: 1 branch
BranchTrueFalseTotal
if (_is_infinite($value)) 0 4 4
136 0 return 0;
137 }
138  
139 4 my $exp = 0;
140 4 for (;;) {
141 12 ▶ if ($value <= $exp || $value % 2) {
Branch: 1 branch
BranchTrueFalseTotal
if ($value <= $exp or $value % 2) 4 8 12
Condition66%2/3
$value <= $exp or $value % 2
l!l&&r!l&&!r
408
MC/DC50%1/2
$value <= $exp or $value % 2
$value <= $exp $value % 2
Truth table66%2/3
A or B
A= $value <= $expB= $value % 2
ABresult
1X1
011
000
142 4 return ($value == $exp);
143 }
144 8 $value >>= 1;
145 8 $exp++;
146 }
147 }
148  
149 # ENHANCE-ME: round_down_pow(value,2) then exp-=log2(exp) is maybe only
150 # 0,+1,+2 away from being correct
151 #
152 22526 ▶sub value_to_i_floor {
Subroutine value_to_i_floor: called CC=5 SCAR=16.3
Pod documented
153 22526 my ($self, $value) = @_;
154 ### WoodallNumbers value_to_i_floor(): $value
155  
156 22526 $value = int($value) + 1; # now seeking $value == $exp * 2**$exp
157 22526 ▶ if ($value < 8) {
Branch: 1 branch
BranchTrueFalseTotal
if ($value < 8) 6 22520 22526
158 6 return 1;
159 }
160 22520 ▶ if (_is_infinite($value)) {
Branch: 1 branch
BranchTrueFalseTotal
if (_is_infinite($value)) 0 22520 22520
161 0 return $value;
162 }
163  
164 22520 my $i = 1;
165 22520 my $power = ($value*0) + 2; # 2^1=2, inherit bignum 2
166  
167 22520 for (;;) {
168 229351 my $try_value = $i*$power;
169  
170 ### $i
171 ### try_value: "$try_value"
172  
173 229351 ▶ if ($try_value >= $value) {
Branch: 1 branch
BranchTrueFalseTotal
if ($try_value >= $value) 22520 206831 229351
174 22520 return $i - 1 + ($try_value == $value);
175 }
176  
177 206831 ▶ if ($i == $uv_i_limit) {
Branch: 1 branch
BranchTrueFalseTotal
if ($i == $uv_i_limit) 0 206831 206831
178 0 $power = Math::NumSeq::_to_bigint($power);
179 }
180 206831 $power *= 2;
181 206831 $i++;
182 }
183 }
184  
185 # shared by Math::NumSeq::CullenNumbers
186 19 ▶sub value_to_i_estimate {
Subroutine value_to_i_estimate: called CC=3 SCAR=11.0
Pod documented
187 19 my ($self, $value) = @_;
188  
189 19 ▶ if ($value < 1) {
Branch: 1 branch
BranchTrueFalseTotal
if ($value < 1) 8 11 19
190 8 return 0;
191 }
192  
193 11 my $i = _blog2_estimate($value);
194 11 ▶ if (! defined $i) {
Branch: 1 branch
BranchTrueFalseTotal
unless (defined $i) 10 1 11
195 10 $i = log($value) * (1/log(2));
196 }
197 11 $i -= log($i) * (1/log(2));
198 11 return int($i);
199 }
200  
201 2 1;
202 __END__
« NumSeq/MoranNumbers.pm ↑ Summary NumSeq/Pell.pm »