NumSeq/LucasNumbers.pm

filter: Statementstmt 95.2% 139 / 146 Branchbran 84.7% 39 / 46 Conditioncond 73.3% 11 / 15 MC/DCmcdc 55.5% 5 / 9 Subroutinesub 100% 21 / 21 Podpod 81.8% 9 / 11 totaltotal 90.3% 224 / 248 CC 28 SCAR 15.7
CC
28
Cov
91%
ith_pair
10.1
ith
8.0
value_to_i_estimate
4.0
CRAP 4.8
« NumSeq/FibbinaryBitCount.pm ↑ Summary NumSeq/Abundant.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::LucasNumbers;
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 2 ▶use Math::NumSeq::Base::Sparse;
Subroutine BEGIN: called CC=1 SCAR=0.0
25 2 @ISA = ('Math::NumSeq::Base::Sparse');
26  
27 2 ▶use Math::NumSeq;
Subroutine BEGIN: called CC=1 SCAR=0.0
28 2 *_is_infinite = \&Math::NumSeq::_is_infinite;
29 2 *_to_bigint = \&Math::NumSeq::_to_bigint;
30  
31 2 ▶use Math::NumSeq::Fibonacci;
Subroutine BEGIN: called CC=1 SCAR=0.0
32 2 *_blog2_estimate = \&Math::NumSeq::Fibonacci::_blog2_estimate;
33 2 *_bit_split_hightolow = \&Math::NumSeq::Fibonacci::_bit_split_hightolow;
34  
35  
36 # uncomment this to run the ### lines
37 # use Smart::Comments;
38  
39  
40 # use constant name => Math::NumSeq::__('Lucas Numbers');
41 4 ▶sub description {
Subroutine description: called CC=3 SCAR=11.0
Pod documented
42 4 my ($self) = @_;
43 4 ▶ if (ref $self && $self->i_start == 0) {
Branch: 1 branch
BranchTrueFalseTotal
if (ref $self and $self->i_start == 0) { } 1 3 4
Condition100%3/3
ref $self and $self->i_start == 0
!ll&&!rl&&r
211
MC/DC100%2/2
ref $self and $self->i_start == 0
ref $self $self->i_start == 0
Truth table100%3/3
A and B
A= ref $selfB= $self->i_start == 0
ABresult
0X0
100
111
44 1 return Math::NumSeq::__('Lucas numbers 2, 1, 3, 4, 7, 11, 18, 29, etc, being L(i+1) = L(i) + L(i-1) starting from 2,1. This is the same recurrence as the Fibonacci numbers, but a different starting point.');
45 } else {
46 3 return Math::NumSeq::__('Lucas numbers 1, 3, 4, 7, 11, 18, 29, etc, being L(i+1) = L(i) + L(i-1) starting from 1,3. This is the same recurrence as the Fibonacci numbers, but a different starting point.');
47 }
48 }
49  
50 # negatives at i odd negative, otherwise minimum 1 at i=1
51 2 ▶sub values_min {
Subroutine values_min: called CC=3 SCAR=11.0
Pod documented
52 2 my ($self) = @_;
53 2 my $i = $self->i_start;
54 2 ▶ if ($i <= 0 && $i % 2 == 0) {
Branch: 1 branch
BranchTrueFalseTotal
if ($i <= 0 and $i % 2 == 0) 1 1 2
Condition66%2/3
$i <= 0 and $i % 2 == 0
!ll&&!rl&&r
101
MC/DC50%1/2
$i <= 0 and $i % 2 == 0
$i <= 0 $i % 2 == 0
Truth table66%2/3
A and B
A= $i <= 0B= $i % 2 == 0
ABresult
0X0
100
111
55 # i even, increase to make i odd and i<=1
56 1 $i += 1;
57 }
58 2 return $self->ith($i);
59 }
60  
61 5 ▶sub characteristic_increasing {
Subroutine characteristic_increasing: called CC=1 SCAR=0.0
Pod undocumented
62 5 my ($self) = @_;
63 # not increasing at i=0 value=2 then i=1 value=1
64 5 return ($self->i_start >= 1);
65 }
66 1 ▶sub characteristic_increasing_from_i {
Subroutine characteristic_increasing_from_i: called CC=1 SCAR=0.0
Pod undocumented
67 1 my ($self) = @_;
68 1 return _max($self->i_start,1);
69 }
70 2 ▶use constant characteristic_integer => 1;
Subroutine BEGIN: called CC=1 SCAR=0.0
71 2 ▶use constant default_i_start => 1;
Subroutine BEGIN: called CC=1 SCAR=0.0
72  
73 1 ▶sub _max {
Subroutine _max: called CC=3 SCAR=11.2
74 1 my $ret = shift;
75 1 ▶ while (@_) {
Branch: 1 branch
BranchTrueFalseTotal
if (@_) 1 1 2
76 1 my $next = shift;
77 1 ▶ if ($next > $ret) {
Branch: 1 branch
BranchTrueFalseTotal
if ($next > $ret) 0 1 1
78 0 $ret = $next;
79 }
80 }
81 1 return $ret;
82 }
83  
84 #------------------------------------------------------------------------------
85 # cf A000285 starting 1,4
86 # A022086 starting 0,3
87 # A022087 starting 0,4
88 # A022095 starting 1,5
89 # A022130 starting 4,9
90 # A080023 closest to log(phi), 2,3,4,7,11
91 # A169985 nearestint(phi^n) 1,2,3,4,7,11,18
92 {
93 2 my %oeis_anum = (
94 # OEIS-Catalogue array begin
95 0 => 'A000032', # i_start=0 # Lucas starting at 2,1,3,...
96 1 => 'A000204', # # Lucas starting at 1,3,...
97 # OEIS-Catalogue array end
98 );
99 2 ▶ sub oeis_anum {
Subroutine oeis_anum: called CC=1 SCAR=0.0
Pod documented
100 2 my ($self) = @_;
101 2 return $oeis_anum{$self->i_start};
102 }
103 }
104  
105 #------------------------------------------------------------------------------
106  
107 # the biggest f0 for which both f0 and f1 fit into a UV, and which therefore
108 # for the next step will require BigInt
109 #
110 2 my $uv_limit;
111 my $uv_i_limit;
112 {
113 # Float integers too in 32 bits ?
114 # my $max = 1;
115 # for (1 .. 256) {
116 # my $try = $max*2 + 1;
117 # ### $try
118 # if ($try == 2*$max || $try == 2*$max+2) {
119 # last;
120 # }
121 # $max = $try;
122 # }
123 2 my $max = ~0;
124  
125 # f1+f0 > i
126 # f0 > i-f1
127 # check i-f1 as the stopping point, so that if i=UV_MAX then won't
128 # overflow a UV trying to get to f1>=i
129 #
130 2 my $i = 0;
131 2 my $f0 = 1;
132 2 my $f1 = 3;
133 2 my $prev_f0;
134 2 ▶ while ($f0 <= $max - $f1) {
Branch: 1 branch
BranchTrueFalseTotal
if ($f0 <= $max - $f1) 180 2 182
135 180 $prev_f0 = $f0;
136 180 ($f1,$f0) = ($f1+$f0,$f1);
137 180 $i++;
138 }
139 ### $prev_f0
140 ### $f0
141 ### $f1
142 ### ~0 : ~0
143  
144 2 $uv_limit = $prev_f0;
145 2 $uv_i_limit = $i;
146 ### $uv_limit
147 ### $uv_i_limit
148 ### assert: __PACKAGE__->ith($uv_i_limit) == $uv_limit
149 };
150  
151 #------------------------------------------------------------------------------
152  
153 11 ▶sub rewind {
Subroutine rewind: called CC=1 SCAR=0.0
Pod documented
154 11 my ($self) = @_;
155 11 $self->seek_to_i($self->i_start);
156 }
157 26 ▶sub seek_to_i {
Subroutine seek_to_i: called CC=2 SCAR=7.2
Pod documented
158 26 my ($self, $i) = @_;
159 26 $self->{'i'} = $i;
160 26 ▶ if (abs($i) >= $uv_i_limit) {
Branch: 1 branch
BranchTrueFalseTotal
if (abs $i >= $uv_i_limit) 0 26 26
161 0 $i = Math::NumSeq::_to_bigint($i);
162 }
163 26 $self->{'f0'} = $self->ith($i);
164 26 $self->{'f1'} = $self->ith($i+1);
165  
166 # or perhaps
167 # ($self->{'f0'}, $self->{'f1'}) = $self->ith_pair($i);
168 }
169  
170 109 ▶sub next {
Subroutine next: called CC=2 SCAR=7.9
Pod documented
171 109 my ($self) = @_;
172 ### LucasNumbers next(): "f0=$self->{'f0'}, f1=$self->{'f1'}"
173  
174 (my $ret,
175 $self->{'f0'},
176 $self->{'f1'})
177 = ($self->{'f0'},
178 $self->{'f1'},
179 109 $self->{'f0'}+$self->{'f1'});
180 ### $ret
181  
182 109 ▶ if ($ret == $uv_limit) {
Branch: 1 branch
BranchTrueFalseTotal
if ($ret == $uv_limit) 0 109 109
183 0 $self->{'f0'} = Math::NumSeq::_to_bigint($self->{'f0'});
184 0 $self->{'f1'} = Math::NumSeq::_to_bigint($self->{'f1'});
185 }
186  
187 109 return ($self->{'i'}++, $ret);
188 }
189  
190 # F[4] = (F[2]+L[2])^2/2 - 3*F[2]^2 - 2*(-1)^2
191 # = (1+3)^2/4 - 3*1^2 - 2
192 # = 16/4 - 3 - 2
193  
194 # F[3] = ((F[1]+L[1])^2 - 2*(-1)^1)/4 + F[1]^2
195 # = ((1+3)^2 - -2)/4 + 1^2
196 # = (16 + 2)/4 + 1
197 # = (16 + 2)/4 + 1
198  
199 # F[3] = (F[1]+L[1])^2/4 + F[1]^2
200 # = (1+3)^2/4 + 1^2
201 # = 16/4 + 1
202 # = 5
203  
204 # -8,5,-3,2,-1,1, 0, 1,1,2,3,5,8,13,21
205 # -11,7,-4,3,-1, 2, 1,3,4,7,11,18,29
206 #
207  
208 90 ▶sub ith {
Subroutine ith: called CC=8 SCAR=20.8
Pod documented
209 90 my ($self, $i) = @_;
210 ### LucasNumbers ith(): $i
211  
212 90 ▶ if (_is_infinite($i)) {
Branch: 1 branch
BranchTrueFalseTotal
if (_is_infinite($i)) 0 90 90
213 0 return $i;
214 }
215 90 $i = int($i);
216 90 ▶ if ($i == 0) {
Branch: 1 branch
BranchTrueFalseTotal
if ($i == 0) 11 79 90
217 11 return 2;
218 }
219  
220 # automatic BigInt if not another bignum class
221 79 ▶ my $to_bigint = ($i >= $uv_i_limit || $i <= -$uv_i_limit && ! ref $i);
Condition83%5/6
$i >= $uv_i_limit || $i <= -$uv_i_limit && !ref($i)
l!l&&r!l&&!r
2275
$i <= -$uv_i_limit and not ref $i
!ll&&!rl&&r
7502
MC/DC66%2/3
$i >= $uv_i_limit || $i <= -$uv_i_limit && !ref($i)
$i >= $uv_i_limit $i <= -$uv_i_limit not ref $i
Truth table75%3/4
A || B and not(C)
A= $i >= $uv_i_limitB= $i <= -$uv_i_limitC= not ref $i
ABCresult
1XX1
0111
00X0
0100
222 ### $to_bigint
223  
224 79 my $lowzeros = 0;
225 79 ▶ until ($i % 2) {
Branch: 1 branch
BranchTrueFalseTotal
unless ($i % 2) 52 79 131
226 52 $lowzeros++;
227 52 $i /= 2;
228 }
229  
230 79 my ($L0) = $self->ith_pair($i);
231 ### $L0
232 79 ▶ if ($to_bigint) {
Branch: 1 branch
BranchTrueFalseTotal
if ($to_bigint) 4 75 79
233 ### to bigint ...
234 4 $L0 = _to_bigint($L0);
235 ### $L0
236 }
237  
238 ### apply lowzeros: $lowzeros
239 79 my $add = -2;
240 79 ▶ while ($lowzeros--) {
Branch: 1 branch
BranchTrueFalseTotal
if ($lowzeros--) 52 79 131
241 52 $L0 *= $L0;
242 52 $L0 -= $add;
243 52 $add = 2;
244 ### lowzeros L0: "$L0 " . ref $L0
245 }
246  
247 ### final ith() ...
248 ### L0: "$L0"
249  
250 79 return $L0;
251  
252  
253 # {
254 # # cf plain interative
255 # $i--;
256 # my $f0 = ($i * 0) + 1; # inherit bignum 1
257 # my $f1 = $f0 + 2; # inherit bignum 3
258 # while (--$i > 0) {
259 # $f0 += $f1;
260 #
261 # unless (--$i > 0) {
262 # return $f0;
263 # }
264 # $f1 += $f0;
265 # }
266 # return $f1;
267 # }
268 }
269  
270 112 ▶sub ith_pair {
Subroutine ith_pair: called CC=10 SCAR=23.1
Pod documented
271 112 my ($self, $i) = @_;
272 ### LucasNumbers ith_pair(): $i
273  
274 112 ▶ if (_is_infinite($i)) {
Branch: 1 branch
BranchTrueFalseTotal
if (_is_infinite($i)) 0 112 112
275 0 return ($i,$i);
276 }
277 112 $i = int($i);
278  
279 112 my $neg;
280 112 ▶ if ($i < 0) {
Branch: 1 branch
BranchTrueFalseTotal
if ($i < 0) 22 90 112
281 22 $i = -1 - $i; # L[-k] = L[-1-k] * (-1)^k
282 22 $neg = 1;
283 }
284  
285 112 my ($Lk, $Lkplus1);
286 112 ▶ if ($i == 0) {
Branch: 1 branch
BranchTrueFalseTotal
if ($i == 0) { } 9 103 112
287 9 $Lk = 2; # L[0] = 2
288 9 $Lkplus1 = 1; # L[1] = 1
289  
290 } else {
291 # initial k=1
292 103 ▶ my $zero = ($i >= $uv_i_limit && ! ref $i
Branch: 1 branch
BranchTrueFalseTotal
$i >= $uv_i_limit && !ref($i) ? : 0 103 103
Condition33%1/3
$i >= $uv_i_limit and not ref $i
!ll&&!rl&&r
10300
MC/DC0%0/2
$i >= $uv_i_limit and not ref $i
$i >= $uv_i_limit not ref $i
Truth table33%1/3
A and not(B)
A= $i >= $uv_i_limitB= not ref $i
ABresult
0X0
100
111
293 ? _to_bigint(0) # automatic BigInt if not another bignum class
294 : $i * 0); # inherit bignum $i
295  
296 103 $Lk = 1 + $zero; # L[k] = L[1] = 1
297 103 $Lkplus1 = 3 + $zero; # L[k+1] = L[2] = 3
298 103 my $add = -2; # 2*(-1)^k
299  
300  
301 103 my @bits = _bit_split_hightolow($i);
302 ### @bits
303 103 shift @bits; # drop high 1-bit
304  
305 103 ▶ while (@bits) {
Branch: 1 branch
BranchTrueFalseTotal
if (@bits) 111 103 214
306 ### at: "Lk=$Lk Lkplus1=$Lkplus1 bit=$bits[0]"
307 111 $Lk *= $Lk;
308 111 $Lk -= $add; # L[2k] = L[k]^2 - 2*(-1)^k
309  
310 111 $Lkplus1 *= $Lkplus1;
311 111 $Lkplus1 += $add; # L[2k+2] = L[k+1]^2 + 2*(-1)^k
312  
313 # L[2k+1] = L[2k+2] - L[2k]
314 111 my $Lmid = $Lkplus1 - $Lk; # L[2k+1] = L[2k+2] - L[2k]
315  
316 111 ▶ if (shift @bits) { # high to low
Branch: 1 branch
BranchTrueFalseTotal
if (shift @bits) { } 57 54 111
317 57 $Lk = $Lmid; # L[2k+1], L[2k+2]
318 57 $add = -2;
319 } else {
320 54 $Lkplus1 = $Lmid; # L[2k], L[2k+1]
321 54 $add = 2;
322 }
323 }
324 }
325 ### loop final: "Lk=$Lk Lkplus1=$Lkplus1"
326  
327 112 ▶ if ($neg) {
Branch: 1 branch
BranchTrueFalseTotal
if ($neg) 22 90 112
328 22 ($Lk,$Lkplus1) = ($Lkplus1, $Lk);
329 22 ▶ if ($i % 2) {
Branch: 1 branch
BranchTrueFalseTotal
if ($i % 2) { } 4 18 22
330 4 $Lkplus1 = -$Lkplus1;
331 } else {
332 18 $Lk = -$Lk;
333 }
334 }
335 112 return ($Lk, $Lkplus1);
336 }
337  
338 2 ▶use constant 1.02 _PHI => (1 + sqrt(5)) / 2;
Subroutine BEGIN: called CC=1 SCAR=0.0
339  
340 33 ▶sub value_to_i_estimate {
Subroutine value_to_i_estimate: called CC=4 SCAR=14.0
Pod documented
341 33 my ($self, $value) = @_;
342 33 ▶ if (_is_infinite($value)) {
Branch: 1 branch
BranchTrueFalseTotal
if (_is_infinite($value)) 0 33 33
343 0 return $value;
344 }
345 33 ▶ if ($value <= 0) {
Branch: 1 branch
BranchTrueFalseTotal
if ($value <= 0) 14 19 33
346 14 return 0;
347 }
348 19 ▶ if (defined (my $blog2 = _blog2_estimate($value))) {
Branch: 1 branch
BranchTrueFalseTotal
if (defined(my $blog2 = _blog2_estimate($value))) 2 17 19
349 # i ~= log2(L(i)) / log2(phi)
350 # with log2(x) = log(x)/log(2)
351 2 return int($blog2 * (1 / (log(_PHI)/log(2))));
352 }
353  
354 # i ~= log(L(i)) / log(phi)
355 17 return int(log($value) * (1/log(_PHI)));
356 }
357  
358 2 1;
359 __END__
« NumSeq/FibbinaryBitCount.pm ↑ Summary NumSeq/Abundant.pm »