File Coverage

blib/lib/Math/NumSeq/Squares.pm

Criterion	Covered	Total	%
statement	87	90	96.6
branch	18	22	81.8
condition			n/a
subroutine	22	22	100.0
pod	9	9	100.0
total	136	143	95.1

# 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::Squares;
use 5.004;
use strict;
use POSIX 'ceil';
use List::Util 'max';

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

use Math::NumSeq;
@ISA = ('Math::NumSeq');

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

# use constant name =>  Math::NumSeq::__('Perfect Squares');
use constant description => Math::NumSeq::__('The squares 1,4,9,16,25, etc k*k.');
use constant characteristic_increasing => 1;
use constant characteristic_integer => 1;
use constant i_start => 0;
use constant values_min => 0;

#------------------------------------------------------------------------------
# cf A001105 2*n^2
#    A000037 non-squares
#    A010052 characterisic 1/0 for squares
#
use constant oeis_anum => 'A000290'; # squares

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

use constant 1.02 _UV_I_LIMIT => do {
  # Float integers too when IV=32bits ?
  # my $max = 1;
  # for (1 .. 256) {
  #   my $try = $max*2 + 1;
  #   ### $try
  #   if ($try == 2*$max || $try == 2*$max+2) {
  #     last;
  #   }
  #   $max = $try;
  # }
  my $max = ~0;

  my $bit = 4;
  for (my $i = $max; $i != 0; $i=int($i/8)) {
    $bit *= 2;
  }
  ### $bit

  my $sqrt = 0;
  for ( ; $bit != 0; $bit=int($bit/2)) {
    my $try = $sqrt + $bit;
    if ($try <= $max / $try) {
      $sqrt = $try;
    }
  }

  ### $max
  ### limit sqrt: $sqrt
  ### limit square: $sqrt*$sqrt
  ### sqrt hex: sprintf '%X', $sqrt
  ### square hex: sprintf '%X', $sqrt*$sqrt

  ### assert: $sqrt <= $max/$sqrt

  $sqrt
};

sub rewind {
  my ($self) = @_;
  $self->{'i'} = $self->i_start;
}
sub seek_to_i {
  my ($self, $i) = @_;
  if ($i >= _UV_I_LIMIT) {
    $i = Math::NumSeq::_to_bigint($i);
  }
  $self->{'i'} = $i;
}
sub seek_to_value {
  my ($self, $value) = @_;
  $self->seek_to_i($self->value_to_i_ceil($value));
}
sub next {
  my ($self) = @_;
  ### Squares next(): $self->{'i'}
  my $i = $self->{'i'}++;
  if ($i == _UV_I_LIMIT) {
    $self->{'i'} = Math::NumSeq::_to_bigint($self->{'i'});
  }
  return ($i, $i*$i);
}

sub ith {
  my ($self, $i) = @_;
  return $i*$i;
}
sub pred {
  my ($self, $value) = @_;
  ### Squares pred(): $value

  if ($value < 0) { return 0; }

  my $int = int($value);
  if ($value != $int) { return 0; }

  my $i = int(sqrt($int));
  return ($int == $i*$i);
}

sub value_to_i {
  my ($self, $value) = @_;
  if ($value >= 0) {
    my $int = int($value);
    if ($value == $int) {
      my $i = int(sqrt($int));
      if ($int == $self->ith($i)) {
        return $i;
      }
    }
  }
  return undef;
}
sub value_to_i_floor {
  my ($self, $value) = @_;
  if ($value < 0) { $value = 0; }
  return int(sqrt(int($value)));
}
*value_to_i_estimate = \&value_to_i_floor;

sub value_to_i_ceil {
  my ($self, $value) = @_;
  if ($value < 0) { return 0; }
  my $i = $self->value_to_i_floor($value);
  if ($i*$i < $value) {
    $i += 1;
  }
  return $i;
}


1;
__END__