File Coverage

blib/lib/Math/NumSeq/GolayRudinShapiroCumulative.pm

Criterion	Covered	Total	%
statement	78	84	92.8
branch	18	22	81.8
condition	7	14	50.0
subroutine	17	18	94.4
pod	5	5	100.0
total	125	143	87.4

# Copyright 2012, 2013, 2014 Kevin Ryde

# This file is part of Math-NumSeq.
#
# Math-NumSeq is free software; you can redistribute it and/or modify
# it under the terms of the GNU General Public License as published by the
# Free Software Foundation; either version 3, or (at your option) any later
# version.
#
# Math-NumSeq is distributed in the hope that it will be useful, but
# WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
# or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
# for more details.
#
# You should have received a copy of the GNU General Public License along
# with Math-NumSeq.  If not, see .

package Math::NumSeq::GolayRudinShapiroCumulative;
use 5.004;
use strict;

use vars '$VERSION', '@ISA';
$VERSION = 71;

use Math::NumSeq;
@ISA = ('Math::NumSeq');
*_is_infinite = \&Math::NumSeq::_is_infinite;

use Math::NumSeq::GolayRudinShapiro;

# uncomment this to run the ### lines
#use Smart::Comments;


# use constant name => Math::NumSeq::__('Golay-Rudin-Shapiro Cumulative');
use constant description => Math::NumSeq::__('Cumulative Golay/Rudin/Shapiro sequence.');
use constant values_min => 1;
use constant characteristic_integer => 1;
use constant characteristic_smaller => 1;
use constant i_start => Math::NumSeq::GolayRudinShapiro->default_i_start;

#------------------------------------------------------------------------------
# cf A020990 - cumulative GRS(2n+1), flips sign at odd i
#    A051032 - GRS cumulative of 2^n
#    A212591 - index of first occurrence of k in the partial sums
#    A020991 - index of last occurrence of k in the partial sums
#    A093573 - indexes of all positions where k occurs

use constant oeis_anum => 'A020986';  # GRS +/-1 cumulative

#------------------------------------------------------------------------------

sub rewind {
  my ($self) = @_;
  $self->{'grs'} = Math::NumSeq::GolayRudinShapiro->new;
  $self->{'value'} = 0;
}
sub tell_i {
  my ($self) = @_;
  return $self->{'grs'}->tell_i;
}
sub _UNTESTED__seek_to_i {
  my ($self, $i) = @_;
  $self->{'grs'}->seek_to_i($i);
  $self->{'value'} = $self->ith($i-1) || 0;
}

sub next {
  my ($self) = @_;

  # doubling up ...
  # $self->{'grs'}->next;
  # my ($i, $value) = $self->{'grs'}->next;
  # return ($i>>1,
  #         ($self->{'value'} += $value));

  my ($i, $value) = $self->{'grs'}->next;
  return ($i,
          ($self->{'value'} += $value));
}

sub ith {
  my ($self, $i) = @_;
  ### ith(): $i

  if ($i < 0) {
    return undef;
  }
  if (_is_infinite($i)) {
    return $i;
  }

  if ($i <= 1) {
    return $i+1;
  }

  my @bits = _bits_low_to_high($i);
  my $bit = shift @bits;
  my $ret = 1;
  my $power = ($i * 0) + 1;   # inherit possible bignum 1

  ### initial bit: $bit

  for (;;) {
    my $next = shift @bits;
    if ($bit && $next) {
      ### negate A to: "ret=$ret"
      $ret = -$ret;
    }
    if ($bit) {
      $ret += $power;
      ### add A: "$power giving ret=$ret"
    }
    $power *= 2;
    last unless @bits;
    $bit = $next;

    $next = shift @bits;
    $i = int($i/2);
    if ($bit && $next) {
      $ret = -$ret;
    }
    if ($bit) {
      ### add B: "$power to ret=$ret"
      $ret += $power;
    }
    last unless @bits;
    $bit = $next;
  }

  ### final add: $power
  return ($ret + $power);
}

sub _bits_low_to_high {
  my ($n) = @_;
  if (ref $n) {
    if ($n->isa('Math::BigInt')
        && $n->can('as_bin')) {
      return reverse split //, substr($n->as_bin,2);
    }
  }
  my @bits;
  while ($n) {
    push @bits, $n % 2;
    $n = int($n/2);
  }
  return @bits;
}

sub pred {
  my ($self, $value) = @_;
  return ($value >= 1
          && $value == int($value));
}

1;
__END__