File Coverage

blib/lib/Math/NumSeq/SpiroFibonacci.pm

Criterion	Covered	Total	%
statement	66	88	75.0
branch	12	22	54.5
condition	6	18	33.3
subroutine	15	20	75.0
pod	5	7	71.4
total	104	155	67.1

# 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 .


# cf
# A092360 Spiro-tribonacci numbers: a(n) = sum of three previous terms that are nearest when terms arranged in a spiral.
# A092369 Spiro-tetranacci numbers: a(n) = sum of four previous terms that are nearest when terms arranged in a spiral.
# A094769 Square spiral of sums of selected preceding terms, starting at 0 followed by 1 (a spiral Fibonacci-like sequence).


# math-image --values=SpiroFibonacci --output=numbers --size=78
#
# math-image --values=SpiroFibonacci,recurrence_type=absdiff --output=text --size=60x15


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

use vars '$VERSION', '@ISA';
$VERSION = 71;
use Math::NumSeq;
@ISA = ('Math::NumSeq');
*_to_bigint = \&Math::NumSeq::_to_bigint;

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


# use constant name => Math::NumSeq::__('...');
use constant description => Math::NumSeq::__('Spiro-Fibonacci recurrence.');
use constant default_i_start => 0;

use constant parameter_info_array =>
  [
   # { name    => 'spiral_type',
   #   type    => 'enum',
   #   default => 'square',
   #   choices => ['square','hex'],
   # },
   { name    => 'recurrence_type',
     type    => 'enum',
     choices => ['additive','absdiff'],
     default => 'additive',
   },
   { name    => 'initial_0',
     display => Math::NumSeq::__('Initial value 0'),
     type    => 'integer',
     default => 0,
     width   => 3,
     description => Math::NumSeq::__('Initial value ...'),
   },
   { name    => 'initial_1',
     display => Math::NumSeq::__('Initial value 1'),
     type    => 'integer',
     default => 1,
     width   => 3,
     description => Math::NumSeq::__('Initial value ...'),
   },
  ];

sub characteristic_integer {
  my ($self) = @_;
  return (_is_integer($self->{'initial_0'})
          && _is_integer($self->{'initial_1'}));
}
sub characteristic_smaller {
  my ($self) = @_;
  return ($self->{'recurrence_type'} eq 'absdiff');
}
sub _is_integer {
  my ($n) = @_;
  return ($n == int($n));
}

# FIXME: absdiff range related to least common multiple, maybe
sub values_min {
  my ($self) = @_;
  if ($self->{'initial_0'} >= 0 && $self->{'initial_1'} >= 0) {
    return _min (0, $self->{'initial_0'}, $self->{'initial_1'});
  }
  return undef;
}
sub values_max {
  my ($self) = @_;
  if ($self->{'recurrence_type'} eq 'absdiff') {
    return _max (abs($self->{'initial_0'}),
                 abs($self->{'initial_1'}));
  } else {
    if ($self->{'initial_0'} <= 0 && $self->{'initial_1'} <= 0) {
      return _max ($self->{'initial_0'},
                   $self->{'initial_1'});
    } else {
      return undef;
    }
  }
}
sub _min {
  my $ret = shift;
  while (@_) {
    my $next = shift;
    if ($ret > $next) {
      $ret = $next;
    }
  }
  return $ret;
}
sub _max {
  my $ret = shift;
  while (@_) {
    my $next = shift;
    if ($next > $ret) {
      $ret = $next;
    }
  }
  return $ret;
}


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

# cf A079422 cumulative absdiff up to n^2
#    A094925 hexagonal 1,1  three around a(n-1)
#    A094926 hexagonal 0,1  three around a(n-1)

my %oeis_anum = ('additive,0,1' => 'A078510',
                 # OEIS-Catalogue: A078510

                 'absdiff,0,1' => 'A079421',
                 # OEIS-Catalogue: A079421 recurrence_type=absdiff

                 # all zeros if initial_0 == initial_1 == 0
                 'additive,0,0' => 'A000004',
                 'absdiff,0,0'  => 'A000004',
                 # OEIS-Other: A000004 initial_1=0
                 # OEIS-Other: A000004 initial_1=0 recurrence_type=absdiff
                );

sub oeis_anum {
  my ($self) = @_;
  return $oeis_anum{join(',',
                         @{$self}{  # hash slice
                           'recurrence_type',
                             'initial_0',
                               'initial_1'})};
}


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

