| 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
| |||||||||||
| 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
| |||||||||||
| 108 | 0 | $self->{'a'} = 0; | |||||||||
| 109 | } else { | ||||||||||
| 110 | 29 | my $root = sqrt($sqrt); | |||||||||
| 111 | 29 | ▶ | if ($root == int($root)) { | ||||||||
|
Branch: 1 branch
| |||||||||||
| 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
| |||||||||||
| 129 | 22 | ▶ | if ($a) { | ||||||||
|
Branch: 1 branch
| |||||||||||
| 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
| |||||||||||
| 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__ | ||||||||||