NumSeq/BalancedBinary.pm

filter: Statementstmt 95.7% 226 / 236 Branchbran 83.7% 62 / 74 Conditioncond 76.9% 20 / 26 MC/DCmcdc 60.0% 9 / 15 Subroutinesub 100% 26 / 26 Podpod 100% 10 / 10 totaltotal 91.2% 353 / 387 CC 59 SCAR 21.8
CC
59
Cov
92%
_value_to_i_round
16.1
ith
14.1
value_to_i
13.2
CRAP 8.8
« NumSeq/HafermanCarpet.pm ↑ Summary NumSeq/UndulatingNumbers.pm »
1 # Copyright 2012, 2013, 2014, 2016, 2018, 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  
19 # http://www.iki.fi/~kartturi/matikka/tab9766.htm
20 # A009766 Catalan triangle
21 # A099039 Riordan array
22  
23 package Math::NumSeq::BalancedBinary;
24 2 ▶use 5.004;
Subroutine BEGIN: called CC=1 SCAR=0.0
25 2 ▶use strict;
Subroutine BEGIN: called CC=1 SCAR=0.0
26 2 ▶use List::Util 'max';
Subroutine BEGIN: called CC=1 SCAR=0.0
27  
28 2 ▶use vars '$VERSION', '@ISA';
Subroutine BEGIN: called CC=1 SCAR=0.0
29 2 $VERSION = 75;
30  
31 2 ▶use Math::NumSeq;
Subroutine BEGIN: called CC=1 SCAR=0.0
32 2 @ISA = ('Math::NumSeq');
33 2 *_is_infinite = \&Math::NumSeq::_is_infinite;
34 2 *_to_bigint = \&Math::NumSeq::_to_bigint;
35  
36 2 ▶use Math::NumSeq::Repdigits;
Subroutine BEGIN: called CC=1 SCAR=0.0
37 2 *_digit_split_lowtohigh = \&Math::NumSeq::Repdigits::_digit_split_lowtohigh;
38  
39 2 ▶use Math::NumSeq::Fibonacci;
Subroutine BEGIN: called CC=1 SCAR=0.0
40 2 *_blog2_estimate = \&Math::NumSeq::Fibonacci::_blog2_estimate;
41  
42 # uncomment this to run the ### lines
43 # use Smart::Comments;
44  
45  
46 # use constant name => Math::NumSeq::__('Balanced Binary');
47 2 ▶use constant description => Math::NumSeq::__('Bits 1,0 balanced like parentheses.');
Subroutine BEGIN: called CC=1 SCAR=0.0
48 2 ▶use constant characteristic_increasing => 1;
Subroutine BEGIN: called CC=1 SCAR=0.0
49 2 ▶use constant characteristic_integer => 1;
Subroutine BEGIN: called CC=1 SCAR=0.0
50 2 ▶use constant default_i_start => 1;
Subroutine BEGIN: called CC=1 SCAR=0.0
51 2 ▶use constant values_min => 2;
Subroutine BEGIN: called CC=1 SCAR=0.0
52  
53 # pred() works, next() doesn't.
54 # Any merit in bit-reversed form ?
55 #
56 # use constant parameter_info_array =>
57 # [ { name => 'direction',
58 # share_key => 'pairs_fsb',
59 # display => Math::NumSeq::__('Direction'),
60 # type => 'enum',
61 # default => 'HtoL',
62 # choices => ['HtoL','LtoH'],
63 # choices_display => [Math::NumSeq::__('HtoL'),
64 # Math::NumSeq::__('LtoH'),
65 # ],
66 # },
67 # ];
68  
69 5 ▶sub new {
Subroutine new: called CC=2 SCAR=7.1
Pod documented
70 5 my $self = shift->SUPER::new(@_);
71 5 ▶ $self->{'direction'} ||= 'HtoL';
Condition50%1/2
$self->{"direction"} ||= "HtoL"
l!l
05
MC/DC0%0/1
$self->{"direction"} ||= "HtoL"
$self->{"direction"}
Truth table50%1/2
A
A= $self->{"direction"}
Aresult
11
00
72 5 return $self;
73 }
74  
75 #------------------------------------------------------------------------------
76 # A063171 in binary
77 # A080116 predicate 0,1
78 # A080300 inverse, ranking value->i or 0
79 # A080237 num trailing zeros
80 # A085192 first diffs
81 # A000108 Catalan numbers, count of values in 4^k blocks
82 # A071152 balanced 2*binary, Lukasiewicz words for the rooted plane binary trees
83 # A075171 trees by binary runs in integers, coded to Dyck words
84 # A071153 Lukasiewicz coded digits
85 #
86 2 my %oeis_anum = (HtoL => 'A014486', # balanced binary
87 # OEIS-Catalogue: A014486
88  
89 LtoH => undef,
90 );
91 1 ▶sub oeis_anum {
Subroutine oeis_anum: called CC=1 SCAR=0.0
Pod documented
92 1 my ($self) = @_;
93 1 return $oeis_anum{$self->{'direction'}};
94 }
95  
96  
97 #------------------------------------------------------------------------------
98  
99 # When $self->{'wantlen'} becomes equal to _WANTLEN_TO_BIGINT then go to
100 # Math::BigInt since the bits of a UV would be overflowed.
101 #
102 # _WANTLEN_TO_BIGINT is floor(numbits(UV)/2), but calculated by a probe of
103 # "~0".
104 #
105 # On a 32-bit UV balance binary value=0xFFFF0000 is reached at i=48_760_366
106 # which is fairly big but might be reached by a long running loop. On a
107 # 64-bit UV the corresponding limit is i=75*10^15 so would not be reached in
108 # any reasonable time.
109 #
110 2 ▶use constant 1.02 _WANTLEN_TO_BIGINT => do {
Subroutine BEGIN: called CC=2 SCAR=6.9
111 2 my $uv = ~0;
112 2 my $limit = 0;
113 2 ▶ while ($uv >= 3) {
Branch: 1 branch
BranchTrueFalseTotal
if ($uv >= 3) 64 2 66
114 64 $uv >>= 2;
115 64 $limit++;
116 }
117 ### $limit
118 $limit
119 2 };
120  
121 7 ▶sub rewind {
Subroutine rewind: called CC=1 SCAR=0.0
Pod documented
122 7 my ($self) = @_;
123 7 $self->{'wantlen'} = 0;
124 7 $self->{'bits'} = [];
125 7 $self->{'value'} = 0;
126 7 $self->{'i'} = $self->i_start;
127 }
128  
129 133 ▶sub next {
Subroutine next: called CC=6 SCAR=17.9
Pod documented
130 133 my ($self) = @_;
131 ### BalancedBinary next() ...
132 133 my $bits = $self->{'bits'};
133 133 my $value;
134  
135 133 ▶ if (! @$bits) {
Branch: 1 branch
BranchTrueFalseTotal
if (not @$bits) { } 5 128 133
136 ### initial 2 ...
137 5 push @$bits, 2;
138 5 $value = 2;
139  
140 } else {
141 128 $value = $self->{'value'};
142 128 for (;;) {
143 ### at: "bits=".join(',',@{$self->{'bits'}})
144 194 ▶ if (scalar(@$bits) < 2) {
Branch: 1 branch
BranchTrueFalseTotal
if (scalar @$bits < 2) 17 177 194
145 ### extend to wantlen: $self->{'wantlen'}+1
146 17 $value = ($bits->[0] *= 4);
147 17 ▶ if (++$self->{'wantlen'} == _WANTLEN_TO_BIGINT) {
Branch: 1 branch
BranchTrueFalseTotal
if (++$self->{"wantlen"} == 32) 0 17 17
148 ### promote to BigInt from now on ...
149 0 $bits->[0] = $value = _to_bigint($value);
150 }
151 17 last;
152 }
153  
154 177 $value -= $bits->[-1];
155 177 my $bit = ($bits->[-1] *= 2);
156 177 ▶ if ($bit < $bits->[-2]) {
Branch: 1 branch
BranchTrueFalseTotal
if ($bit < $bits->[-2]) 111 66 177
157 ### shifted bit ...
158 111 $value += $bit;
159 111 last;
160 }
161 ### drop this bit ...
162 66 pop @$bits;
163 }
164  
165 ### pad for: "value=$value bits=".join(',',@$bits)
166 # trailing bits ...,128, 32, 8, 2
167 128 my $bit = 2 + ($bits->[0]&1); # inherit BigInt
168 128 foreach my $pos (reverse scalar(@$bits) .. $self->{'wantlen'}) {
169 ### pad with: $bit
170 83 $bits->[$pos] = $bit;
171 83 $value += $bit;
172 83 $bit *= 4;
173 }
174 }
175  
176 ### return: "value=$value bits=".join(',',@$bits)
177 return ($self->{'i'}++,
178 133 $self->{'value'} = $value);
179 }
180  
181 36 ▶sub ith {
Subroutine ith: called CC=13 SCAR=26.5
Pod documented
182 36 my ($self, $i) = @_;
183 ### BalancedBinary ith(): $i
184  
185 36 ▶ if ($i < 1) {
Branch: 1 branch
BranchTrueFalseTotal
if ($i < 1) 4 32 36
186 4 return undef;
187 }
188 32 ▶ if (_is_infinite($i)) {
Branch: 1 branch
BranchTrueFalseTotal
if (_is_infinite($i)) 0 32 32
189 0 return $i;
190 }
191  
192 32 $i -= 1;
193 ### initial i remainder: $i
194  
195 32 my $zero = ($i*0); # inherit BigInt
196  
197 32 my @num;
198 32 $num[0][0] = 0;
199 32 $num[1][0] = 1;
200 32 $num[1][1] = 1;
201 32 my $z = 1;
202  
203 32 for ( ; ; $z++) {
204 97 my $prev = $num[$z][0] = 1; # all zeros, no ones
205 97 ▶ if ($z == 16) {
Branch: 1 branch
BranchTrueFalseTotal
if ($z == 16) 0 97 97
206 0 $prev += $zero;
207 0 ▶ if (! ref $zero) {
Branch: 1 branch
BranchTrueFalseTotal
unless (ref $zero) 0 0 0
208 ### promote to BigInt ...
209 0 $zero = _to_bigint($zero);
210 }
211 }
212 97 foreach my $o (1 .. $z) {
213 211 ▶ $num[$z][$o]
Condition100%2/2
$num[$z - 1][$o] || 0
l!l
11497
MC/DC100%1/1
$num[$z - 1][$o] || 0
$num[$z - 1][$o]
Truth table100%2/2
A
A= $num[$z - 1][$o]
Aresult
11
00
214 = ($prev # 1... $num[$z][$o-1]
215 += ($num[$z-1][$o] || 0)); # 0... if $z>=1
216 }
217 97 my $catalan = $num[$z][$z];
218 97 ▶ if ($i < $catalan) {
Branch: 1 branch
BranchTrueFalseTotal
if ($i < $catalan) 32 65 97
219 32 last;
220 }
221 ### subtract catalan: $catalan
222 65 $i -= $catalan;
223 }
224  
225 ### i remaining: $i
226 32 my @ret = (1);
227 32 my $o = $z-1;
228 32 ▶ while ($o >= 1) {
Branch: 1 branch
BranchTrueFalseTotal
if ($o >= 1) 110 32 142
229 ### at: "i=$i z=$z o=$o ret=".join('',@ret)
230 ### assert: $z >= $o
231  
232 110 ▶ if ($z > $o) {
Branch: 1 branch
BranchTrueFalseTotal
if ($z > $o) 75 35 110
233 ### compare: "z=".($z-1).",o=$o num=".($num[$z-1][$o]||'undef')
234 75 my $znum = $num[$z-1][$o];
235 75 ▶ if ($i < $znum) {
Branch: 1 branch
BranchTrueFalseTotal
if ($i < $znum) 45 30 75
236 ### 0 ...
237 45 push @ret, 0;
238 45 $z--;
239 45 next;
240 }
241 30 $i -= $znum;
242 }
243 ### 1 ...
244 65 push @ret, 1;
245 65 $o--;
246 }
247  
248 32 push @ret, (0) x $z;
249 ### final: "ret=".join('',@ret)
250  
251 32 ▶ if (! ref $zero && @ret >= 2*_WANTLEN_TO_BIGINT) {
Branch: 1 branch
BranchTrueFalseTotal
if (not ref $zero and @ret >= 64) 0 32 32
Condition33%1/3
not ref $zero and @ret >= 64
!ll&&!rl&&r
0320
MC/DC0%0/2
not ref $zero and @ret >= 64
not ref $zero @ret >= 64
Truth table33%1/3
not(A) and B
A= not ref $zeroB= @ret >= 64
ABresult
0X0
100
111
252 ### promote to BigInt ...
253 0 $zero = _to_bigint($zero);
254 }
255  
256 32 @ret = reverse @ret;
257 ### return: _digit_join(\@ret, 2, $zero)
258 32 return _digit_join(\@ret, 2, $zero);
259 }
260  
261 # $aref->[0] low digit
262 32 ▶sub _digit_join {
Subroutine _digit_join: called CC=2 SCAR=6.9
263 32 my ($aref, $radix, $zero) = @_;
264 32 my $n = $zero;
265 32 foreach my $digit (reverse @$aref) { # high to low
266 194 $n *= $radix;
267 194 $n += $digit;
268 }
269 32 return $n;
270 }
271  
272 58 ▶sub value_to_i {
Subroutine value_to_i: called CC=13 SCAR=25.8
Pod documented
273 58 my ($self, $value) = @_;
274 ### BalancedBinary value_to_i(): $value
275  
276 58 ▶ if ($value < 2 || $value != int($value)) {
Branch: 1 branch
BranchTrueFalseTotal
if ($value < 2 or $value != int $value) 26 32 58
Condition100%3/3
$value < 2 or $value != int $value
l!l&&r!l&&!r
52132
MC/DC100%2/2
$value < 2 or $value != int $value
$value < 2 $value != int $value
Truth table100%3/3
A or B
A= $value < 2B= $value != int $value
ABresult
1X1
011
000
277 26 return undef;
278 }
279 32 ▶ if (_is_infinite($value)) {
Branch: 1 branch
BranchTrueFalseTotal
if (_is_infinite($value)) 0 32 32
280 0 return $value;
281 }
282  
283 32 ▶ my @bits = _digit_split_lowtohigh($value,2)
Branch: 1 branch
BranchTrueFalseTotal
my(@bits) = _digit_split_lowtohigh($value, 2) or return undef 32 0 32
284 or return undef;
285  
286 32 ▶ _pred_on_bits($self,\@bits)
Branch: 1 branch
BranchTrueFalseTotal
_pred_on_bits($self, \@bits) or return undef 22 10 32
287 or return undef;
288  
289 22 my @num;
290 22 $num[0][0] = 0;
291 22 $num[1][0] = 1;
292 22 $num[1][1] = 1;
293 22 my $w = scalar(@bits) / 2;
294 ### $w
295  
296 22 my $zero = $value*0;
297 22 my $i = 1 + $zero;
298  
299 22 foreach my $z (1 .. $w) {
300 64 my $prev = $num[$z][0] = 1; # all zeros, no ones
301 64 ▶ if ($z > 16) {
Branch: 1 branch
BranchTrueFalseTotal
if ($z > 16) 0 64 64
302 0 $prev += $zero;
303 }
304 64 foreach my $o (1 .. $z) {
305 134 ▶ $num[$z][$o]
Condition100%2/2
$num[$z - 1][$o] || 0
l!l
7064
MC/DC100%1/1
$num[$z - 1][$o] || 0
$num[$z - 1][$o]
Truth table100%2/2
A
A= $num[$z - 1][$o]
Aresult
11
00
306 = ($prev # 1... $num[$z][$o-1]
307 += ($num[$z-1][$o] || 0)); # 0... if $z>=1
308 }
309 64 $i += $num[$z-1][$z-1];
310 }
311 ### base i: $i
312  
313 ### bits: join('',@bits)
314 22 shift @bits; # skip high 1-bit
315 22 my $z = $w;
316 22 my $o = $w-1;
317 22 foreach my $bit (@bits) { # high to low
318 ### at: "z=$z o=$o bit=$bit"
319 ### assert: $o >= 0
320 ### assert: $z >= $o
321 106 ▶ if ($bit) {
Branch: 1 branch
BranchTrueFalseTotal
if ($bit) { } 42 64 106
322 ### bit 1 add: $num[$z-1][$o]
323 42 ▶ $i += $num[$z-1][$o] || 0;
Condition100%2/2
$num[$z - 1][$o] || 0
l!l
1824
MC/DC100%1/1
$num[$z - 1][$o] || 0
$num[$z - 1][$o]
Truth table100%2/2
A
A= $num[$z - 1][$o]
Aresult
11
00
324 42 $o--;
325 } else {
326 64 $z--;
327 }
328 }
329 22 return $i;
330 }
331  
332 954 ▶sub value_to_i_floor {
Subroutine value_to_i_floor: called CC=1 SCAR=0.0
Pod documented
333 954 my ($self, $value) = @_;
334 954 return _value_to_i_round ($self, $value, 0);
335 }
336 952 ▶sub value_to_i_ceil {
Subroutine value_to_i_ceil: called CC=1 SCAR=0.0
Pod documented
337 952 my ($self, $value) = @_;
338 952 return _value_to_i_round ($self, $value, 1);
339 }
340  
341 # Return the i corresponding to $value.
342 # If $value is not balanced binary then round according to $ceil.
343 # $ceil=1 to round up, or $ceil=0 to round down.
344 #
345 1906 ▶sub _value_to_i_round {
Subroutine _value_to_i_round: called CC=16 SCAR=27.8
346 1906 my ($self, $value, $ceil) = @_;
347 ### _value_to_i_round(): $value
348  
349 1906 ▶ if ($value < 2) {
Branch: 1 branch
BranchTrueFalseTotal
if ($value < 2) 21 1885 1906
350 21 return $self->i_start();
351 }
352 1885 ▶ if (_is_infinite($value)) {
Branch: 1 branch
BranchTrueFalseTotal
if (_is_infinite($value)) 0 1885 1885
353 0 return $value;
354 }
355  
356 {
357 1885 my $int = int($value);
358 1885 ▶ if ($value != $int) {
Branch: 1 branch
BranchTrueFalseTotal
if ($value != $int) 32 1853 1885
359 32 $value = $int + $ceil; # +1 if not integer and want ceil
360 }
361 }
362 1885 my @bits = reverse _digit_split_lowtohigh($value,2);
363  
364 1885 ▶ if (scalar(@bits) & 1) {
Branch: 1 branch
BranchTrueFalseTotal
if (scalar @bits & 1) 681 1204 1885
365 # ENHANCE-ME: this is Catalan cumulative, or cumulative+1
366 ### odd num bits ...
367 681 @bits = ((0) x scalar(@bits), 1);
368 }
369 ### assert: (scalar(@bits) % 2) == 0
370  
371 1885 my @num;
372 1885 $num[0][0] = 0;
373 1885 $num[1][0] = 1;
374 1885 $num[1][1] = 1;
375 1885 my $w = scalar(@bits)/2;
376 ### $w
377  
378 1885 my $zero = $value*0;
379 1885 my $i = 1 + $zero;
380  
381 1885 foreach my $z (1 .. $w) {
382 8492 my $prev = $num[$z][0] = 1; # all zeros, no ones
383 8492 ▶ if ($z > 16) {
Branch: 1 branch
BranchTrueFalseTotal
if ($z > 16) 0 8492 8492
384 0 $prev += $zero;
385 }
386 8492 foreach my $o (1 .. $z) {
387 24000 ▶ $num[$z][$o]
Condition100%2/2
$num[$z - 1][$o] || 0
l!l
155088492
MC/DC100%1/1
$num[$z - 1][$o] || 0
$num[$z - 1][$o]
Truth table100%2/2
A
A= $num[$z - 1][$o]
Aresult
11
00
388 = ($prev # 1... $num[$z][$o-1]
389 += ($num[$z-1][$o] || 0)); # 0... if $z>=1
390 }
391 8492 $i += $num[$z-1][$z-1];
392 }
393 ### base i: $i
394  
395 ### bits: join('',@bits)
396 1885 shift @bits; # skip high 1-bit
397 1885 my $z = $w;
398 1885 my $o = $w-1;
399  
400 1885 foreach my $bit (@bits) { # high to low
401 ### at: "z=$z o=$o bit=$bit"
402 ### assert: $o >= 0
403 ### assert: $z >= $o
404 7186 ▶ if ($bit) {
Branch: 1 branch
BranchTrueFalseTotal
if ($bit) { } 2581 4605 7186
405 2581 ▶ if ($o == 0) {
Branch: 1 branch
BranchTrueFalseTotal
if ($o == 0) 387 2194 2581
406 ### all 1s used, rest round down to zeros, so done: $i + $ceil
407 387 return $i + $ceil;
408 }
409 ### bit 1 add: $num[$z-1][$o]
410 2194 ▶ $i += $num[$z-1][$o] || 0;
Condition100%2/2
$num[$z - 1][$o] || 0
l!l
1428766
MC/DC100%1/1
$num[$z - 1][$o] || 0
$num[$z - 1][$o]
Truth table100%2/2
A
A= $num[$z - 1][$o]
Aresult
11
00
411 2194 $o--;
412  
413 } else {
414 4605 ▶ if ($z == $o) {
Branch: 1 branch
BranchTrueFalseTotal
if ($z == $o) 1323 3282 4605
415 ### 0 out of place, round up to 101010 ...
416 1323 ▶ while ($o) {
Branch: 1 branch
BranchTrueFalseTotal
if ($o) 4413 1323 5736
417 4413 ▶ $i += $num[$o-1][$o] || 0;
Condition50%1/2
$num[$o - 1][$o] || 0
l!l
04413
MC/DC0%0/1
$num[$o - 1][$o] || 0
$num[$o - 1][$o]
Truth table50%1/2
A
A= $num[$o - 1][$o]
Aresult
11
00
418 4413 $o--;
419 }
420 1323 return $i - (1-$ceil);
421 }
422  
423 3282 $z--;
424 }
425 }
426 175 return $i;
427 }
428  
429  
430  
431 # 1 10,
432 # 2 1010,
433 # 3 1100,
434 # 4 101010,
435 # 5 101100,
436 # 6 110010,
437 # 7 110100,
438 # 8 111000,
439 # 9 10101010, 170
440 #
441 # 10xxxx
442 # 1xxxx0
443 # num(width) = 2*num(width-1) + extra
444 # num(1) = 1
445 # num(2) = 2*1 = 2
446 # num(3) = 2*2 + 1 = 5
447 # total(width)
448 # = num(1) + num(2) + num(3) + ... + num(width)
449 # = 1 + 2*1 + 2*2+1 +
450  
451 540 ▶sub pred {
Subroutine pred: called CC=4 SCAR=13.9
Pod documented
452 540 my ($self, $value) = @_;
453 ### BalancedBinary pred(): $value
454  
455 540 ▶ if ($value != int($value) || _is_infinite($value)) {
Branch: 1 branch
BranchTrueFalseTotal
if ($value != int $value or _is_infinite($value)) 176 364 540
Condition66%2/3
$value != int $value or _is_infinite($value)
l!l&&r!l&&!r
1760364
MC/DC50%1/2
$value != int $value or _is_infinite($value)
$value != int $value _is_infinite($value)
Truth table66%2/3
A or B
A= $value != int $valueB= _is_infinite($value)
ABresult
1X1
011
000
456 176 return 0;
457 }
458  
459 364 ▶ my @bits = _digit_split_lowtohigh($value,2)
Branch: 1 branch
BranchTrueFalseTotal
my(@bits) = _digit_split_lowtohigh($value, 2) or return 0 362 2 364
460 or return 0;
461 362 return _pred_on_bits($self,\@bits);
462 }
463 394 ▶sub _pred_on_bits {
Subroutine _pred_on_bits: called CC=5 SCAR=16.1
464 394 my ($self, $bits) = @_;
465 ### _pred_on_bits(): $bits
466  
467 394 ▶ if (scalar(@$bits) & 1) {
Branch: 1 branch
BranchTrueFalseTotal
if (scalar @$bits & 1) 170 224 394
468 ### odd length ...
469 170 return 0;
470 }
471  
472 224 ▶ if ($self->{'direction'} eq 'HtoL') {
Branch: 1 branch
BranchTrueFalseTotal
if ($self->{"direction"} eq "HtoL") 224 0 224
473 224 @$bits = reverse @$bits;
474 ### reversed bits: @$bits
475 }
476  
477 224 my $count = 0;
478 224 foreach my $bit (@$bits) {
479 ### at: "bit=$bit count=$count"
480 1040 ▶ if (($count += ($bit<<1)-1) < 0) {
Branch: 1 branch
BranchTrueFalseTotal
if (($count += ($bit << 1) - 1) < 0) 114 926 1040
481 114 return 0;
482 }
483 }
484 ### final count: $count
485 110 return ! $count;
486 }
487  
488 # w = log2(value) / 2
489 # Catalan = 4^w / (sqrt(Pi * w) * (w + 1))
490 # = 4^(log2(v)/2) / (sqrt(pi*log2(v)/2) * (log2(v)/2+1))
491 # = v / (sqrt(pi*log2(v)/2) * (log2(v)/2+1))
492 # = v / (sqrt(pi*log2(v)/2) * (log2(v)+2)/2)
493 # = v / (sqrt(pi*log2(v)/2)/2 * (log2(v)+2))
494 # = v / (sqrt(pi/8*log2(v)) * (log2(v)+2))
495 #
496 # if value has 2*w bits then cumulative catalan
497 # i = sum w=0 to log2(value)/2
498 # of value / (sqrt(pi/8*log2(value)) * (log2(value)+2))
499 #
500 # is cumulative close enough to the plain ?
501 #
502 # 2*w bits, ipart=Catalan(w) value=4^w
503 # so w = log4(value)
504 # ipart = Catalan(log4(value))
505 # =
506  
507 20 ▶sub value_to_i_estimate {
Subroutine value_to_i_estimate: called CC=5 SCAR=16.1
Pod documented
508 20 my ($self, $value) = @_;
509 ### value_to_i_estimate: $value
510  
511 20 ▶ if ($value <= 2) {
Branch: 1 branch
BranchTrueFalseTotal
if ($value <= 2) 8 12 20
512 8 return 1;
513 }
514  
515 12 my $log2 = _blog2_estimate($value);
516 12 ▶ if (! defined $log2) {
Branch: 1 branch
BranchTrueFalseTotal
unless (defined $log2) 11 1 12
517 11 $log2 = log($value) * (1/log(2));
518 }
519 12 $log2 = max($log2,1);
520  
521 12 ▶ if (ref $value && $value->isa('Math::BigInt')) {
Branch: 1 branch
BranchTrueFalseTotal
if (ref $value and $value->isa("Math::BigInt")) 1 11 12
Condition66%2/3
ref $value and $value->isa("Math::BigInt")
!ll&&!rl&&r
1101
MC/DC50%1/2
ref $value and $value->isa("Math::BigInt")
ref $value $value->isa("Math::BigInt")
Truth table66%2/3
A and B
A= ref $valueB= $value->isa("Math::BigInt")
ABresult
0X0
100
111
522 # oldish BigInt doesn't like to divide BigInt/NV
523 1 require Math::BigFloat;
524 1 $value = Math::BigFloat->new($value);
525 }
526  
527 12 return max(1,
528 int($value / (sqrt((3.141592/8)*$log2) * ($log2+1))));
529 }
530  
531 2 1;
532 __END__
« NumSeq/HafermanCarpet.pm ↑ Summary NumSeq/UndulatingNumbers.pm »