File Coverage

blib/lib/Math/NumSeq/FibonacciWord.pm

Criterion	Covered	Total	%
statement	89	93	95.7
branch	12	16	75.0
condition	6	8	75.0
subroutine	18	19	94.7
pod	8	8	100.0
total	133	144	92.3

# Copyright 2010, 2011, 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::FibonacciWord;
use 5.004;
use strict;

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

use Math::NumSeq;
use Math::NumSeq::Base::IterateIth;
@ISA = ('Math::NumSeq::Base::IterateIth',
        'Math::NumSeq');

use Math::NumSeq::Fibbinary;

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


sub description {
  my ($self) = @_;
  if (ref $self && $self->{'fibonacci_word_type'} eq 'dense') {
    return Math::NumSeq::__('0/1/2 dense Fibonacci word taking pairs from the plain word.');
  }
  return Math::NumSeq::__('0/1 values related to Fibonacci numbers, 0,1,0,0,1,0,1,0,etc.');
}
use constant default_i_start => 0;
use constant characteristic_integer => 1;
use constant characteristic_smaller => 1;
use constant values_min => 0;
sub values_max {
  my ($self) = @_;
  return ($self->{'fibonacci_word_type'} eq 'dense' ? 2 : 1);
}

use constant parameter_info_array =>
  [
   { name    => 'fibonacci_word_type',
     display => Math::NumSeq::__('Fibonacci Word Type'),
     type    => 'enum',
     default => 'plain',
     choices => ['plain','dense'],
     choices_display => [Math::NumSeq::__('Plain'),
                         Math::NumSeq::__('Dense'),
                        ],
     description => Math::NumSeq::__('Which of the pair of values to show.'),
   },
  ];

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

# cf A003842 same with values 1/2 instead of 0/1
#    A014675 same with values 2/1 instead of 0/1
#    A001468 values 2/1 instead of 0/1, skip leading 0, self-referential
#    A005614 inverse 1/0, starting from 1
#
#    A003622 positions of 1s
#    A000201 positions of 0s
#    A089910 positions of 1,1 pairs
#    A114986 characteristic of A000201, with extra 1 ??
#    A096270 expressed as 01 and 011, is inverse with leading 0
#    A036299 values 0/1 inverse, bignum concatenating
#    A008352 values 1/2 inverse, bignum concatenating
#
#    A189479 0->01 1->101
#    A007066 positions of 0s
#    A076662 first diffs of positions, values 3/2 with extra leading 3
#
#    A135817 whythoff repres 0s
#    A135818 whythoff repres 1s
#    A189921 whythoff form
#    A135817 whythoff length A+B
#

# A003849 OFFSET=0 values 0,1, 0,0, 1,0, 1,0, etc
# A143667 OFFSET=1 values 1,0,2,2,etc
#
my %oeis_anum
  = (
     # OEIS-Catalogue array begin
     plain => 'A003849',                         #
     'dense,i_start=1,i_offset=-1' => 'A143667', # fibonacci_word_type=dense i_start=1 i_offset=-1
     # OEIS-Catalogue array end
    );
sub oeis_anum {
  my ($self) = @_;
  my $key = $self->{'fibonacci_word_type'};
  my $i_start = $self->i_start;
  if ($i_start != $self->default_i_start) {
    $key .= ",i_start=$i_start";
  }
  if ($self->{'i_offset'}) {
    $key .= ",i_offset=$self->{'i_offset'}";
  }
  return $oeis_anum{$key};
}

#------------------------------------------------------------------------------
# i_offset is a hack to number A143667 starting OFFSET=1, whereas otherwise
# here start i=0
#
# $self->{'i'} is the next $i to return from next()
#
# $self->{'value'} is Fibbinary->ith($self->{'i'}), or for "dense" is
# Fibbinary->ith(2 * $self->{'i'}).  $self->{'value'} is incremented by the
# same bit-twiddling as in Fibbinary.  The low bit of $self->{'value'} is
# the FibonacciWord $value.  Or for "dense" the low bit of two successive
# values combined.
#

sub rewind {
  my ($self) = @_;
  $self->{'i'} = $self->i_start;
  $self->{'value'} = 0;
  $self->{'i_offset'} ||= 0;
}
sub seek_to_i {
  my ($self, $i) = @_;
  $self->{'i'} = $i;
  if ($self->{'fibonacci_word_type'} eq 'dense') {
    $self->{'value'} = Math::NumSeq::Fibbinary->ith(2*$i);
  } else {
    $self->{'value'} = Math::NumSeq::Fibbinary->ith($i);
  }
}
sub next {
  my ($self) = @_;
  ### FibonacciWord next() ...

  if ($self->{'fibonacci_word_type'} eq 'dense') {
    my $v = $self->{'value'};
    my $high = ($v & 1) << 1;

    my $filled = ($v >> 1) | $v;
    my $mask = (($filled+1) ^ $filled) >> 1;
    $v = ($v | $mask) + 1;

    $filled = ($v >> 1) | $v;
    $mask = (($filled+1) ^ $filled) >> 1;
    $self->{'value'} = ($v | $mask) + 1;

    return ($self->{'i'}++, $high | ($v & 1));

  } else {
    my $v = $self->{'value'};
    my $filled = ($v >> 1) | $v;
    my $mask = (($filled+1) ^ $filled) >> 1;
    $self->{'value'} = ($v | $mask) + 1;

    ### value : sprintf('0b %6b',$v)
    ### filled: sprintf('0b %6b',$filled)
    ### mask  : sprintf('0b %6b',$mask)
    ### bit   : sprintf('0b %6b',$mask+1)
    ### newv  : sprintf('0b %6b',$self->{'value'})

    return ($self->{'i'}++, $v & 1);
  }
}

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

  $i = $i + $self->{'i_offset'};

  # if $i is inf or nan then $f0=$i*0 is nan and the while loop zero-trips
  # and return is nan

  my $f0 = ($i * 0) + 1;  # inherit bignum 1
  my $f1 = $f0 + 1;       # inherit bignum 2
  my $level = 0;
  ### start: "$f1,$f0  level=$level"

  # f1+f0 > i
  # f0 > i-f1
  # check i-f1 as the stopping point, so that if i=UV_MAX then won't
  # overflow a UV trying to get to f1>=i
  #
  while ($f0 <= $i-$f1) {
    ($f1,$f0) = ($f1+$f0,$f1);
    $level++;
  }
  ### above: "$f1,$f0  level=$level"

  if ($self->{'fibonacci_word_type'} eq 'dense') {
    my $v = Math::NumSeq::Fibbinary->ith(2*$i);
    my $high = ($v & 1) << 1;

    my $filled = ($v >> 1) | $v;
    my $mask = (($filled+1) ^ $filled) >> 1;
    $v = ($v | $mask) + 1;

    return ($high | ($v & 1));

  } else {

    do {
      ### at: "$f1,$f0  i=$i"
      if ($i >= $f1) {
        $i -= $f1;
      }
      ($f1,$f0) = ($f0,$f1-$f0);
    } while ($level--);

    ### assert: $i == 0 || $i == 1
    ### ret: $i
    return $i;
  }
}

sub pred {
  my ($self, $value) = @_;
  return ($value == 0 || $value == 1
          || ($self->{'fibonacci_word_type'} eq 'dense'
              && $value == 2));
}

1;
__END__