| 1 | # Copyright 2010, 2011, 2012, 2013, 2014, 2016, 2019, 2020, 2021 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::Perrin; | ||||||||||
| 19 | 2 | ▶ | use 5.004; | ||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||
| 20 | 2 | ▶ | use strict; | ||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||
| 21 | |||||||||||
| 22 | 2 | ▶ | use vars '$VERSION', '@ISA'; | ||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||
| 23 | 2 | $VERSION = 75; | |||||||||
| 24 | 2 | ▶ | use Math::NumSeq::Base::Sparse; | ||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||
| 25 | 2 | @ISA = ('Math::NumSeq::Base::Sparse'); | |||||||||
| 26 | 2 | *_is_infinite = \&Math::NumSeq::_is_infinite; | |||||||||
| 27 | |||||||||||
| 28 | # uncomment this to run the ### lines | ||||||||||
| 29 | #use Smart::Comments; | ||||||||||
| 30 | |||||||||||
| 31 | |||||||||||
| 32 | # use constant name => Math::NumSeq::__('Perrin Sequence'); | ||||||||||
| 33 | 2 | ▶ | use constant description => Math::NumSeq::__('Perrin numbers 3, 0, 2, 3, 2, 5, 5, 7, 10, etc, being P(i) = P(i-2) + P(i-3) starting from 3,0,2.'); | ||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||
| 34 | 2 | ▶ | use constant i_start => 0; | ||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||
| 35 | 2 | ▶ | use constant characteristic_increasing_from_i => 1; | ||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||
| 36 | 2 | ▶ | use constant characteristic_integer => 1; | ||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||
| 37 | 2 | ▶ | use constant values_min => 0; | ||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||
| 38 | 2 | ▶ | use constant oeis_anum => 'A001608'; # perrin | ||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||
| 39 | |||||||||||
| 40 | 2 | my $uv_limit = do { | |||||||||
| 41 | # Float integers too in 32 bits ? | ||||||||||
| 42 | # my $max = 1; | ||||||||||
| 43 | # for (1 .. 256) { | ||||||||||
| 44 | # my $try = $max*2 + 1; | ||||||||||
| 45 | # ### $try | ||||||||||
| 46 | # if ($try == 2*$max || $try == 2*$max+2) { | ||||||||||
| 47 | # last; | ||||||||||
| 48 | # } | ||||||||||
| 49 | # $max = $try; | ||||||||||
| 50 | # } | ||||||||||
| 51 | 2 | my $max = ~0; | |||||||||
| 52 | |||||||||||
| 53 | # f1+f0 > max | ||||||||||
| 54 | # f0 > max-f1 | ||||||||||
| 55 | # check i-f1 as the stopping point, so that if i=UV_MAX then won't | ||||||||||
| 56 | # overflow a UV trying to get to f1>=i | ||||||||||
| 57 | # | ||||||||||
| 58 | 2 | my $f0 = 3; | |||||||||
| 59 | 2 | my $f1 = 0; | |||||||||
| 60 | 2 | my $f2 = 2; | |||||||||
| 61 | 2 | my $prev_f0; | |||||||||
| 62 | 2 | ▶ | while ($f0 <= $max - $f1) { | ||||||||
|
Branch: 1 branch
| |||||||||||
| 63 | 310 | $prev_f0 = $f0; | |||||||||
| 64 | 310 | ($f0,$f1,$f2) = ($f1, $f2, $f0+$f1); | |||||||||
| 65 | } | ||||||||||
| 66 | ### $prev_f0 | ||||||||||
| 67 | ### $f0 | ||||||||||
| 68 | ### $f1 | ||||||||||
| 69 | ### $f2 | ||||||||||
| 70 | ### ~0 : ~0 | ||||||||||
| 71 | |||||||||||
| 72 | $prev_f0 | ||||||||||
| 73 | 2 | }; | |||||||||
| 74 | |||||||||||
| 75 | 6 | ▶ | sub rewind { | ||||||||
|
Subroutine
rewind: called CC=1 SCAR=0.0
Pod
documented
| |||||||||||
| 76 | 6 | my ($self) = @_; | |||||||||
| 77 | 6 | $self->{'i'} = $self->i_start; | |||||||||
| 78 | 6 | $self->{'f0'} = 3; | |||||||||
| 79 | 6 | $self->{'f1'} = 0; | |||||||||
| 80 | 6 | $self->{'f2'} = 2; | |||||||||
| 81 | } | ||||||||||
| 82 | 124 | ▶ | sub next { | ||||||||
|
Subroutine
next: called CC=2 SCAR=7.9
Pod
documented
| |||||||||||
| 83 | 124 | my ($self) = @_; | |||||||||
| 84 | ### Perrin next(): "i=$self->{'i'} $self->{'f0'} $self->{'f1'} $self->{'f2'}" | ||||||||||
| 85 | (my $ret, | ||||||||||
| 86 | $self->{'f0'}, | ||||||||||
| 87 | $self->{'f1'}, | ||||||||||
| 88 | $self->{'f2'}) | ||||||||||
| 89 | = ($self->{'f0'}, | ||||||||||
| 90 | $self->{'f1'}, | ||||||||||
| 91 | $self->{'f2'}, | ||||||||||
| 92 | 124 | $self->{'f0'}+$self->{'f1'}); | |||||||||
| 93 | |||||||||||
| 94 | 124 | ▶ | if ($ret == $uv_limit) { | ||||||||
|
Branch: 1 branch
| |||||||||||
| 95 | ### go to bigint ... | ||||||||||
| 96 | 0 | $self->{'f1'} = Math::NumSeq::_to_bigint($self->{'f1'}); | |||||||||
| 97 | 0 | $self->{'f2'} = Math::NumSeq::_to_bigint($self->{'f2'}); | |||||||||
| 98 | } | ||||||||||
| 99 | |||||||||||
| 100 | ### ret: "$ret" | ||||||||||
| 101 | 124 | return ($self->{'i'}++, $ret); | |||||||||
| 102 | } | ||||||||||
| 103 | |||||||||||
| 104 | 24 | ▶ | sub value_to_i_estimate { | ||||||||
|
Subroutine
value_to_i_estimate: called CC=3 SCAR=11.0
Pod
documented
| |||||||||||
| 105 | 24 | my ($self, $value) = @_; | |||||||||
| 106 | |||||||||||
| 107 | 24 | ▶ | if (_is_infinite($value)) { | ||||||||
|
Branch: 1 branch
| |||||||||||
| 108 | 0 | return $value; | |||||||||
| 109 | } | ||||||||||
| 110 | |||||||||||
| 111 | 24 | my $f1 = ($value * 0); # inherit bignum 0 | |||||||||
| 112 | 24 | my $f0 = $f1 + 3; # inherit bignum 3 | |||||||||
| 113 | 24 | my $f2 = $f1 + 2; # inherit bignum 2 | |||||||||
| 114 | |||||||||||
| 115 | 24 | my $i = 0; | |||||||||
| 116 | 24 | for (;;) { | |||||||||
| 117 | ### at: "i=$i $f0, $f1, $f2" | ||||||||||
| 118 | 139 | ▶ | if ($value <= $f0) { | ||||||||
|
Branch: 1 branch
| |||||||||||
| 119 | 24 | return $i; | |||||||||
| 120 | } | ||||||||||
| 121 | 115 | ($f0,$f1,$f2) = ($f1,$f2, $f0+$f1); | |||||||||
| 122 | 115 | $i++; | |||||||||
| 123 | } | ||||||||||
| 124 | } | ||||||||||
| 125 | |||||||||||
| 126 | 2 | 1; | |||||||||
| 127 | __END__ | ||||||||||