| 1 | # Copyright 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::GolayRudinShapiroCumulative; | ||||||||||||||||||||||||||||
| 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 | |||||||||||||||||||||||||||||
| 25 | 2 | ▶ | use Math::NumSeq; | ||||||||||||||||||||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||||||||||||||||||||
| 26 | 2 | @ISA = ('Math::NumSeq'); | |||||||||||||||||||||||||||
| 27 | 2 | *_is_infinite = \&Math::NumSeq::_is_infinite; | |||||||||||||||||||||||||||
| 28 | |||||||||||||||||||||||||||||
| 29 | 2 | ▶ | use Math::NumSeq::GolayRudinShapiro; | ||||||||||||||||||||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||||||||||||||||||||
| 30 | |||||||||||||||||||||||||||||
| 31 | # uncomment this to run the ### lines | ||||||||||||||||||||||||||||
| 32 | #use Smart::Comments; | ||||||||||||||||||||||||||||
| 33 | |||||||||||||||||||||||||||||
| 34 | |||||||||||||||||||||||||||||
| 35 | # use constant name => Math::NumSeq::__('Golay-Rudin-Shapiro Cumulative'); | ||||||||||||||||||||||||||||
| 36 | 2 | ▶ | use constant description => Math::NumSeq::__('Cumulative Golay/Rudin/Shapiro sequence.'); | ||||||||||||||||||||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||||||||||||||||||||
| 37 | 2 | ▶ | use constant values_min => 1; | ||||||||||||||||||||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||||||||||||||||||||
| 38 | 2 | ▶ | use constant characteristic_integer => 1; | ||||||||||||||||||||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||||||||||||||||||||
| 39 | 2 | ▶ | use constant characteristic_smaller => 1; | ||||||||||||||||||||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||||||||||||||||||||
| 40 | 2 | ▶ | use constant i_start => Math::NumSeq::GolayRudinShapiro->default_i_start; | ||||||||||||||||||||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||||||||||||||||||||
| 41 | |||||||||||||||||||||||||||||
| 42 | #------------------------------------------------------------------------------ | ||||||||||||||||||||||||||||
| 43 | # cf A020990 - cumulative GRS(2n+1), flips sign at odd i | ||||||||||||||||||||||||||||
| 44 | # A051032 - GRS cumulative of 2^n | ||||||||||||||||||||||||||||
| 45 | # A212591 - index of first occurrence of k in the partial sums | ||||||||||||||||||||||||||||
| 46 | # A020991 - index of last occurrence of k in the partial sums | ||||||||||||||||||||||||||||
| 47 | # A093573 - indexes of all positions where k occurs | ||||||||||||||||||||||||||||
| 48 | |||||||||||||||||||||||||||||
| 49 | 2 | ▶ | use constant oeis_anum => 'A020986'; # GRS +/-1 cumulative | ||||||||||||||||||||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||||||||||||||||||||
| 50 | |||||||||||||||||||||||||||||
| 51 | #------------------------------------------------------------------------------ | ||||||||||||||||||||||||||||
| 52 | |||||||||||||||||||||||||||||
| 53 | 7 | ▶ | sub rewind { | ||||||||||||||||||||||||||
|
Subroutine
rewind: called CC=1 SCAR=0.0
Pod
documented
| |||||||||||||||||||||||||||||
| 54 | 7 | my ($self) = @_; | |||||||||||||||||||||||||||
| 55 | 7 | $self->{'grs'} = Math::NumSeq::GolayRudinShapiro->new; | |||||||||||||||||||||||||||
| 56 | 7 | $self->{'value'} = 0; | |||||||||||||||||||||||||||
| 57 | } | ||||||||||||||||||||||||||||
| 58 | 2 | ▶ | sub tell_i { | ||||||||||||||||||||||||||
|
Subroutine
tell_i: called CC=1 SCAR=0.0
Pod
documented
| |||||||||||||||||||||||||||||
| 59 | 2 | my ($self) = @_; | |||||||||||||||||||||||||||
| 60 | 2 | return $self->{'grs'}->tell_i; | |||||||||||||||||||||||||||
| 61 | } | ||||||||||||||||||||||||||||
| 62 | 0 | ▶ | sub _UNTESTED__seek_to_i { | ||||||||||||||||||||||||||
|
Subroutine
_UNTESTED__seek_to_i: not called CC=2 SCAR=17.9
| |||||||||||||||||||||||||||||
| 63 | 0 | my ($self, $i) = @_; | |||||||||||||||||||||||||||
| 64 | 0 | $self->{'grs'}->seek_to_i($i); | |||||||||||||||||||||||||||
| 65 | 0 | ▶ | $self->{'value'} = $self->ith($i-1) || 0; | ||||||||||||||||||||||||||
|
Condition0%0/2
$self->ith($i - 1) || 0
MC/DC0%0/1
$self->ith($i - 1) || 0
$self->ith($i - 1)
Truth table0%0/2
A
A= $self->ith($i - 1)
| |||||||||||||||||||||||||||||
| 66 | } | ||||||||||||||||||||||||||||
| 67 | |||||||||||||||||||||||||||||
| 68 | 20034 | ▶ | sub next { | ||||||||||||||||||||||||||
|
Subroutine
next: called CC=1 SCAR=0.0
Pod
documented
| |||||||||||||||||||||||||||||
| 69 | 20034 | my ($self) = @_; | |||||||||||||||||||||||||||
| 70 | |||||||||||||||||||||||||||||
| 71 | # doubling up ... | ||||||||||||||||||||||||||||
| 72 | # $self->{'grs'}->next; | ||||||||||||||||||||||||||||
| 73 | # my ($i, $value) = $self->{'grs'}->next; | ||||||||||||||||||||||||||||
| 74 | # return ($i>>1, | ||||||||||||||||||||||||||||
| 75 | # ($self->{'value'} += $value)); | ||||||||||||||||||||||||||||
| 76 | |||||||||||||||||||||||||||||
| 77 | 20034 | my ($i, $value) = $self->{'grs'}->next; | |||||||||||||||||||||||||||
| 78 | return ($i, | ||||||||||||||||||||||||||||
| 79 | 20034 | ($self->{'value'} += $value)); | |||||||||||||||||||||||||||
| 80 | } | ||||||||||||||||||||||||||||
| 81 | |||||||||||||||||||||||||||||
| 82 | 20054 | ▶ | sub ith { | ||||||||||||||||||||||||||
|
Subroutine
ith: called CC=12 SCAR=24.9
Pod
documented
| |||||||||||||||||||||||||||||
| 83 | 20054 | my ($self, $i) = @_; | |||||||||||||||||||||||||||
| 84 | ### ith(): $i | ||||||||||||||||||||||||||||
| 85 | |||||||||||||||||||||||||||||
| 86 | 20054 | ▶ | if ($i < 0) { | ||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||
| 87 | 3 | return undef; | |||||||||||||||||||||||||||
| 88 | } | ||||||||||||||||||||||||||||
| 89 | 20051 | ▶ | if (_is_infinite($i)) { | ||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||
| 90 | 0 | return $i; | |||||||||||||||||||||||||||
| 91 | } | ||||||||||||||||||||||||||||
| 92 | |||||||||||||||||||||||||||||
| 93 | 20051 | ▶ | if ($i <= 1) { | ||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||
| 94 | 10 | return $i+1; | |||||||||||||||||||||||||||
| 95 | } | ||||||||||||||||||||||||||||
| 96 | |||||||||||||||||||||||||||||
| 97 | 20041 | my @bits = _bits_low_to_high($i); | |||||||||||||||||||||||||||
| 98 | 20041 | my $bit = shift @bits; | |||||||||||||||||||||||||||
| 99 | 20041 | my $ret = 1; | |||||||||||||||||||||||||||
| 100 | 20041 | my $power = ($i * 0) + 1; # inherit possible bignum 1 | |||||||||||||||||||||||||||
| 101 | |||||||||||||||||||||||||||||
| 102 | ### initial bit: $bit | ||||||||||||||||||||||||||||
| 103 | |||||||||||||||||||||||||||||
| 104 | 20041 | for (;;) { | |||||||||||||||||||||||||||
| 105 | 118229 | my $next = shift @bits; | |||||||||||||||||||||||||||
| 106 | 118229 | ▶ | if ($bit && $next) { | ||||||||||||||||||||||||||
|
Branch: 1 branch
Condition100%3/3
$bit and $next
MC/DC100%2/2
$bit and $next
$bit
$next
Truth table100%3/3
A and B
A= $bitB= $next
| |||||||||||||||||||||||||||||
| 107 | ### negate A to: "ret=$ret" | ||||||||||||||||||||||||||||
| 108 | 28744 | $ret = -$ret; | |||||||||||||||||||||||||||
| 109 | } | ||||||||||||||||||||||||||||
| 110 | 118229 | ▶ | if ($bit) { | ||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||
| 111 | 56792 | $ret += $power; | |||||||||||||||||||||||||||
| 112 | ### add A: "$power giving ret=$ret" | ||||||||||||||||||||||||||||
| 113 | } | ||||||||||||||||||||||||||||
| 114 | 118229 | $power *= 2; | |||||||||||||||||||||||||||
| 115 | 118229 | ▶ | last unless @bits; | ||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||
| 116 | 109123 | $bit = $next; | |||||||||||||||||||||||||||
| 117 | |||||||||||||||||||||||||||||
| 118 | 109123 | $next = shift @bits; | |||||||||||||||||||||||||||
| 119 | 109123 | $i = int($i/2); | |||||||||||||||||||||||||||
| 120 | 109123 | ▶ | if ($bit && $next) { | ||||||||||||||||||||||||||
|
Branch: 1 branch
Condition100%3/3
$bit and $next
MC/DC100%2/2
$bit and $next
$bit
$next
Truth table100%3/3
A and B
A= $bitB= $next
| |||||||||||||||||||||||||||||
| 121 | 28597 | $ret = -$ret; | |||||||||||||||||||||||||||
| 122 | } | ||||||||||||||||||||||||||||
| 123 | 109123 | ▶ | if ($bit) { | ||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||
| 124 | ### add B: "$power to ret=$ret" | ||||||||||||||||||||||||||||
| 125 | 52479 | $ret += $power; | |||||||||||||||||||||||||||
| 126 | } | ||||||||||||||||||||||||||||
| 127 | 109123 | ▶ | last unless @bits; | ||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||
| 128 | 98188 | $bit = $next; | |||||||||||||||||||||||||||
| 129 | } | ||||||||||||||||||||||||||||
| 130 | |||||||||||||||||||||||||||||
| 131 | ### final add: $power | ||||||||||||||||||||||||||||
| 132 | 20041 | return ($ret + $power); | |||||||||||||||||||||||||||
| 133 | } | ||||||||||||||||||||||||||||
| 134 | |||||||||||||||||||||||||||||
| 135 | 20041 | ▶ | sub _bits_low_to_high { | ||||||||||||||||||||||||||
|
Subroutine
_bits_low_to_high: called CC=5 SCAR=19.7
| |||||||||||||||||||||||||||||
| 136 | 20041 | my ($n) = @_; | |||||||||||||||||||||||||||
| 137 | 20041 | ▶ | if (ref $n) { | ||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||
| 138 | 0 | ▶ | if ($n->isa('Math::BigInt') | ||||||||||||||||||||||||||
|
Branch: 1 branch
Condition0%0/3
$n->isa("Math::BigInt") and $n->can("as_bin")
MC/DC0%0/2
$n->isa("Math::BigInt") and $n->can("as_bin")
$n->isa("Math::BigInt")
$n->can("as_bin")
Truth table0%0/3
A and B
A= $n->isa("Math::BigInt")B= $n->can("as_bin")
| |||||||||||||||||||||||||||||
| 139 | && $n->can('as_bin')) { | ||||||||||||||||||||||||||||
| 140 | 0 | return reverse split //, substr($n->as_bin,2); | |||||||||||||||||||||||||||
| 141 | } | ||||||||||||||||||||||||||||
| 142 | } | ||||||||||||||||||||||||||||
| 143 | 20041 | my @bits; | |||||||||||||||||||||||||||
| 144 | 20041 | ▶ | while ($n) { | ||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||
| 145 | 247393 | push @bits, $n % 2; | |||||||||||||||||||||||||||
| 146 | 247393 | $n = int($n/2); | |||||||||||||||||||||||||||
| 147 | } | ||||||||||||||||||||||||||||
| 148 | 20041 | return @bits; | |||||||||||||||||||||||||||
| 149 | } | ||||||||||||||||||||||||||||
| 150 | |||||||||||||||||||||||||||||
| 151 | 17 | ▶ | sub pred { | ||||||||||||||||||||||||||
|
Subroutine
pred: called CC=2 SCAR=8.1
Pod
documented
| |||||||||||||||||||||||||||||
| 152 | 17 | my ($self, $value) = @_; | |||||||||||||||||||||||||||
| 153 | 17 | ▶ | return ($value >= 1 | ||||||||||||||||||||||||||
|
Condition33%1/3
$value >= 1 && $value == int $value
MC/DC0%0/2
$value >= 1 && $value == int $value
$value >= 1
$value == int $value
Truth table33%1/3
A && B
A= $value >= 1B= $value == int $value
| |||||||||||||||||||||||||||||
| 154 | && $value == int($value)); | ||||||||||||||||||||||||||||
| 155 | } | ||||||||||||||||||||||||||||
| 156 | |||||||||||||||||||||||||||||
| 157 | 2 | 1; | |||||||||||||||||||||||||||
| 158 | __END__ | ||||||||||||||||||||||||||||