File Coverage

blib/lib/Math/NumSeq/Perrin.pm
Criterion Covered Total %
statement 50 53 94.3
branch 4 6 66.6
condition n/a
subroutine 13 13 100.0
pod 3 3 100.0
total 70 75 93.3


line stmt bran cond sub pod time code
1             # Copyright 2010, 2011, 2012, 2013, 2014 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 .
17              
18             package Math::NumSeq::Perrin;
19 2     2   21149 use 5.004;
  2         9  
  2         125  
20 2     2   16 use strict;
  2         6  
  2         97  
21              
22 2     2   14 use vars '$VERSION', '@ISA';
  2         6  
  2         168  
23             $VERSION = 71;
24 2     2   692 use Math::NumSeq::Base::Sparse;
  2         5  
  2         159  
25             @ISA = ('Math::NumSeq::Base::Sparse');
26             *_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     2   15 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.');
  2         4  
  2         10  
34 2     2   14 use constant i_start => 0;
  2         4  
  2         157  
35 2     2   13 use constant characteristic_increasing_from_i => 1;
  2         6  
  2         99  
36 2     2   12 use constant characteristic_integer => 1;
  2         5  
  2         257  
37 2     2   12 use constant values_min => 0;
  2         4  
  2         195  
38 2     2   14 use constant oeis_anum => 'A001608'; # perrin
  2         10  
  2         1156  
39              
40             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             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             my $f0 = 3;
59             my $f1 = 0;
60             my $f2 = 2;
61             my $prev_f0;
62             while ($f0 <= $max - $f1) {
63             $prev_f0 = $f0;
64             ($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             };
74              
75             sub rewind {
76 6     6 1 897 my ($self) = @_;
77 6         46 $self->{'i'} = $self->i_start;
78 6         13 $self->{'f0'} = 3;
79 6         10 $self->{'f1'} = 0;
80 6         186 $self->{'f2'} = 2;
81             }
82             sub next {
83 124     124 1 1667 my ($self) = @_;
84             ### Perrin next(): "i=$self->{'i'} $self->{'f0'} $self->{'f1'} $self->{'f2'}"
85 124         407 (my $ret,
86             $self->{'f0'},
87             $self->{'f1'},
88             $self->{'f2'})
89             = ($self->{'f0'},
90             $self->{'f1'},
91             $self->{'f2'},
92             $self->{'f0'}+$self->{'f1'});
93              
94 124 50       425 if ($ret == $uv_limit) {
95             ### go to bigint ...
96 0         0 $self->{'f1'} = Math::NumSeq::_to_bigint($self->{'f1'});
97 0         0 $self->{'f2'} = Math::NumSeq::_to_bigint($self->{'f2'});
98             }
99              
100             ### ret: "$ret"
101 124         378 return ($self->{'i'}++, $ret);
102             }
103              
104             sub value_to_i_estimate {
105 24     24 1 415 my ($self, $value) = @_;
106              
107 24 50       67 if (_is_infinite($value)) {
108 0         0 return $value;
109             }
110              
111 24         699 my $f1 = ($value * 0); # inherit bignum 0
112 24         217 my $f0 = $f1 + 3; # inherit bignum 3
113 24         294 my $f2 = $f1 + 2; # inherit bignum 2
114              
115 24         282 my $i = 0;
116 24         30 for (;;) {
117             ### at: "i=$i $f0, $f1, $f2"
118 139 100       442 if ($value <= $f0) {
119 24         98 return $i;
120             }
121 115         1706 ($f0,$f1,$f2) = ($f1,$f2, $f0+$f1);
122 115         3093 $i++;
123             }
124             }
125              
126             1;
127             __END__