NumSeq/Fibonacci.pm

filter: Statementstmt 86.3% 133 / 154 Branchbran 68.9% 40 / 58 Conditioncond 50.0% 6 / 12 MC/DCmcdc 37.5% 3 / 8 Subroutinesub 95.4% 21 / 22 Podpod 100% 6 / 6 totaltotal 80.3% 209 / 260 CC 33 SCAR 29.2
CC
33
Cov
80%
_UNTESTED__value_to_i
90.0
ith_pair
9.0
_blog2_estimate
5.6
CRAP 18.6
« NumSeq/ReverseAdd.pm ↑ Summary NumSeq/FractionDigits.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::Fibonacci;
19 28 ▶use 5.004;
Subroutine BEGIN: called CC=1 SCAR=0.0
20 28 ▶use strict;
Subroutine BEGIN: called CC=1 SCAR=0.0
21  
22 28 ▶use vars '$VERSION','@ISA';
Subroutine BEGIN: called CC=1 SCAR=0.0
23 28 $VERSION = 75;
24 28 ▶use Math::NumSeq::Base::Sparse; # FIXME: implement pred() directly ...
Subroutine BEGIN: called CC=1 SCAR=0.0
25 28 @ISA = ('Math::NumSeq::Base::Sparse');
26  
27 28 ▶use Math::NumSeq;
Subroutine BEGIN: called CC=1 SCAR=0.0
28 28 *_is_infinite = \&Math::NumSeq::_is_infinite;
29 28 *_to_bigint = \&Math::NumSeq::_to_bigint;
30  
31 # uncomment this to run the ### lines
32 # use Smart::Comments;
33  
34  
35 # use constant name => Math::NumSeq::__('Fibonacci Numbers');
36 28 ▶use constant description => Math::NumSeq::__('The Fibonacci numbers 1,1,2,3,5,8,13,21, etc, each F(i) = F(i-1) + F(i-2), starting from 1,1.');
Subroutine BEGIN: called CC=1 SCAR=0.0
37  
38 28 ▶use constant values_min => 0;
Subroutine BEGIN: called CC=1 SCAR=0.0
39 28 ▶use constant i_start => 0;
Subroutine BEGIN: called CC=1 SCAR=0.0
40 28 ▶use constant characteristic_increasing => 1;
Subroutine BEGIN: called CC=1 SCAR=0.0
41 28 ▶use constant characteristic_integer => 1;
Subroutine BEGIN: called CC=1 SCAR=0.0
42  
43 #------------------------------------------------------------------------------
44 # cf A105527 - index when n-nacci exceeds Fibonacci
45 # A020695 - Pisot 2,3,5,8,etc starting OFFSET=0
46 # A212804 - starting 1,0 OFFSET=0
47  
48 28 ▶use constant oeis_anum => 'A000045'; # Fibonacci starting at i=0 0,1,1,2,3
Subroutine BEGIN: called CC=1 SCAR=0.0
49  
50 #------------------------------------------------------------------------------
51  
52 # $uv_limit is the biggest Fibonacci number f0 for which both f0 and f1 fit
53 # into a UV. Upon reaching $uv_limit the next step will require BigInt.
54 # $uv_i_limit is the i index of $uv_limit.
55 #
56 28 my $uv_limit;
57 28 my $uv_i_limit = 0;
58 {
59 # Float integers too in 32 bits ?
60 # my $max = 1;
61 # for (1 .. 256) {
62 # my $try = $max*2 + 1;
63 # ### $try
64 # if ($try == 2*$max || $try == 2*$max+2) {
65 # last;
66 # }
67 # $max = $try;
68 # }
69 28 my $max = ~0;
70  
71 # f1+f0 > i
72 # f0 > i-f1
73 # check i-f1 as the stopping point, so that if i=UV_MAX then won't
74 # overflow a UV trying to get to f1>=i
75 #
76 28 my $f0 = 1;
77 28 my $f1 = 1;
78 28 my $prev_f0;
79 28 ▶ while ($f0 <= $max - $f1) {
Branch: 1 branch
BranchTrueFalseTotal
if ($f0 <= $max - $f1) 2548 28 2576
80 2548 $prev_f0 = $f0;
81 2548 ($f1,$f0) = ($f1+$f0,$f1);
82 2548 $uv_i_limit++;
83 }
84  
85 ### Fibonacci UV limit ...
86 ### $prev_f0
87 ### $f0
88 ### $f1
89 ### ~0 : ~0
90  
91 28 $uv_limit = $prev_f0;
92  
93 ### $uv_limit
94 ### $uv_i_limit
95  
96 28 ▶ __PACKAGE__->ith($uv_i_limit) == $uv_limit
Branch: 1 branch
BranchTrueFalseTotal
__PACKAGE__->ith($uv_i_limit) == $uv_limit or warn "Oops, wrong uv_i_limit" 28 0 28
97 or warn "Oops, wrong uv_i_limit";
98 }
99  
100 10 ▶sub rewind {
Subroutine rewind: called CC=1 SCAR=0.0
Pod documented
101 10 my ($self) = @_;
102 ### Fibonacci rewind()
103 10 $self->{'f0'} = 0;
104 10 $self->{'f1'} = 1;
105 10 $self->{'i'} = $self->i_start;
106 }
107 183 ▶sub seek_to_i {
Subroutine seek_to_i: called CC=1 SCAR=0.0
Pod documented
108 183 my ($self, $i) = @_;
109 183 ($self->{'f0'}, $self->{'f1'}) = $self->ith_pair($i);
110 183 $self->{'i'} = $i;
111 }
112 1139 ▶sub next {
Subroutine next: called CC=2 SCAR=6.9
Pod documented
113 1139 my ($self) = @_;
114 ### Fibonacci next(): "f0=$self->{'f0'}, f1=$self->{'f1'}"
115 (my $ret,
116 $self->{'f0'},
117 $self->{'f1'})
118 = ($self->{'f0'},
119 $self->{'f1'},
120 1139 $self->{'f0'} + $self->{'f1'});
121 ### $ret
122  
123 1139 ▶ if ($ret == $uv_limit) {
Branch: 1 branch
BranchTrueFalseTotal
if ($ret == $uv_limit) 4 1135 1139
124 ### go to bigint f1 ...
125 4 $self->{'f1'} = _to_bigint($self->{'f1'});
126 }
127  
128 1139 return ($self->{'i'}++, $ret);
129 }
130  
131 # F[k-1] + F[k] = F[k+1]
132 # F[k-1] = F[k+1] - F[k]
133 # F[2k+1] = (2F[k]+F[k-1])*(2F[k]-F[k-1]) + 2*(-1)^k
134 # = (2F[k] + F[k+1] - F[k])*(2F[k] - (F[k+1] - F[k])) + 2*(-1)^k
135 # = (F[k] + F[k+1])*(2F[k] - F[k+1] + F[k]) + 2*(-1)^k
136 # = (F[k] + F[k+1])*(3F[k] - F[k+1]) + 2*(-1)^k
137 # F[2k] = F[k]*(F[k]+2F[k-1])
138 # = F[k]*(F[k]+2(F[k+1] - F[k]))
139 # = F[k]*(F[k]+2F[k+1] - 2F[k])
140 # = F[k]*(2F[k+1] - F[k])
141  
142 686 ▶sub ith {
Subroutine ith: called CC=5 SCAR=16.1
Pod documented
143 686 my ($self, $i) = @_;
144 ### Fibonacci ith(): $i
145  
146 686 my $lowbit = ($i % 2);
147 686 my $pair_i = ($i - $lowbit) / 2;
148 686 my ($F0, $F1) = $self->ith_pair($pair_i);
149  
150 686 ▶ if ($i > $uv_i_limit && ! ref $F0) {
Branch: 1 branch
BranchTrueFalseTotal
if ($i > $uv_i_limit and not ref $F0) 243 443 686
Condition100%3/3
$i > $uv_i_limit and not ref $F0
!ll&&!rl&&r
4412243
MC/DC100%2/2
$i > $uv_i_limit and not ref $F0
$i > $uv_i_limit not ref $F0
Truth table100%3/3
A and not(B)
A= $i > $uv_i_limitB= not ref $F0
ABresult
0X0
100
111
151 ### automatic BigInt as not another bignum class ...
152 243 $F0 = _to_bigint($F0);
153 243 $F1 = _to_bigint($F1);
154 }
155  
156 # last step needing just one of F[2k] or F[2k+1] done by one multiply
157 # instead of two squares in the ith_pair() loop
158 #
159 686 ▶ if ($lowbit) {
Branch: 1 branch
BranchTrueFalseTotal
if ($lowbit) { } 356 330 686
160 356 ▶ $F0 = ($F0 + $F1) * (3*$F0 - $F1) + ($pair_i % 2 ? -2 : 2);
Branch: 1 branch
BranchTrueFalseTotal
$pair_i % 2 ? : 193 163 356
161 } else {
162 330 $F0 *= (2*$F1 - $F0);
163 }
164 686 return $F0;
165 }
166  
167 2127 ▶sub ith_pair {
Subroutine ith_pair: called CC=9 SCAR=22.0
Pod documented
168 2127 my ($self, $i) = @_;
169 ### Fibonacci ith_pair(): $i
170  
171 2127 ▶ if (_is_infinite($i)) {
Branch: 1 branch
BranchTrueFalseTotal
if (_is_infinite($i)) 3 2124 2127
172 3 return ($i,$i);
173 }
174  
175 2124 my $neg = ($i < 0);
176 2124 ▶ if ($neg) {
Branch: 1 branch
BranchTrueFalseTotal
if ($neg) 22 2102 2124
177 22 $i = -1-$i;
178 }
179  
180 2124 my @bits = _bit_split_hightolow($i+1);
181 ### @bits
182 2124 shift @bits; # drop high 1-bit
183  
184 # k=1 which is the high bit of @bits
185 # $Fk1 = F[k-1] = 0
186 # $Fk = F[k] = 1
187 #
188 2124 my $Fk1 = ($i * 0); # inherit bignum 0
189 2124 ▶ if ($i >= $uv_i_limit && ! ref $Fk1) {
Branch: 1 branch
BranchTrueFalseTotal
if ($i >= $uv_i_limit and not ref $Fk1) 550 1574 2124
Condition66%2/3
$i >= $uv_i_limit and not ref $Fk1
!ll&&!rl&&r
15740550
MC/DC50%1/2
$i >= $uv_i_limit and not ref $Fk1
$i >= $uv_i_limit not ref $Fk1
Truth table66%2/3
A and not(B)
A= $i >= $uv_i_limitB= not ref $Fk1
ABresult
0X0
100
111
190 # automatic BigInt if not another number class
191 550 $Fk1 = _to_bigint(0);
192 }
193 2124 my $Fk = $Fk1 + 1; # inherit bignum 1
194  
195 2124 my $add = -2; # (-1)^k
196 2124 ▶ while (@bits) {
Branch: 1 branch
BranchTrueFalseTotal
if (@bits) 10522 2124 12646
197 ### remaining bits: @bits
198 ### Fk1: "$Fk1"
199 ### Fk: "$Fk"
200  
201 # two squares and some adds
202 # F[2k+1] = 4*F[k]^2 - F[k-1]^2 + 2*(-1)^k
203 # F[2k-1] = F[k]^2 + F[k-1]^2
204 # F[2k] = F[2k+1] - F[2k-1]
205 #
206 10522 $Fk *= $Fk;
207 10522 $Fk1 *= $Fk1;
208 10522 my $F2kplus1 = 4*$Fk - $Fk1 + $add;
209 10522 $Fk1 += $Fk; # F[2k-1]
210 10522 my $F2k = $F2kplus1 - $Fk1;
211  
212 10522 ▶ if (shift @bits) { # high to low
Branch: 1 branch
BranchTrueFalseTotal
if (shift @bits) { } 4826 5696 10522
213 4826 $Fk1 = $F2k; # F[2k]
214 4826 $Fk = $F2kplus1; # F[2k+1]
215 4826 $add = -2;
216 } else {
217 # $Fk1 is F[2k-1] already
218 5696 $Fk = $F2k; # F[2k]
219 5696 $add = 2;
220 }
221 }
222  
223 2124 ▶ if ($neg) {
Branch: 1 branch
BranchTrueFalseTotal
if ($neg) 22 2102 2124
224 22 ($Fk1,$Fk) = ($Fk, $Fk1);
225 22 ▶ if ($i % 2) {
Branch: 1 branch
BranchTrueFalseTotal
if ($i % 2) { } 9 13 22
226 9 $Fk1 = -$Fk1;
227 } else {
228 13 $Fk = -$Fk;
229 }
230 }
231  
232 ### final ...
233 ### Fk1: "$Fk1"
234 ### Fk: "$Fk"
235 2124 return ($Fk1, $Fk);
236 }
237  
238 2575 ▶sub _bit_split_hightolow {
Subroutine _bit_split_hightolow: called CC=5 SCAR=16.3
239 2575 my ($n) = @_;
240 ### _bit_split_hightolow(): "$n"
241  
242 2575 ▶ if (ref $n) {
Branch: 1 branch
BranchTrueFalseTotal
if (ref $n) 39 2536 2575
243 39 ▶ if ($n->isa('Math::BigInt')
Branch: 1 branch
BranchTrueFalseTotal
if ($n->isa("Math::BigInt") and $n->can("as_bin")) 39 0 39
Condition33%1/3
$n->isa("Math::BigInt") and $n->can("as_bin")
!ll&&!rl&&r
0039
MC/DC0%0/2
$n->isa("Math::BigInt") and $n->can("as_bin")
$n->isa("Math::BigInt") $n->can("as_bin")
Truth table33%1/3
A and B
A= $n->isa("Math::BigInt")B= $n->can("as_bin")
ABresult
0X0
100
111
244 && $n->can('as_bin')) {
245 ### BigInt: $n->as_bin
246 39 return split //, substr($n->as_bin,2);
247 }
248 }
249 2536 my @bits;
250 2536 ▶ while ($n) {
Branch: 1 branch
BranchTrueFalseTotal
if ($n) 14459 2536 16995
251 14459 push @bits, $n % 2;
252 14459 $n = int($n/2);
253 }
254 2536 return reverse @bits;
255 }
256  
257 28 ▶use constant 1.02 _PHI => (1 + sqrt(5)) / 2;
Subroutine BEGIN: called CC=1 SCAR=0.0
258 28 ▶use constant 1.02 _BETA => -1/_PHI;
Subroutine BEGIN: called CC=1 SCAR=0.0
259  
260 40 ▶sub value_to_i_estimate {
Subroutine value_to_i_estimate: called CC=4 SCAR=14.0
Pod documented
261 40 my ($self, $value) = @_;
262 40 ▶ if (_is_infinite($value)) {
Branch: 1 branch
BranchTrueFalseTotal
if (_is_infinite($value)) 0 40 40
263 0 return $value;
264 }
265 40 ▶ if ($value <= 0) {
Branch: 1 branch
BranchTrueFalseTotal
if ($value <= 0) 9 31 40
266 9 return 0;
267 }
268  
269 31 ▶ if (defined (my $blog2 = _blog2_estimate($value))) {
Branch: 1 branch
BranchTrueFalseTotal
if (defined(my $blog2 = _blog2_estimate($value))) 1 30 31
270 # i ~= (log2(F(i)) + log2(phi)) / log2(phi-beta)
271 # with log2(x) = log(x)/log(2)
272 1 return int( ($blog2 + (log(_PHI - _BETA)/log(2)))
273 / (log(_PHI)/log(2)) );
274 }
275  
276 # i ~= (log(F(i)) + log(phi)) / log(phi-beta)
277 30 return int( (log($value) + log(_PHI - _BETA))
278 / log(_PHI) );
279 }
280  
281 0 ▶sub _UNTESTED__value_to_i {
Subroutine _UNTESTED__value_to_i: not called CC=9 SCAR=45.0
282 0 my ($self, $value) = @_;
283 0 ▶ if ($value < 0) { return undef; }
Branch: 1 branch
BranchTrueFalseTotal
if ($value < 0) 0 0 0
284 0 my $i = $self->value_to_i_estimate($value) - 3;
285 0 ▶ if (_is_infinite($i)) { return $i; }
Branch: 1 branch
BranchTrueFalseTotal
if (_is_infinite($i)) 0 0 0
286  
287 0 ▶ if ($i < 0) { $i = 0; }
Branch: 1 branch
BranchTrueFalseTotal
if ($i < 0) 0 0 0
288 0 my ($f0,$f1) = $self->ith_pair($i);
289 0 foreach (1 .. 10) {
290 0 ▶ if ($f0 == $value) {
Branch: 1 branch
BranchTrueFalseTotal
if ($f0 == $value) 0 0 0
291 0 return $i;
292 }
293 0 ▶ last if $f0 > $value;
Branch: 1 branch
BranchTrueFalseTotal
if $f0 > $value 0 0 0
294 0 ▶ if ($i == $uv_i_limit && ! ref $f0) {
Branch: 1 branch
BranchTrueFalseTotal
if ($i == $uv_i_limit and not ref $f0) 0 0 0
Condition0%0/3
$i == $uv_i_limit and not ref $f0
!ll&&!rl&&r
000
MC/DC0%0/2
$i == $uv_i_limit and not ref $f0
$i == $uv_i_limit not ref $f0
Truth table0%0/3
A and not(B)
A= $i == $uv_i_limitB= not ref $f0
ABresult
0X0
100
111
295 # automatic BigInt if not another number class
296 0 $f1 = _to_bigint($f1);
297 }
298 0 ($f0, $f1) = ($f1, $f0+$f1);
299 0 $i += 1;
300 }
301 0 return undef;
302 }
303  
304 #------------------------------------------------------------------------------
305 # generic, shared
306  
307 # if $n is a BigInt, BigRat or BigFloat then return an estimate of log base 2
308 # otherwise return undef.
309 #
310 # For Math::BigInt
311 #
312 # For BigRat the calculation is just a bit count of the numerator less the
313 # denominator so may be off by +/-1 or +/-2 or some such. For
314 #
315 569 ▶sub _blog2_estimate {
Subroutine _blog2_estimate: called CC=5 SCAR=17.3
316 569 my ($n) = @_;
317  
318 569 ▶ if (ref $n) {
Branch: 1 branch
BranchTrueFalseTotal
if (ref $n) 32 537 569
319 ### _blog2_estimate(): "$n"
320  
321 32 ▶ if ($n->isa('Math::BigRat')) {
Branch: 1 branch
BranchTrueFalseTotal
if ($n->isa("Math::BigRat")) 0 32 32
322 0 return ($n->numerator->copy->blog(2) - $n->denominator->copy->blog(2))->numify;
323 }
324 32 ▶ if ($n->isa('Math::BigFloat')) {
Branch: 1 branch
BranchTrueFalseTotal
if ($n->isa("Math::BigFloat")) 0 32 32
325 0 return $n->as_int->blog(2)->numify;
326 }
327 32 ▶ if ($n->isa('Math::BigInt')) {
Branch: 1 branch
BranchTrueFalseTotal
if ($n->isa("Math::BigInt")) 32 0 32
328 32 return $n->copy->blog(2)->numify;
329 }
330 }
331 537 return undef;
332 }
333  
334 28 1;
335 __END__
« NumSeq/ReverseAdd.pm ↑ Summary NumSeq/FractionDigits.pm »