use constant 1.02;
use constant _UV_LIMIT => (~0 >> 1);
use constant _IV_NEG_LIMIT => - (_UV_LIMIT >> 1);

# my %spiral_type = (square => { num_sides   => 2,
#                                side_longer => -1,
#                              },
#                    hex => { num_sides   => 6,
#                             side_longer => 1,
#                           },
#                   );

sub rewind {
  my ($self) = @_;
  $self->{'i'}     = $self->i_start;
  $self->{'queue'} = [$self->{'initial_0'}, $self->{'initial_1'}];
  $self->{'num_sides'}  = 2;
  $self->{'side_len'}   = 1;
  $self->{'side'}  = $self->{'num_sides'};
  $self->{'count'} = 2;
}

sub next {
  my ($self) = @_;
  ### next(): "i=$self->{'i'}  side_len=$self->{'side_len'} side=$self->{'side'} count=$self->{'count'}"

  my $queue = $self->{'queue'};
  my $i = $self->{'i'}++;
  if ($i < 2) {
    ### initial queue ...
    return ($i, $queue->[$i]);
  }

  my $value;
  if ($self->{'recurrence_type'} eq 'absdiff') {
    $value = abs($queue->[-1] - $queue->[0]);
  } else {
    $value = $queue->[-1] + $queue->[0];
  }
  if (! ref $value && ($value >= _UV_LIMIT || $value <= _IV_NEG_LIMIT)) {
    $queue->[-1] = _to_bigint($queue->[-1]);
  }

  push @$queue, $value;
  my $count = --$self->{'count'};
  ### count down to: $count

  if ($count > 0 && $self->{'side_len'} >= 2) {
    shift @$queue;
  } elsif ($count < 0) {
    ### end of side, next side ...
    if (--$self->{'side'} <= 0) {
      ### end of sides, next loop ...
      $self->{'side'} = $self->{'num_sides'};
      $self->{'side_len'}++;
    }
    $self->{'count'} = $self->{'side_len'};
  } else {
    ### count==0 corner ...
  }
  return ($i, $value);
}

# sub new {
#   ### SpiroFibonacci new(): @_
#   my $self = shift->SUPER::new(@_);
#   require Math::PlanePath::SquareSpiral;
#   $self->{'path'} = Math::PlanePath::SquareSpiral->new;
#   $self->{'cache'} = [];
#   $self->{'cache'}->[1] = $self->{'initial_0'};
#   $self->{'cache'}->[2] = $self->{'initial_1'};
#   return $self;
# }
#
# sub ith {
#   my ($self, $i) = @_;
#   ### SpiroFibonacci ith(): $i
#
#   if (_is_infinite($i)) {
#     return undef;
#   }
#
#   if ($i <= 0) {
#     return undef;
#   }
#   my $orig_i = $i;
#
#   my $cache = $self->{'cache'};
#   my $path = $self->{'path'};
#   my @pending = ($i);
#   my $total = 0;
#
#   while (@pending) {
#     ### @pending
#     $i = pop @pending;
#     if (defined $cache->[$i]) {
#       if ($self->{'recurrence_type'} eq 'absdiff') {
#         $total ^= $cache->[$i];
#       } else {
#         $total += $cache->[$i];
#       }
#     } else {
#       my ($x,$y) = $path->n_to_xy($i);
#       my $pi = 0;
#       foreach my $dxdy ([0,1],[0,-1],
#                         [1,0],[-1,0]) {
#         my ($dx,$dy) = @$dxdy;
#         my $n = $path->xy_to_n($x+$dx,$y+$dy);
#         if ($n < $i-1 && $n > $pi) {
#           ### straight at: "i=$i,x=$x,y=$y   dx=$dx dy=$dy pi=$n"
#           $pi = $n;
#         }
#       }
#       if (! $pi) {
#         foreach my $dxdy ([1,1],[1,-1],
#                           [-1,1],[-1,-1]) {
#           my ($dx,$dy) = @$dxdy;
#           my $n = $path->xy_to_n($x+$dx,$y+$dy);
#           if ($n < $i-1 && $n > $pi) {
#             ### diagonal at: "i=$i,x=$x,y=$y   dx=$dx dy=$dy pi=$n"
#             $pi = $n;
#           }
#         }
#       }
#       if (@pending > 100000) { die; }
#       push @pending, $pi;
#       push @pending, $i-1;
#     }
#   }
#   $self->{'cache'}->[$orig_i] = $total;
#
#   ### $total
#   return $total;
# }

1;
__END__