NumSeq/SternDiatomic.pm

filter: Statementstmt 98.6% 71 / 72 Branchbran 87.5% 7 / 8 Conditioncond 33.3% 1 / 3 MC/DCmcdc 0.0% 0 / 2 Subroutinesub 100% 18 / 18 Podpod 100% 6 / 6 totaltotal 94.5% 103 / 109 CC 7 SCAR 8.6
CC
7
Cov
95%
ith_pair
6.0
pred
2.3
BEGIN
1.0
CRAP 2.4
« NumSeq/Base/Sparse.pm ↑ Summary NumSeq/SelfLengthCumulative.pm »
1 # Copyright 2011, 2012, 2013, 2014, 2016, 2017, 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  
19 # Edsgar Dijkstra
20 # http://www.cs.utexas.edu/users/EWD/ewd05xx/EWD570.PDF
21 # http://www.cs.utexas.edu/users/EWD/ewd05xx/EWD578.PDF
22  
23 # Some Properties of a Function Studied by De Rham, Carlitz and Dijkstra and
24 # its Relation to the Eisenstein-Stern's Diatomic Sequence
25 # I. Urhiba, Math. Comm. 6 2001 181-198
26  
27 # Lind, Stern summary
28 # "An Extension of Stern'S Diatomic Sequence", Duke Math J 36
29 # 1969 55-60
30  
31  
32 package Math::NumSeq::SternDiatomic;
33 2 ▶use 5.004;
Subroutine BEGIN: called CC=1 SCAR=0.0
34 2 ▶use strict;
Subroutine BEGIN: called CC=1 SCAR=0.0
35  
36 2 ▶use vars '$VERSION', '@ISA';
Subroutine BEGIN: called CC=1 SCAR=0.0
37 2 $VERSION = 75;
38 2 ▶use Math::NumSeq;
Subroutine BEGIN: called CC=1 SCAR=0.0
39 2 @ISA = ('Math::NumSeq');
40 2 *_is_infinite = \&Math::NumSeq::_is_infinite;
41  
42 2 ▶use Math::NumSeq::Fibonacci;
Subroutine BEGIN: called CC=1 SCAR=0.0
43 2 *_bit_split_hightolow = \&Math::NumSeq::Fibonacci::_bit_split_hightolow;
44  
45 # uncomment this to run the ### lines
46 #use Smart::Comments;
47  
48 # use constant name => Math::NumSeq::__('Stern Diatomic');
49 2 ▶use constant description => Math::NumSeq::__('Stern\'s diatomic sequence.');
Subroutine BEGIN: called CC=1 SCAR=0.0
50 2 ▶use constant default_i_start => 0;
Subroutine BEGIN: called CC=1 SCAR=0.0
51 2 ▶use constant values_min => 0;
Subroutine BEGIN: called CC=1 SCAR=0.0
52 2 ▶use constant characteristic_smaller => 1;
Subroutine BEGIN: called CC=1 SCAR=0.0
53 2 ▶use constant characteristic_increasing => 0;
Subroutine BEGIN: called CC=1 SCAR=0.0
54 2 ▶use constant characteristic_integer => 1;
Subroutine BEGIN: called CC=1 SCAR=0.0
55  
56 #------------------------------------------------------------------------------
57 # cf A126606 - starting 0,2 gives 2*diatomic
58 # A049455 - repeat 0..2^k
59 # A049456 - extra 1 at end of each row
60 # A174980 - type ([0,1],1), adding 1 extra at n=2^k
61 # A049455,A049456 stern/farey tree
62 # A070878 stern by rows
63 # A070879 stern by rows
64 # http://oeis.org/stern_brocot.html
65 #
66 # cf Michael Somos iteration in A002487
67 2 ▶use constant oeis_anum => 'A002487';
Subroutine BEGIN: called CC=1 SCAR=0.0
68  
69 #------------------------------------------------------------------------------
70  
71 4 ▶sub rewind {
Subroutine rewind: called CC=1 SCAR=0.0
Pod documented
72 4 my ($self) = @_;
73 4 $self->{'i'} = $self->i_start;
74 4 $self->{'p'} = 0;
75 4 $self->{'q'} = 1;
76 }
77 12 ▶sub seek_to_i {
Subroutine seek_to_i: called CC=1 SCAR=0.0
Pod documented
78 12 my ($self, $i) = @_;
79 12 $self->{'i'} = $i;
80 12 ($self->{'p'},$self->{'q'}) = $self->ith_pair($i);
81 }
82  
83 203 ▶sub next {
Subroutine next: called CC=1 SCAR=0.0
Pod documented
84 203 my ($self) = @_;
85 203 my $p = $self->{'p'};
86 203 my $q = $self->{'q'};
87 203 $self->{'p'} = $q;
88 203 $self->{'q'} = $p + $q - 2*($p % $q);
89 203 return ($self->{'i'}++, $p);
90 }
91  
92 17 ▶sub ith {
Subroutine ith: called CC=1 SCAR=0.0
Pod documented
93 17 my ($self, $i) = @_;
94 17 return ($self->ith_pair($i))[0];
95 }
96  
97 # Return ($value[i], $value[i+1]).
98 40 ▶sub ith_pair {
Subroutine ith_pair: called CC=6 SCAR=18.0
Pod documented
99 40 my ($self, $i) = @_;
100 ### SternDiatomic _ith_pair(): "$i"
101  
102 40 ▶ if ($i < 0) {
Branch: 1 branch
BranchTrueFalseTotal
if ($i < 0) 3 37 40
103 3 ▶ if ($i < -1) {
Branch: 1 branch
BranchTrueFalseTotal
if ($i < -1) { } 1 2 3
104 1 return (undef,undef);
105 } else {
106 2 return (undef,0);
107 }
108 }
109 37 ▶ if (_is_infinite($i)) { # don't loop forever if $value is +/-infinity
Branch: 1 branch
BranchTrueFalseTotal
if (_is_infinite($i)) 0 37 37
110 0 return ($i,$i);
111 }
112  
113 37 my $p = ($i * 0); # inherit bignum 0
114 37 my $q = $p + 1; # inherit bignum 1
115  
116 37 foreach my $bit (_bit_split_hightolow($i)) {
117 103 ▶ if ($bit) {
Branch: 1 branch
BranchTrueFalseTotal
if ($bit) { } 60 43 103
118 60 $p += $q;
119 } else {
120 43 $q += $p;
121 }
122 103 $i = int($i/2);
123 }
124  
125 ### result: "$p, $q"
126 37 return ($p,$q);
127 }
128  
129 12 ▶sub pred {
Subroutine pred: called CC=2 SCAR=8.1
Pod documented
130 12 my ($self, $value) = @_;
131 ### SternDiatomic pred(): $value
132 12 ▶ return ($value >= 0 && $value == int($value));
Condition33%1/3
$value >= 0 && $value == int $value
!ll&&!rl&&r
0012
MC/DC0%0/2
$value >= 0 && $value == int $value
$value >= 0 $value == int $value
Truth table33%1/3
A && B
A= $value >= 0B= $value == int $value
ABresult
0X0
100
111
133 }
134  
135 2 1;
136 __END__
« NumSeq/Base/Sparse.pm ↑ Summary NumSeq/SelfLengthCumulative.pm »