NumSeq/SqrtEngel.pm

filter: Statementstmt 95.7% 68 / 71 Branchbran 66.6% 8 / 12 Conditioncond n/a MC/DCmcdc n/a Subroutinesub 94.1% 16 / 17 Podpod 100% 4 / 4 totaltotal 92.3% 96 / 104 CC 7 SCAR 8.0
CC
7
Cov
92%
values_max
6.0
next
4.0
rewind
3.0
CRAP 2.2
« NumSeq/Emirps.pm ↑ Summary NumSeq/Squares.pm »
1 # Copyright 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::SqrtEngel;
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;
Subroutine BEGIN: called CC=1 SCAR=0.0
25 2 @ISA = ('Math::NumSeq');
26  
27 2 ▶use Math::NumSeq::Squares;
Subroutine BEGIN: called CC=1 SCAR=0.0
28  
29 # uncomment this to run the ### lines
30 #use Smart::Comments;
31  
32  
33 # use constant name => Math::NumSeq::__('Sqrt Engel Expansion');
34 2 ▶use constant description => Math::NumSeq::__('Engel expansion for a square root.');
Subroutine BEGIN: called CC=1 SCAR=0.0
35 2 ▶use constant characteristic_increasing => 0; # in general
Subroutine BEGIN: called CC=1 SCAR=0.0
36 2 ▶use constant characteristic_non_decreasing => 1;
Subroutine BEGIN: called CC=1 SCAR=0.0
37 2 ▶use constant characteristic_integer => 1;
Subroutine BEGIN: called CC=1 SCAR=0.0
38 2 ▶use constant i_start => 1;
Subroutine BEGIN: called CC=1 SCAR=0.0
39  
40 2 ▶use Math::NumSeq::SqrtDigits;
Subroutine BEGIN: called CC=1 SCAR=0.0
41 2 ▶use constant parameter_info_array =>
Subroutine BEGIN: called CC=1 SCAR=0.0
42 [
43 2 Math::NumSeq::SqrtDigits->parameter_info_hash->{'sqrt'},
44 2 ];
45  
46 2 ▶use constant values_min => 1;
Subroutine BEGIN: called CC=1 SCAR=0.0
47 0 ▶sub values_max {
Subroutine values_max: not called CC=2 SCAR=17.9
Pod documented
48 0 my ($self) = @_;
49 0 ▶ return ($self->Math::NumSeq::Squares::pred($self->{'sqrt'})
Branch: 1 branch
BranchTrueFalseTotal
$self->Math::NumSeq::Squares::pred($self->{'sqrt'}) ? : 0 0 0
50 ? 1 # perfect square, only some 1s
51 : undef);
52 }
53  
54 # cf A028259 of phi=(sqrt(5)+1)/2 golden ratio
55 # A068388 of sqrt(3/2)
56 # A059178 cube root 2
57 # A059179 cube root 3
58 #
59 2 my @oeis_anum = (
60 # OEIS-Catalogue array begin
61 undef, # 0
62 undef, # 1
63 'A028254', # # 2
64 'A028257', # sqrt=3
65 undef, # 4
66 'A059176', # sqrt=5
67 undef, # 6
68 'A161368', # sqrt=7
69 undef, # 8
70 undef, # 9
71 'A059177', # sqrt=10
72 # OEIS-Catalogue array end
73 );
74 3 ▶sub oeis_anum {
Subroutine oeis_anum: called CC=1 SCAR=0.0
Pod documented
75 3 my ($self) = @_;
76 3 return $oeis_anum[$self->{'sqrt'}];
77 }
78  
79 # a/b + 1/(b*v) = sqrt(s)
80 # a + 1/v = b*sqrt(s)
81 # 1/v = b*sqrt(s) - a
82 # v = 1 / (b*sqrt(s) - a)
83 # = (b*sqrt(s) + a) / (b*sqrt(s) - a)*(b*sqrt(s) + a)
84 # = (b*sqrt(s) + a) / (b^2*s - a^2)
85 # = (sqrt(s*b^2) + a) / (s*b^2 - a^2)
86 # round up v
87 # sqrt(sb2) never an integer
88 # bigint sqrt rounds down so +1 to round up
89 # division add den-1 to round up
90 # so add 1+den-1=den means
91 # v = floor( (floor(sqrt(s*b^2)) + a) / (s*b^2 - a^2) ) + 1
92 #
93 # a/b + 1/bv < sqrt(s)
94 # a + 1/v < b*sqrt(s)
95 # a^2 + 2a/v + 1/v^2 < s*b^2
96 # a^2*v^2 + 2a*v + 1 < s*b^2*v^2
97 #
98 # a/b < sqrt(s)
99 # a < b*sqrt(s)
100 # a^2 < s*b^2
101 #
102 29 ▶sub rewind {
Subroutine rewind: called CC=3 SCAR=11.1
Pod documented
103 29 my ($self) = @_;
104 29 $self->{'i'} = $self->i_start;
105  
106 29 my $sqrt = $self->{'sqrt'};
107 29 ▶ if ($sqrt <= 0) {
Branch: 1 branch
BranchTrueFalseTotal
if ($sqrt <= 0) { } 0 29 29
108 0 $self->{'a'} = 0;
109 } else {
110 29 my $root = sqrt($sqrt);
111 29 ▶ if ($root == int($root)) {
Branch: 1 branch
BranchTrueFalseTotal
if ($root == int $root) { } 9 20 29
112 # perfect square
113 9 $self->{'perfect_square'} = 1;
114 9 $self->{'a'} = $root;
115 } else {
116 # start 0/1 a=0,b=1, so sb2=s*b^2=s
117 20 $self->{'a'} = Math::NumSeq::_to_bigint(0);
118 20 $self->{'sb2'} = Math::NumSeq::_to_bigint($sqrt);
119 }
120 }
121 }
122 192 ▶sub next {
Subroutine next: called CC=4 SCAR=13.9
Pod documented
123 192 my ($self) = @_;
124 ### SqrtEngel next() ...
125  
126 192 my $a = $self->{'a'};
127 192 my $value;
128 192 ▶ if ($self->{'perfect_square'}) {
Branch: 1 branch
BranchTrueFalseTotal
if ($self->{'perfect_square'}) { } 22 170 192
129 22 ▶ if ($a) {
Branch: 1 branch
BranchTrueFalseTotal
if ($a) { } 19 3 22
130 19 $value = 1;
131 19 $self->{'a'} -= 1;
132 } else {
133 # perfect square no more terms
134 3 return;
135 }
136 } else {
137 ### a: "$self->{'a'}"
138 ### sb2: "$self->{'sb2'}"
139 ### b: "".sqrt($self->{'sb2'} / $self->{'sqrt'})
140 ### assert: $self->{'a'} * $self->{'a'} <= $self->{'sb2'}
141 ### num: (sqrt($self->{'sb2'}) + $self->{'a'}).''
142 ### den: ($self->{'sb2'} - $self->{'a'}**2).''
143  
144 # always "+ 1" to round up because sqrt() is not an integer so the
145 # numerator is not divisible by the denominator
146 #
147 170 $value = (sqrt($self->{'sb2'}) + $a) / ($self->{'sb2'} - $a*$a) + 1;
148 170 $self->{'a'} = $a*$value + 1;
149 170 $self->{'sb2'} *= $value * $value;
150  
151 ### new value: "$value"
152 ### assert: $self->{'a'} * $self->{'a'} <= $self->{'sb2'}
153  
154 170 ▶ if ($value <= ~0) {
Branch: 1 branch
BranchTrueFalseTotal
if ($value <= '18446744073709551615') 170 0 170
155 170 $value = $value->numify;
156 }
157 }
158  
159 189 return ($self->{'i'}++, $value);
160 }
161  
162 # ### assert: $self->{'a'} ** 2 * $value ** 2 + 2 * $self->{'a'} * $value + 1 < $self->{'sb2'} * $value ** 2
163  
164  
165 # a/b + 1/bv + 1/bvw < sqrt(s)
166 # 1/bvw < sqrt(s) - a/b - 1/bv
167 # 1/w < bv*sqrt(s) - bv*a/b - bv/bv
168 # 1/w < bv*sqrt(s) - v*a - 1
169 # 1/w < v*(b*sqrt(s) - a) - 1
170 #
171 # 1/bv + 1/bvw
172 # = 1/bv + 1/bvw + 1/bw - 1/bw
173 # = 1/bw + 1/bvw + (1/bv - 1/bw)
174 # = 1/bw + 1/bvw + w/bvw - v/bvw
175 # = 1/bw + (1+w-v)/bvw
176 #
177 # 1/bv+1/bv1, should have had smaller v at previous stage
178 # 1/bv < sqrt 1/b(v-1) > sqrt
179 # sqrt-1/bv > 0
180 #
181 # 1/bv+1/bv(v-1)
182 # = 1/bv * (1 + 1/(v-1))
183 #
184 # 1/bv < t < 1/b(v-1)
185 # 1/bv + 1/bvw < t < 1/bv + 1/bv(w-1)
186 # 1/bvw < t-1/bv < 1/bv(w-1)
187 #
188 # sqrt(2) - (1 + 1/3 + 1/3*5) > 0
189 # sqrt(2) - (1 + 1/3 + 1/3*6)
190 # = sqrt(2) - 25/18
191 #
192 # R = t - (a/b + 1/bv) > 0
193 # bvR = bvt - (bva/b + bv/bv)
194 # = bvt - (va + 1) > 0
195 # bvwR = tbvw - (avw + w)
196 # bvt - (va + 1) > 0
197 # bvt > (va + 1)
198  
199 # t - (a/b + 1/b(v-1)) < 0
200 # bvt - (bva/b + bv/b(v-1)) < 0
201 # bvt - (va + v/(v-1)) < 0
202 # bvt < (va + v/(v-1))
203 #
204 # S = t - (a/b + 1/bv + 1/bvw) > 0
205 # bvwS = tbvw - (bvwa/b + bvw/bv + bvw/bvw)
206 # = tbvw - (vwa + w + 1) > 0
207  
208  
209  
210 2 1;
211 __END__
« NumSeq/Emirps.pm ↑ Summary NumSeq/Squares.pm »