File Coverage

blib/lib/Math/NumSeq/Tribonacci.pm
Criterion Covered Total %
statement 52 53 98.1
branch 5 6 83.3
condition n/a
subroutine 14 14 100.0
pod 3 3 100.0
total 74 76 97.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::Tribonacci;
19 2     2   7356 use 5.004;
  2         5  
20 2     2   7 use strict;
  2         3  
  2         41  
21              
22 2     2   5 use vars '$VERSION', '@ISA';
  2         2  
  2         101  
23             $VERSION = 72;
24 2     2   320 use Math::NumSeq::Base::Sparse;
  2         2  
  2         87  
25             @ISA = ('Math::NumSeq::Base::Sparse');
26             *_is_infinite = \&Math::NumSeq::_is_infinite;
27              
28              
29             # uncomment this to run the ### lines
30             #use Smart::Comments;
31              
32             # use constant name => Math::NumSeq::__('Tribonacci Numbers');
33 2     2   6 use constant description => Math::NumSeq::__('Tribonacci numbers 0, 0, 1, 1, 2, 4, 7, 13, 24, being T(i) = T(i-1) + T(i-2) + T(i-3) starting from 0,0,1.');
  2         2  
  2         5  
34 2     2   6 use constant characteristic_non_decreasing => 1;
  2         6  
  2         65  
35 2     2   6 use constant characteristic_increasing_from_i => 3;
  2         1  
  2         65  
36 2     2   7 use constant characteristic_integer => 1;
  2         1  
  2         60  
37 2     2   7 use constant values_min => 0;
  2         1  
  2         63  
38 2     2   6 use constant i_start => 0;
  2         2  
  2         59  
39 2     2   7 use constant oeis_anum => 'A000073'; # tribonacci
  2         1  
  2         552  
40              
41             # The biggest f0 for which f0,f1,f2 all fit into a UV, but the sum f0+f1+f2
42             # would overflow and so require BigInt. Then back from there because the
43             # code checks the f0 after the sum f0+f1+f2 is formed.
44             #
45             my $uv_limit = do {
46             my $max = ~0;
47              
48             # f2+f1+f0 <= max
49             # f0 <= max-f1
50             # and f0+f1 <= max-f2
51             #
52             my $f0 = 0;
53             my $f1 = 0;
54             my $f2 = 1;
55             my $prev_prev_f0;
56             my $prev_f0;
57             while ($f0 <= $max - $f1
58             && $f0+$f1 <= $max - $f2) {
59             $prev_prev_f0 = $prev_f0;
60             $prev_f0 = $f0;
61             ($f0,$f1,$f2) = ($f1, $f2, $f2+$f1+$f0);
62             }
63              
64             ### Tribonacci UV limit ...
65             ### $prev_prev_f0
66             ### $prev_f0
67             ### $f0
68             ### $f1
69             ### $f2
70             ### ~0 : ~0
71              
72             $prev_prev_f0
73             };
74              
75             sub rewind {
76 7     7 1 351 my ($self) = @_;
77 7         20 $self->{'i'} = $self->i_start;
78 7         8 $self->{'f0'} = 0;
79 7         7 $self->{'f1'} = 0;
80 7         12 $self->{'f2'} = 1;
81             }
82             sub next {
83 273     273 1 32100 my ($self) = @_;
84             ### Tribonacci 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 273         520 $self->{'f0'}+$self->{'f1'}+$self->{'f2'});
93              
94 273 100       10731 if ($ret == $uv_limit) {
95             ### go to bigint f2 ...
96 2         7 $self->{'f2'} = Math::NumSeq::_to_bigint($self->{'f2'});
97             }
98              
99 273         7502 return ($self->{'i'}++, $ret);
100             }
101              
102             sub value_to_i_estimate {
103 24     24 1 239 my ($self, $value) = @_;
104              
105 24 50       32 if (_is_infinite($value)) {
106 0         0 return $value;
107             }
108              
109 24         230 my $f0 = my $f1 = ($value * 0); # inherit bignum 0
110 24         122 my $f2 = $f0 + 1; # inherit bignum 1
111              
112 24         97 my $i = 0;
113 24         15 for (;;) {
114 108 100       122 if ($value <= $f0) {
115 24         47 return $i;
116             }
117 84         354 ($f0,$f1,$f2) = ($f1,$f2, $f0+$f1+$f2);
118 84         1390 $i++;
119             }
120             }
121              
122             1;
123             __END__