NumSeq/FibonacciWord.pm

filter: Statementstmt 95.9% 95 / 99 Branchbran 80.0% 16 / 20 Conditioncond 85.7% 12 / 14 MC/DCmcdc 71.4% 5 / 7 Subroutinesub 94.7% 18 / 19 Podpod 100% 8 / 8 totaltotal 92.2% 154 / 167 CC 16 SCAR 10.3
CC
16
Cov
92%
values_max
6.0
ith
5.0
pred
4.0
CRAP 2.8
« NumSeq/SqrtContinued.pm ↑ Summary NumSeq/BaumSweet.pm »
1 # Copyright 2010, 2011, 2012, 2013, 2014, 2016, 2019, 2020, 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 package Math::NumSeq::FibonacciWord;
20 2 ▶use 5.004;
Subroutine BEGIN: called CC=1 SCAR=0.0
21 2 ▶use strict;
Subroutine BEGIN: called CC=1 SCAR=0.0
22  
23 2 ▶use vars '$VERSION', '@ISA';
Subroutine BEGIN: called CC=1 SCAR=0.0
24 2 $VERSION = 75;
25  
26 2 ▶use Math::NumSeq;
Subroutine BEGIN: called CC=1 SCAR=0.0
27 2 ▶use Math::NumSeq::Base::IterateIth;
Subroutine BEGIN: called CC=1 SCAR=0.0
28 2 @ISA = ('Math::NumSeq::Base::IterateIth',
29 'Math::NumSeq');
30  
31 2 ▶use Math::NumSeq::Fibbinary;
Subroutine BEGIN: called CC=1 SCAR=0.0
32  
33 # uncomment this to run the ### lines
34 #use Smart::Comments;
35  
36  
37 4 ▶sub description {
Subroutine description: called CC=3 SCAR=11.0
Pod documented
38 4 my ($self) = @_;
39 4 ▶ if (ref $self && $self->{'fibonacci_word_type'} eq 'dense') {
Branch: 1 branch
BranchTrueFalseTotal
if (ref $self and $self->{"fibonacci_word_type"} eq "dense") 1 3 4
Condition100%3/3
ref $self and $self->{"fibonacci_word_type"} eq "dense"
!ll&&!rl&&r
211
MC/DC100%2/2
ref $self and $self->{"fibonacci_word_type"} eq "dense"
ref $self $self->{"fibonacci_word_type"} eq "dense"
Truth table100%3/3
A and B
A= ref $selfB= $self->{"fibonacci_word_type"} eq "dense"
ABresult
0X0
100
111
40 1 return Math::NumSeq::__('0/1/2 dense Fibonacci word taking pairs from the plain word.');
41 }
42 3 return Math::NumSeq::__('0/1 values related to Fibonacci numbers, 0,1,0,0,1,0,1,0,etc.');
43 }
44 2 ▶use constant default_i_start => 0;
Subroutine BEGIN: called CC=1 SCAR=0.0
45 2 ▶use constant characteristic_integer => 1;
Subroutine BEGIN: called CC=1 SCAR=0.0
46 2 ▶use constant characteristic_smaller => 1;
Subroutine BEGIN: called CC=1 SCAR=0.0
47 2 ▶use constant values_min => 0;
Subroutine BEGIN: called CC=1 SCAR=0.0
48 0 ▶sub values_max {
Subroutine values_max: not called CC=2 SCAR=17.9
Pod documented
49 0 my ($self) = @_;
50 0 ▶ return ($self->{'fibonacci_word_type'} eq 'dense' ? 2 : 1);
Branch: 1 branch
BranchTrueFalseTotal
$self->{'fibonacci_word_type'} eq 'dense' ? : 0 0 0
51 }
52  
53 2 ▶use constant parameter_info_array =>
Subroutine BEGIN: called CC=1 SCAR=0.0
54 [
55 { name => 'fibonacci_word_type',
56 display => Math::NumSeq::__('Fibonacci Word Type'),
57 type => 'enum',
58 default => 'plain',
59 choices => ['plain','dense'],
60 choices_display => [Math::NumSeq::__('Plain'),
61 Math::NumSeq::__('Dense'),
62 ],
63 description => Math::NumSeq::__('Which of the pair of values to show.'),
64 },
65 2 ];
66  
67 #------------------------------------------------------------------------------
68  
69 # cf A003842 same with values 1/2 instead of 0/1
70 # A014675 same with values 2/1 instead of 0/1
71 # A001468 values 2/1 instead of 0/1, skip leading 0, self-referential
72 # A005614 inverse 1/0, starting from 1
73 #
74 # A003622 positions of 1s
75 # A000201 positions of 0s
76 # A089910 positions of 1,1 pairs
77 # A114986 characteristic of A000201, with extra 1 ??
78 # A096270 expressed as 01 and 011, is inverse with leading 0
79 # A036299 values 0/1 inverse, bignum concatenating
80 # A008352 values 1/2 inverse, bignum concatenating
81 #
82 # A189479 0->01 1->101
83 # A007066 positions of 0s
84 # A076662 first diffs of positions, values 3/2 with extra leading 3
85 #
86 # A135817 whythoff repres 0s
87 # A135818 whythoff repres 1s
88 # A189921 whythoff form
89 # A135817 whythoff length A+B
90 #
91  
92 # A003849 OFFSET=0 values 0,1, 0,0, 1,0, 1,0, etc
93 # A143667 OFFSET=1 values 1,0,2,2,etc
94 #
95 2 my %oeis_anum
96 = (
97 # OEIS-Catalogue array begin
98 plain => 'A003849', #
99 'dense,i_start=1,i_offset=-1' => 'A143667', # fibonacci_word_type=dense i_start=1 i_offset=-1
100 # OEIS-Catalogue array end
101 );
102 2 ▶sub oeis_anum {
Subroutine oeis_anum: called CC=3 SCAR=12.0
Pod documented
103 2 my ($self) = @_;
104 2 my $key = $self->{'fibonacci_word_type'};
105 2 my $i_start = $self->i_start;
106 2 ▶ if ($i_start != $self->default_i_start) {
Branch: 1 branch
BranchTrueFalseTotal
if ($i_start != $self->default_i_start) 0 2 2
107 0 $key .= ",i_start=$i_start";
108 }
109 2 ▶ if ($self->{'i_offset'}) {
Branch: 1 branch
BranchTrueFalseTotal
if ($self->{"i_offset"}) 0 2 2
110 0 $key .= ",i_offset=$self->{'i_offset'}";
111 }
112 2 return $oeis_anum{$key};
113 }
114  
115 #------------------------------------------------------------------------------
116 # i_offset is a hack to number A143667 starting OFFSET=1, whereas otherwise
117 # here start i=0
118 #
119 # $self->{'i'} is the next $i to return from next()
120 #
121 # $self->{'value'} is Fibbinary->ith($self->{'i'}), or for "dense" is
122 # Fibbinary->ith(2 * $self->{'i'}). $self->{'value'} is incremented by the
123 # same bit-twiddling as in Fibbinary. The low bit of $self->{'value'} is
124 # the FibonacciWord $value. Or for "dense" the low bit of two successive
125 # values combined.
126 #
127  
128 11 ▶sub rewind {
Subroutine rewind: called CC=2 SCAR=7.0
Pod documented
129 11 my ($self) = @_;
130 11 $self->{'i'} = $self->i_start;
131 11 $self->{'value'} = 0;
132 11 ▶ $self->{'i_offset'} ||= 0;
Condition50%1/2
$self->{"i_offset"} ||= 0
l!l
011
MC/DC0%0/1
$self->{"i_offset"} ||= 0
$self->{"i_offset"}
Truth table50%1/2
A
A= $self->{"i_offset"}
Aresult
11
00
133 }
134 27 ▶sub seek_to_i {
Subroutine seek_to_i: called CC=2 SCAR=6.9
Pod documented
135 27 my ($self, $i) = @_;
136 27 $self->{'i'} = $i;
137 27 ▶ if ($self->{'fibonacci_word_type'} eq 'dense') {
Branch: 1 branch
BranchTrueFalseTotal
if ($self->{'fibonacci_word_type'} eq 'dense') { } 14 13 27
138 14 $self->{'value'} = Math::NumSeq::Fibbinary->ith(2*$i);
139 } else {
140 13 $self->{'value'} = Math::NumSeq::Fibbinary->ith($i);
141 }
142 }
143 751 ▶sub next {
Subroutine next: called CC=2 SCAR=6.9
Pod documented
144 751 my ($self) = @_;
145 ### FibonacciWord next() ...
146  
147 751 ▶ if ($self->{'fibonacci_word_type'} eq 'dense') {
Branch: 1 branch
BranchTrueFalseTotal
if ($self->{'fibonacci_word_type'} eq 'dense') { } 133 618 751
148 133 my $v = $self->{'value'};
149 133 my $high = ($v & 1) << 1;
150  
151 133 my $filled = ($v >> 1) | $v;
152 133 my $mask = (($filled+1) ^ $filled) >> 1;
153 133 $v = ($v | $mask) + 1;
154  
155 133 $filled = ($v >> 1) | $v;
156 133 $mask = (($filled+1) ^ $filled) >> 1;
157 133 $self->{'value'} = ($v | $mask) + 1;
158  
159 133 return ($self->{'i'}++, $high | ($v & 1));
160  
161 } else {
162 618 my $v = $self->{'value'};
163 618 my $filled = ($v >> 1) | $v;
164 618 my $mask = (($filled+1) ^ $filled) >> 1;
165 618 $self->{'value'} = ($v | $mask) + 1;
166  
167 ### value : sprintf('0b %6b',$v)
168 ### filled: sprintf('0b %6b',$filled)
169 ### mask : sprintf('0b %6b',$mask)
170 ### bit : sprintf('0b %6b',$mask+1)
171 ### newv : sprintf('0b %6b',$self->{'value'})
172  
173 618 return ($self->{'i'}++, $v & 1);
174 }
175 }
176  
177 596 ▶sub ith {
Subroutine ith: called CC=5 SCAR=16.1
Pod documented
178 596 my ($self, $i) = @_;
179 ### FibonacciWord ith(): $i
180  
181 596 $i = $i + $self->{'i_offset'};
182  
183 # if $i is inf or nan then $f0=$i*0 is nan and the do-while loop
184 # zero-trips and return is nan
185
186 596 my $zero = ($i * 0); # 0, or nan if i inf or nan
187 596 $i += $zero; # nan if $i was inf
188 596 my $f0 = $zero + 1; # inherit bignum 1
189 596 my $f1 = $f0 + 1; # inherit bignum 2
190 596 my $level = 0;
191 ### start: "$f1,$f0 level=$level"
192  
193 # f1+f0 > i
194 # f0 > i-f1
195 # check i-f1 as the stopping point, so that if i=UV_MAX then won't
196 # overflow a UV trying to get to f1>=i
197 #
198 596 ▶ while ($f0 <= $i-$f1) {
Branch: 1 branch
BranchTrueFalseTotal
if ($f0 <= $i - $f1) 4868 596 5464
199 4868 ($f1,$f0) = ($f1+$f0,$f1);
200 4868 $level++;
201 }
202 ### above: "$f1,$f0 level=$level"
203  
204 596 ▶ if ($self->{'fibonacci_word_type'} eq 'dense') {
Branch: 1 branch
BranchTrueFalseTotal
if ($self->{'fibonacci_word_type'} eq 'dense') { } 48 548 596
205 48 my $v = Math::NumSeq::Fibbinary->ith(2*$i);
206 48 my $high = ($v & 1) << 1;
207  
208 48 my $filled = ($v >> 1) | $v;
209 48 my $mask = (($filled+1) ^ $filled) >> 1;
210 48 $v = ($v | $mask) + 1;
211  
212 48 return ($high | ($v & 1));
213  
214 } else {
215  
216 548 ▶ do {
Branch: 1 branch
BranchTrueFalseTotal
$level-- and do { do { if ($i >= $f1) { $i -= $f1; } ; ($f1, $f0) = ($f0, $f1 - $f0) } } 4783 548 5331
217 ### at: "$f1,$f0 i=$i"
218 5331 ▶ if ($i >= $f1) {
Branch: 1 branch
BranchTrueFalseTotal
if ($i >= $f1) 1681 3650 5331
219 1681 $i -= $f1;
220 }
221 5331 ($f1,$f0) = ($f0,$f1-$f0);
222 } while ($level--);
223  
224 ### assert: $i == 0 || $i == 1
225 ### ret: $i
226 548 return $i;
227 }
228 }
229  
230 33 ▶sub pred {
Subroutine pred: called CC=4 SCAR=13.9
Pod documented
231 33 my ($self, $value) = @_;
232 return ($value == 0 || $value == 1
233 33 ▶ || ($self->{'fibonacci_word_type'} eq 'dense'
Condition88%8/9
$value == 0 || $value == 1 || $self->{'fibonacci_word_type'} eq 'dense' && $value == 2
l!l&&r!l&&!r
2553
$value == 0 or $value == 1
l!l&&r!l&&!r
13128
$self->{"fibonacci_word_type"} eq "dense" and $value == 2
!ll&&!rl&&r
305
MC/DC75%3/4
$value == 0 || $value == 1 || $self->{'fibonacci_word_type'} eq 'dense' && $value == 2
$value == 0 $value == 1 $self->{"fibonacci_word_type"} eq "dense" $value == 2
Truth table80%4/5
A or B || C and D
A= $value == 0B= $value == 1C= $self->{"fibonacci_word_type"} eq "dense"D= $value == 2
ABCDresult
1XXX1
01XX1
00111
000X0
00100
234 && $value == 2));
235 }
236  
237 2 1;
238 __END__
« NumSeq/SqrtContinued.pm ↑ Summary NumSeq/BaumSweet.pm »