| 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::Tribonacci; | ||||||||||||||||||||||||||||
| 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 | |||||||||||||||||||||||||||||
| 29 | # uncomment this to run the ### lines | ||||||||||||||||||||||||||||
| 30 | #use Smart::Comments; | ||||||||||||||||||||||||||||
| 31 | |||||||||||||||||||||||||||||
| 32 | # use constant name => Math::NumSeq::__('Tribonacci Numbers'); | ||||||||||||||||||||||||||||
| 33 | 2 | ▶ | 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.'); | ||||||||||||||||||||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||||||||||||||||||||
| 34 | 2 | ▶ | use constant characteristic_non_decreasing => 1; | ||||||||||||||||||||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||||||||||||||||||||
| 35 | 2 | ▶ | use constant characteristic_increasing_from_i => 3; | ||||||||||||||||||||||||||
|
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 i_start => 0; | ||||||||||||||||||||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||||||||||||||||||||
| 39 | 2 | ▶ | use constant oeis_anum => 'A000073'; # tribonacci | ||||||||||||||||||||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||||||||||||||||||||
| 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 | 2 | my $uv_limit = do { | |||||||||||||||||||||||||||
| 46 | 2 | my $max = ~0; | |||||||||||||||||||||||||||
| 47 | |||||||||||||||||||||||||||||
| 48 | # f2+f1+f0 <= max | ||||||||||||||||||||||||||||
| 49 | # f0 <= max-f1 | ||||||||||||||||||||||||||||
| 50 | # and f0+f1 <= max-f2 | ||||||||||||||||||||||||||||
| 51 | # | ||||||||||||||||||||||||||||
| 52 | 2 | my $f0 = 0; | |||||||||||||||||||||||||||
| 53 | 2 | my $f1 = 0; | |||||||||||||||||||||||||||
| 54 | 2 | my $f2 = 1; | |||||||||||||||||||||||||||
| 55 | 2 | my $prev_prev_f0; | |||||||||||||||||||||||||||
| 56 | my $prev_f0; | ||||||||||||||||||||||||||||
| 57 | 2 | ▶ | while ($f0 <= $max - $f1 | ||||||||||||||||||||||||||
|
Branch: 1 branch
Condition66%2/3
$f0 <= $max - $f1 and $f0 + $f1 <= $max - $f2
MC/DC50%1/2
$f0 <= $max - $f1 and $f0 + $f1 <= $max - $f2
$f0 <= $max - $f1
$f0 + $f1 <= $max - $f2
Truth table66%2/3
A and B
A= $f0 <= $max - $f1B= $f0 + $f1 <= $max - $f2
| |||||||||||||||||||||||||||||
| 58 | && $f0+$f1 <= $max - $f2) { | ||||||||||||||||||||||||||||
| 59 | 146 | $prev_prev_f0 = $prev_f0; | |||||||||||||||||||||||||||
| 60 | 146 | $prev_f0 = $f0; | |||||||||||||||||||||||||||
| 61 | 146 | ($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 | 2 | }; | |||||||||||||||||||||||||||
| 74 | |||||||||||||||||||||||||||||
| 75 | 7 | ▶ | sub rewind { | ||||||||||||||||||||||||||
|
Subroutine
rewind: called CC=1 SCAR=0.0
Pod
documented
| |||||||||||||||||||||||||||||
| 76 | 7 | my ($self) = @_; | |||||||||||||||||||||||||||
| 77 | 7 | $self->{'i'} = $self->i_start; | |||||||||||||||||||||||||||
| 78 | 7 | $self->{'f0'} = 0; | |||||||||||||||||||||||||||
| 79 | 7 | $self->{'f1'} = 0; | |||||||||||||||||||||||||||
| 80 | 7 | $self->{'f2'} = 1; | |||||||||||||||||||||||||||
| 81 | } | ||||||||||||||||||||||||||||
| 82 | 273 | ▶ | sub next { | ||||||||||||||||||||||||||
|
Subroutine
next: called CC=2 SCAR=6.9
Pod
documented
| |||||||||||||||||||||||||||||
| 83 | 273 | 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 | $self->{'f0'}+$self->{'f1'}+$self->{'f2'}); | |||||||||||||||||||||||||||
| 93 | |||||||||||||||||||||||||||||
| 94 | 273 | ▶ | if ($ret == $uv_limit) { | ||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||
| 95 | ### go to bigint f2 ... | ||||||||||||||||||||||||||||
| 96 | 2 | $self->{'f2'} = Math::NumSeq::_to_bigint($self->{'f2'}); | |||||||||||||||||||||||||||
| 97 | } | ||||||||||||||||||||||||||||
| 98 | |||||||||||||||||||||||||||||
| 99 | 273 | return ($self->{'i'}++, $ret); | |||||||||||||||||||||||||||
| 100 | } | ||||||||||||||||||||||||||||
| 101 | |||||||||||||||||||||||||||||
| 102 | 24 | ▶ | sub value_to_i_estimate { | ||||||||||||||||||||||||||
|
Subroutine
value_to_i_estimate: called CC=3 SCAR=11.1
Pod
documented
| |||||||||||||||||||||||||||||
| 103 | 24 | my ($self, $value) = @_; | |||||||||||||||||||||||||||
| 104 | |||||||||||||||||||||||||||||
| 105 | 24 | ▶ | if (_is_infinite($value)) { | ||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||
| 106 | 0 | return $value; | |||||||||||||||||||||||||||
| 107 | } | ||||||||||||||||||||||||||||
| 108 | |||||||||||||||||||||||||||||
| 109 | 24 | my $f0 = my $f1 = ($value * 0); # inherit bignum 0 | |||||||||||||||||||||||||||
| 110 | 24 | my $f2 = $f0 + 1; # inherit bignum 1 | |||||||||||||||||||||||||||
| 111 | |||||||||||||||||||||||||||||
| 112 | 24 | my $i = 0; | |||||||||||||||||||||||||||
| 113 | 24 | for (;;) { | |||||||||||||||||||||||||||
| 114 | 108 | ▶ | if ($value <= $f0) { | ||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||
| 115 | 24 | return $i; | |||||||||||||||||||||||||||
| 116 | } | ||||||||||||||||||||||||||||
| 117 | 84 | ($f0,$f1,$f2) = ($f1,$f2, $f0+$f1+$f2); | |||||||||||||||||||||||||||
| 118 | 84 | $i++; | |||||||||||||||||||||||||||
| 119 | } | ||||||||||||||||||||||||||||
| 120 | } | ||||||||||||||||||||||||||||
| 121 | |||||||||||||||||||||||||||||
| 122 | 2 | 1; | |||||||||||||||||||||||||||
| 123 | __END__ | ||||||||||||||||||||||||||||