| 1 | # Copyright 2010, 2011, 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::Squares; | ||||||||||
| 19 | 4 | ▶ | use 5.004; | ||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||
| 20 | 4 | ▶ | use strict; | ||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||
| 21 | 4 | ▶ | use POSIX 'ceil'; | ||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||
| 22 | 4 | ▶ | use List::Util 'max'; | ||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||
| 23 | |||||||||||
| 24 | 4 | ▶ | use vars '$VERSION','@ISA'; | ||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||
| 25 | 4 | $VERSION = 75; | |||||||||
| 26 | |||||||||||
| 27 | 4 | ▶ | use Math::NumSeq; | ||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||
| 28 | 4 | @ISA = ('Math::NumSeq'); | |||||||||
| 29 | |||||||||||
| 30 | # uncomment this to run the ### lines | ||||||||||
| 31 | #use Smart::Comments; | ||||||||||
| 32 | |||||||||||
| 33 | # use constant name => Math::NumSeq::__('Perfect Squares'); | ||||||||||
| 34 | 4 | ▶ | use constant description => Math::NumSeq::__('The squares 1,4,9,16,25, etc k*k.'); | ||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||
| 35 | 4 | ▶ | use constant characteristic_increasing => 1; | ||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||
| 36 | 4 | ▶ | use constant characteristic_integer => 1; | ||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||
| 37 | 4 | ▶ | use constant i_start => 0; | ||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||
| 38 | 4 | ▶ | use constant values_min => 0; | ||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||
| 39 | |||||||||||
| 40 | #------------------------------------------------------------------------------ | ||||||||||
| 41 | # cf A001105 2*n^2 | ||||||||||
| 42 | # A000037 non-squares | ||||||||||
| 43 | # A010052 characterisic 1/0 for squares | ||||||||||
| 44 | # | ||||||||||
| 45 | 4 | ▶ | use constant oeis_anum => 'A000290'; # squares | ||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||
| 46 | |||||||||||
| 47 | #------------------------------------------------------------------------------ | ||||||||||
| 48 | |||||||||||
| 49 | 4 | ▶ | use constant 1.02 _UV_I_LIMIT => do { | ||||||||
|
Subroutine
BEGIN: called CC=4 SCAR=13.9
| |||||||||||
| 50 | # Float integers too when IV=32bits ? | ||||||||||
| 51 | # my $max = 1; | ||||||||||
| 52 | # for (1 .. 256) { | ||||||||||
| 53 | # my $try = $max*2 + 1; | ||||||||||
| 54 | # ### $try | ||||||||||
| 55 | # if ($try == 2*$max || $try == 2*$max+2) { | ||||||||||
| 56 | # last; | ||||||||||
| 57 | # } | ||||||||||
| 58 | # $max = $try; | ||||||||||
| 59 | # } | ||||||||||
| 60 | 4 | my $max = ~0; | |||||||||
| 61 | |||||||||||
| 62 | 4 | my $bit = 4; | |||||||||
| 63 | 4 | ▶ | for (my $i = $max; $i != 0; $i=int($i/8)) { | ||||||||
|
Branch: 1 branch
| |||||||||||
| 64 | 88 | $bit *= 2; | |||||||||
| 65 | } | ||||||||||
| 66 | ### $bit | ||||||||||
| 67 | |||||||||||
| 68 | 4 | my $sqrt = 0; | |||||||||
| 69 | 4 | ▶ | for ( ; $bit != 0; $bit=int($bit/2)) { | ||||||||
|
Branch: 1 branch
| |||||||||||
| 70 | 100 | my $try = $sqrt + $bit; | |||||||||
| 71 | 100 | ▶ | if ($try <= $max / $try) { | ||||||||
|
Branch: 1 branch
| |||||||||||
| 72 | 100 | $sqrt = $try; | |||||||||
| 73 | } | ||||||||||
| 74 | } | ||||||||||
| 75 | |||||||||||
| 76 | ### $max | ||||||||||
| 77 | ### limit sqrt: $sqrt | ||||||||||
| 78 | ### limit square: $sqrt*$sqrt | ||||||||||
| 79 | ### sqrt hex: sprintf '%X', $sqrt | ||||||||||
| 80 | ### square hex: sprintf '%X', $sqrt*$sqrt | ||||||||||
| 81 | |||||||||||
| 82 | ### assert: $sqrt <= $max/$sqrt | ||||||||||
| 83 | |||||||||||
| 84 | 4 | $sqrt | |||||||||
| 85 | 4 | }; | |||||||||
| 86 | |||||||||||
| 87 | 7 | ▶ | sub rewind { | ||||||||
|
Subroutine
rewind: called CC=1 SCAR=0.0
Pod
documented
| |||||||||||
| 88 | 7 | my ($self) = @_; | |||||||||
| 89 | 7 | $self->{'i'} = $self->i_start; | |||||||||
| 90 | } | ||||||||||
| 91 | 19 | ▶ | sub seek_to_i { | ||||||||
|
Subroutine
seek_to_i: called CC=2 SCAR=7.6
Pod
documented
| |||||||||||
| 92 | 19 | my ($self, $i) = @_; | |||||||||
| 93 | 19 | ▶ | if ($i >= _UV_I_LIMIT) { | ||||||||
|
Branch: 1 branch
| |||||||||||
| 94 | 0 | $i = Math::NumSeq::_to_bigint($i); | |||||||||
| 95 | } | ||||||||||
| 96 | 19 | $self->{'i'} = $i; | |||||||||
| 97 | } | ||||||||||
| 98 | 13 | ▶ | sub seek_to_value { | ||||||||
|
Subroutine
seek_to_value: called CC=1 SCAR=0.0
Pod
documented
| |||||||||||
| 99 | 13 | my ($self, $value) = @_; | |||||||||
| 100 | 13 | $self->seek_to_i($self->value_to_i_ceil($value)); | |||||||||
| 101 | } | ||||||||||
| 102 | 46 | ▶ | sub next { | ||||||||
|
Subroutine
next: called CC=2 SCAR=7.4
Pod
documented
| |||||||||||
| 103 | 46 | my ($self) = @_; | |||||||||
| 104 | ### Squares next(): $self->{'i'} | ||||||||||
| 105 | 46 | my $i = $self->{'i'}++; | |||||||||
| 106 | 46 | ▶ | if ($i == _UV_I_LIMIT) { | ||||||||
|
Branch: 1 branch
| |||||||||||
| 107 | 0 | $self->{'i'} = Math::NumSeq::_to_bigint($self->{'i'}); | |||||||||
| 108 | } | ||||||||||
| 109 | 46 | return ($i, $i*$i); | |||||||||
| 110 | } | ||||||||||
| 111 | |||||||||||
| 112 | 37 | ▶ | sub ith { | ||||||||
|
Subroutine
ith: called CC=1 SCAR=0.0
Pod
documented
| |||||||||||
| 113 | 37 | my ($self, $i) = @_; | |||||||||
| 114 | 37 | return $i*$i; | |||||||||
| 115 | } | ||||||||||
| 116 | 57 | ▶ | sub pred { | ||||||||
|
Subroutine
pred: called CC=3 SCAR=11.1
Pod
documented
| |||||||||||
| 117 | 57 | my ($self, $value) = @_; | |||||||||
| 118 | ### Squares pred(): $value | ||||||||||
| 119 | |||||||||||
| 120 | 0 | ▶ | if ($value < 0) { return 0; } | ||||||||
|
Branch: 1 branch
| |||||||||||
| 121 | |||||||||||
| 122 | 57 | my $int = int($value); | |||||||||
| 123 | 57 | ▶ | if ($value != $int) { return 0; } | ||||||||
|
Branch: 1 branch
| |||||||||||
| 124 | |||||||||||
| 125 | 32 | my $i = int(sqrt($int)); | |||||||||
| 126 | 32 | return ($int == $i*$i); | |||||||||
| 127 | } | ||||||||||
| 128 | |||||||||||
| 129 | 30 | ▶ | sub value_to_i { | ||||||||
|
Subroutine
value_to_i: called CC=4 SCAR=13.9
Pod
documented
| |||||||||||
| 130 | 30 | my ($self, $value) = @_; | |||||||||
| 131 | 30 | ▶ | if ($value >= 0) { | ||||||||
|
Branch: 1 branch
| |||||||||||
| 132 | 26 | my $int = int($value); | |||||||||
| 133 | 26 | ▶ | if ($value == $int) { | ||||||||
|
Branch: 1 branch
| |||||||||||
| 134 | 16 | my $i = int(sqrt($int)); | |||||||||
| 135 | 16 | ▶ | if ($int == $self->ith($i)) { | ||||||||
|
Branch: 1 branch
| |||||||||||
| 136 | 12 | return $i; | |||||||||
| 137 | } | ||||||||||
| 138 | } | ||||||||||
| 139 | } | ||||||||||
| 140 | 18 | return undef; | |||||||||
| 141 | } | ||||||||||
| 142 | 114 | ▶ | sub value_to_i_floor { | ||||||||
|
Subroutine
value_to_i_floor: called CC=2 SCAR=6.9
Pod
documented
| |||||||||||
| 143 | 114 | my ($self, $value) = @_; | |||||||||
| 144 | 114 | ▶ | if ($value < 0) { $value = 0; } | ||||||||
|
Branch: 1 branch
| |||||||||||
| 145 | 114 | return int(sqrt(int($value))); | |||||||||
| 146 | } | ||||||||||
| 147 | 4 | *value_to_i_estimate = \&value_to_i_floor; | |||||||||
| 148 | |||||||||||
| 149 | 55 | ▶ | sub value_to_i_ceil { | ||||||||
|
Subroutine
value_to_i_ceil: called CC=3 SCAR=11.0
Pod
documented
| |||||||||||
| 150 | 55 | my ($self, $value) = @_; | |||||||||
| 151 | 55 | ▶ | if ($value < 0) { return 0; } | ||||||||
|
Branch: 1 branch
| |||||||||||
| 152 | 52 | my $i = $self->value_to_i_floor($value); | |||||||||
| 153 | 52 | ▶ | if ($i*$i < $value) { | ||||||||
|
Branch: 1 branch
| |||||||||||
| 154 | 17 | $i += 1; | |||||||||
| 155 | } | ||||||||||
| 156 | 52 | return $i; | |||||||||
| 157 | } | ||||||||||
| 158 | |||||||||||
| 159 | |||||||||||
| 160 | 4 | 1; | |||||||||
| 161 | __END__ | ||||||||||