NumSeq/Fibbinary.pm

filter: Statementstmt 97.8% 138 / 141 Branchbran 92.1% 35 / 38 Conditioncond 75.0% 6 / 8 MC/DCmcdc 60.0% 3 / 5 Subroutinesub 100% 25 / 25 Podpod 100% 11 / 11 totaltotal 95.6% 218 / 228 CC 25 SCAR 13.5
CC
25
Cov
96%
_value_to_i_and_floor
9.0
ith
6.0
pred
5.0
CRAP 3.9
« NumSeq/NumAronson.pm ↑ Summary NumSeq/ConcatNumbers.pm »
1 # Copyright 2011, 2012, 2013, 2014, 2015, 2016, 2019, 2020, 2021, 2022 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  
19 # ZOrderCurve, ImaginaryBase tree shape
20 # DragonCurve repeating runs
21 #
22 # cf fxtbook ch38 p756
23 #
24 # cf visualizing
25 # http://cs-people.bu.edu/ilir/zecko/
26  
27  
28 package Math::NumSeq::Fibbinary;
29 4 ▶use 5.004;
Subroutine BEGIN: called CC=1 SCAR=0.0
30 4 ▶use strict;
Subroutine BEGIN: called CC=1 SCAR=0.0
31 4 ▶use Carp;
Subroutine BEGIN: called CC=1 SCAR=0.0
32  
33 4 ▶use vars '$VERSION', '@ISA';
Subroutine BEGIN: called CC=1 SCAR=0.0
34 4 $VERSION = 75;
35 4 ▶use Math::NumSeq;
Subroutine BEGIN: called CC=1 SCAR=0.0
36 4 @ISA = ('Math::NumSeq');
37 4 *_is_infinite = \&Math::NumSeq::_is_infinite;
38 4 *_to_bigint = \&Math::NumSeq::_to_bigint;
39  
40 4 ▶use Math::NumSeq::Fibonacci;
Subroutine BEGIN: called CC=1 SCAR=0.0
41 4 *_bit_split_hightolow = \&Math::NumSeq::Fibonacci::_bit_split_hightolow;
42 4 *_blog2_estimate = \&Math::NumSeq::Fibonacci::_blog2_estimate;
43  
44 # uncomment this to run the ### lines
45 # use Smart::Comments;
46  
47  
48 # use constant name => Math::NumSeq::__('Fibbinary Numbers');
49 4 ▶use constant description => Math::NumSeq::__('Fibbinary numbers 0,1,2,4,5,8,9,etc, integers without adjacent 1-bits.');
Subroutine BEGIN: called CC=1 SCAR=0.0
50 4 ▶use constant default_i_start => 0;
Subroutine BEGIN: called CC=1 SCAR=0.0
51 4 ▶use constant characteristic_increasing => 1;
Subroutine BEGIN: called CC=1 SCAR=0.0
52 4 ▶use constant characteristic_integer => 1;
Subroutine BEGIN: called CC=1 SCAR=0.0
53  
54 1 ▶sub values_min {
Subroutine values_min: called CC=1 SCAR=0.0
Pod documented
55 1 my ($self) = @_;
56 1 return $self->ith($self->i_start);
57 }
58  
59 #------------------------------------------------------------------------------
60 # cf A000119 - number of Fibonacci sums forms
61 # A003622 - n with odd Zeckendorf, cf golden seq
62 # A037011 - baum-sweet cubic, might be 1 iff i is in the fibbinary seq
63 # A014417 - n in Fibonacci base, the fibbinaries written out in binary
64 # A139764 - smallest Zeckendorf term
65 # A054204 - using only even Fibs
66 #
67 4 ▶use constant oeis_anum => 'A003714'; # Fibbinary, OFFSET=0 start value=0
Subroutine BEGIN: called CC=1 SCAR=0.0
68  
69 #------------------------------------------------------------------------------
70 # $self->{'i'}, $self->{'value'} are the next $i,$value to return.
71 # next() increments 'i' and steps 'value'.
72 # So the next value is calculated ahead of its actually being needed,
73 # but doing so
74  
75 10 ▶sub rewind {
Subroutine rewind: called CC=1 SCAR=0.0
Pod documented
76 10 my ($self) = @_;
77 10 $self->{'i'} = $self->i_start;
78 10 $self->{'value'} = 0;
79 }
80 41 ▶sub seek_to_i {
Subroutine seek_to_i: called CC=2 SCAR=7.4
Pod documented
81 41 my ($self, $i) = @_;
82 41 ▶ if ($i < 0) {
Branch: 1 branch
BranchTrueFalseTotal
if ($i < 0) 0 41 41
83 0 croak "Cannot seek to ",$i,", sequence begins at i=0";
84 }
85 41 $self->{'i'} = $i;
86 41 $self->{'value'} = $self->ith($i);
87 }
88 14 ▶sub seek_to_value {
Subroutine seek_to_value: called CC=1 SCAR=0.0
Pod documented
89 14 my ($self, $value) = @_;
90 14 $self->seek_to_i($self->value_to_i_ceil($value));
91 }
92  
93 712 ▶sub next {
Subroutine next: called CC=1 SCAR=0.0
Pod documented
94 712 my ($self) = @_;
95 ### Fibbinary next() ...
96  
97 712 my $v = $self->{'value'};
98 712 $self->{'value'} = _value_next($self,$v);
99 712 return ($self->{'i'}++, $v);
100 }
101  
102 712 ▶sub _value_next {
Subroutine _value_next: called CC=1 SCAR=0.0
103 712 my ($self, $value) = @_;
104 712 my $filled = ($value >> 1) | $value;
105 712 my $mask = (($filled+1) ^ $filled) >> 1;
106  
107 ### value : sprintf('0b %6b',$value)
108 ### filled: sprintf('0b %6b',$filled)
109 ### mask : sprintf('0b %6b',$mask)
110 ### bit : sprintf('0b %6b',$mask+1)
111 ### newv : sprintf('0b %6b',($value | $mask))
112  
113 712 return ($value | $mask) + 1;
114 }
115  
116 1544 ▶sub ith {
Subroutine ith: called CC=6 SCAR=17.9
Pod documented
117 1544 my ($self, $i) = @_;
118 ### Fibbinary ith(): $i
119  
120 1544 ▶ if (_is_infinite($i)) {
Branch: 1 branch
BranchTrueFalseTotal
if (_is_infinite($i)) 3 1541 1544
121 3 return $i;
122 }
123  
124 # f1+f0 > i
125 # f0 > i-f1
126 # check i-f1 as the stopping point, so that if i=UV_MAX then won't
127 # overflow a UV trying to get to f1>=i
128 #
129 1541 my @fibs;
130 {
131 1541 my $f0 = ($i * 0); # inherit bignum 0
132 1541 my $f1 = $f0 + 1; # inherit bignum 1
133 1541 @fibs = ($f0);
134 1541 ▶ while ($f0 <= $i-$f1) {
Branch: 1 branch
BranchTrueFalseTotal
if ($f0 <= $i - $f1) 16606 1541 18147
135 16606 ($f1,$f0) = ($f1+$f0,$f1);
136 16606 push @fibs, $f1;
137 }
138 }
139 ### @fibs
140  
141 1541 my $value = 0;
142 1541 ▶ while (my $f = pop @fibs) {
Branch: 1 branch
BranchTrueFalseTotal
if (my $f = pop @fibs) 11825 958 12783
143 ### at: "$f i=$i value=$value"
144 11825 $value *= 2;
145 11825 ▶ if ($i >= $f) {
Branch: 1 branch
BranchTrueFalseTotal
if ($i >= $f) 5364 6461 11825
146 5364 $value += 1;
147 5364 $i -= $f;
148 ### sub: "$f to i=$i value=$value"
149  
150 # never consecutive fibs, so pop without comparing to i
151 5364 ▶ pop @fibs || last;
Branch: 1 branch
BranchTrueFalseTotal
pop @fibs or last 4781 583 5364
152 4781 $value *= 2;
153 }
154 }
155 1541 return $value;
156 }
157  
158 85 ▶sub pred {
Subroutine pred: called CC=5 SCAR=16.2
Pod documented
159 85 my ($self, $value) = @_;
160 ### Fibbinary pred(): $value
161  
162 85 my $int;
163 85 ▶ unless ($value >= 0
Branch: 1 branch
BranchTrueFalseTotal
unless ($value >= 0 and $value == ($int = int $value)) 32 53 85
Condition66%2/3
$value >= 0 and $value == ($int = int $value)
!ll&&!rl&&r
03253
MC/DC50%1/2
$value >= 0 and $value == ($int = int $value)
$value >= 0 $value == ($int = int $value)
Truth table66%2/3
A and B
A= $value >= 0B= $value == ($int = int $value)
ABresult
0X0
100
111
164 && $value == ($int = int($value))) {
165 32 return 0;
166 }
167  
168 # go to BigInt if NV floating point integer bigger than UV, since "&"
169 # operator will cast to a UV and lose bits
170 53 ▶ if ($int > ~0 && ! ref $int) {
Branch: 1 branch
BranchTrueFalseTotal
if ($int > '18446744073709551615' and not ref $int) 1 52 53
Condition66%2/3
$int > '18446744073709551615' and not ref $int
!ll&&!rl&&r
5201
MC/DC50%1/2
$int > '18446744073709551615' and not ref $int
$int > '18446744073709551615' not ref $int
Truth table66%2/3
A and not(B)
A= $int > '18446744073709551615'B= not ref $int
ABresult
0X0
100
111
171 1 $int = _to_bigint(sprintf('%.0f',$int));
172 ### use BigInt: $int
173 ### str: sprintf('%.0f',$int)
174 }
175  
176 ### and: ($int & ($int >> 1)).''
177 53 return ! ($int & ($int >> 1));
178 }
179  
180 #------------------------------------------------------------------------------
181  
182 219 ▶sub value_to_i_floor {
Subroutine value_to_i_floor: called CC=2 SCAR=6.9
Pod documented
183 219 my ($self, $value) = @_;
184 ### Fibbinary value_to_i_floor(): $value
185 219 ▶ if ($value < 0) { return 0; }
Branch: 1 branch
BranchTrueFalseTotal
if ($value < 0) 5 214 219
186 214 my ($i) = _value_to_i_and_floor($value);
187 214 return $i;
188 }
189 64 ▶sub value_to_i_ceil {
Subroutine value_to_i_ceil: called CC=2 SCAR=7.4
Pod documented
190 64 my ($self, $value) = @_;
191 ### Fibbinary value_to_i_ceil(): $value
192 0 ▶ if ($value < 0) { return 0; }
Branch: 1 branch
BranchTrueFalseTotal
if ($value < 0) 0 64 64
193 64 my ($i,$floor) = _value_to_i_and_floor($value);
194 64 return $i + $floor;
195 }
196 49 ▶sub value_to_i {
Subroutine value_to_i: called CC=3 SCAR=11.0
Pod documented
197 49 my ($self, $value) = @_;
198 ### Fibbinary value_to_i(): $value
199 49 ▶ if ($value < 0) { return undef; }
Branch: 1 branch
BranchTrueFalseTotal
if ($value < 0) 4 45 49
200 45 my ($i,$floor) = _value_to_i_and_floor($value);
201 45 ▶ return ($floor ? undef : $i);
Branch: 1 branch
BranchTrueFalseTotal
$floor ? : 17 28 45
202 }
203  
204 # return ($i, $floor)
205 323 ▶sub _value_to_i_and_floor {
Subroutine _value_to_i_and_floor: called CC=9 SCAR=22.0
206 323 my ($value) = @_;
207  
208 323 ▶ if (_is_infinite($value)) {
Branch: 1 branch
BranchTrueFalseTotal
if (_is_infinite($value)) 0 323 323
209 0 return ($value,
210 0); # reckon infinite as not rounded
211 }
212  
213 323 my $floor;
214 {
215 323 my $int = int($value);
216 323 ▶ $floor = ($value == $int ? 0 : 1);
Branch: 1 branch
BranchTrueFalseTotal
$value == $int ? : 294 29 323
217 323 ▶ $value = $int
Condition100%2/2
$int || (return 0, $floor)
l!l
31112
MC/DC100%1/1
$int || (return 0, $floor)
$int
Truth table100%2/2
A
A= $int
Aresult
11
00
218 || return (0, $floor); # i=0 not handled below
219 }
220  
221 311 my @bits = _bit_split_hightolow($value);
222 311 my @fibs;
223 {
224 311 my $f0 = ($value * 0); # inherit bignum 0
225 311 my $f1 = $f0 + 1; # inherit bignum 1
226 311 foreach (@bits) {
227 1652 ($f1,$f0) = ($f1+$f0,$f1);
228 1652 push @fibs, $f1;
229 }
230 }
231 ### @fibs
232  
233 311 my $prev_bit = shift @bits; # high 1-bit
234 311 my $i = pop @fibs;
235  
236 ### initial i: $i
237  
238 311 foreach my $bit (@bits) { # high to low
239 965 my $fib = pop @fibs;
240 ### $bit
241 ### $fib
242  
243 965 ▶ if ($bit) {
Branch: 1 branch
BranchTrueFalseTotal
if ($bit) 355 610 965
244 355 ▶ if ($prev_bit) {
Branch: 1 branch
BranchTrueFalseTotal
if ($prev_bit) 146 209 355
245 ### consecutive bits 11xxx, round down to 10xxx with xxx=1010 ...
246 146 ▶ while (@fibs) {
Branch: 1 branch
BranchTrueFalseTotal
if (@fibs) 230 146 376
247 230 $i += pop @fibs;
248 230 pop @fibs;
249 }
250 146 return ($i,
251 1); # rounded down
252 }
253 209 $i += $fib;
254 ### add i to: $i
255 }
256 819 $prev_bit = $bit;
257 }
258 ### exact i: "$i"
259 165 return ($i,
260 $floor); # not rounded, unless $value was fractional
261 }
262  
263 #------------------------------------------------------------------------------
264 # value_to_i_estimate()
265  
266 4 ▶use constant 1.02 _PHI => (1 + sqrt(5)) / 2;
Subroutine BEGIN: called CC=1 SCAR=0.0
267  
268 # (phi-beta) = phi+1/phi = 2phi-1
269 #
270 # value=2^k
271 # log(value) = k*log(2)
272 # k = log(value)/log(2)
273 # i = F(k)
274 # = phi^(k+1) / (phi-beta)
275 # = phi^k * C where C=phi/(phi-beta) ~= 0.72
276 # log(i/C) = k*log(phi)
277 # k = log(i/C)/log(phi)
278 #
279 # log(i/C)/log(phi) = log(value)/log(2)
280 # log(i/C) = log(value) * log(phi)/log(2)
281 # i/C = e^ (log(value) * log(phi)/log(2))
282 # i/C = (e^log(value)) ^ (log(phi)/log(2)))
283 # i = C * value ^ (log(phi)/log(2)))
284 #
285 # log(phi)/log(2) ~= 0.694
286 #
287  
288 23 ▶sub value_to_i_estimate {
Subroutine value_to_i_estimate: called CC=3 SCAR=11.0
Pod documented
289 23 my ($self, $value) = @_;
290  
291 23 ▶ if ($value <= 0) {
Branch: 1 branch
BranchTrueFalseTotal
if ($value <= 0) 8 15 23
292 8 return 0;
293 }
294  
295 15 $value = int($value);
296 15 ▶ if (my $blog2 = Math::NumSeq::Fibonacci::_blog2_estimate($value)) {
Branch: 1 branch
BranchTrueFalseTotal
if (my $blog2 = Math::NumSeq::Fibonacci::_blog2_estimate($value)) 1 14 15
297 1 my $shift = int ((1 - log(_PHI)/log(2))
298 * Math::NumSeq::Fibonacci::_blog2_estimate($value));
299 1 return $value >> $shift;
300 }
301  
302 14 return int ((((_PHI + 1/_PHI)/_PHI))
303 * $value ** (log(_PHI)/log(2)));
304 }
305  
306 # Can get close taking bits low to high and tweaking for consecutive 1s.
307 # But the high to low of the full value_to_i_floor() is only a little extra
308 # work.
309 #
310 # sub value_to_i_estimate {
311 # my ($self, $value) = @_;
312 # ### Fibbinary value_to_i_estimate(): $value
313 #
314 # if (_is_infinite($value)) {
315 # return $value;
316 # }
317 #
318 # my $f0 = my $f1 = ($value * 0)+1; # inherit bignum 1
319 # my $i = 0;
320 #
321 # my $prev_bit = 0;
322 # while ($value) {
323 # my $bit = $value % 2;
324 # if ($bit) {
325 # if ($prev_bit) {
326 # $i += $f0;
327 # } else {
328 # $i += $f1;
329 # }
330 # }
331 # $prev_bit = $bit;
332 # ($f1,$f0) = ($f1+$f0,$f1);
333 # $value = int($value/2);
334 # }
335 # return $i;
336 # }
337  
338 4 1;
339 __END__
« NumSeq/NumAronson.pm ↑ Summary NumSeq/ConcatNumbers.pm »