File Coverage

blib/lib/Math/NumSeq/FractionDigits.pm
Criterion Covered Total %
statement 106 114 92.9
branch 17 24 70.8
condition 8 36 22.2
subroutine 17 17 100.0
pod 5 5 100.0
total 153 196 78.0


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::FractionDigits;
19 2     2   89521 use 5.004;
  2         11  
  2         122  
20 2     2   16 use strict;
  2         3  
  2         95  
21 2     2   12 use List::Util 'max';
  2         4  
  2         208  
22              
23 2     2   653 use Math::NumSeq;
  2         4  
  2         125  
24             *_is_infinite = \&Math::NumSeq::_is_infinite;
25             *_to_bigint = \&Math::NumSeq::_to_bigint;
26              
27 2     2   13 use vars '$VERSION', '@ISA';
  2         4  
  2         126  
28             $VERSION = 71;
29 2     2   516 use Math::NumSeq::Base::Digits;
  2         5  
  2         152  
30             @ISA = ('Math::NumSeq::Base::Digits');
31              
32             # uncomment this to run the ### lines
33             #use Smart::Comments;
34              
35              
36             # use constant name => Math::NumSeq::__('Fraction Digits');
37 2     2   13 use constant description => Math::NumSeq::__('A given fraction number written out in binary.');
  2         3  
  2         10  
38 2     2   10 use constant i_start => 0;
  2         4  
  2         194  
39              
40 2         16 use constant parameter_info_array =>
41             [ Math::NumSeq::Base::Digits->parameter_info_list,
42             { name => 'fraction',
43             display => Math::NumSeq::__('Fraction'),
44             type => 'string',
45             type_hint => 'fraction',
46             width => 10,
47             default => '5/29', # an arbitrary choice
48             description => Math::NumSeq::__('The fraction to show, for example 5/29. Press Return when ready to display the expression.'),
49             },
50 2     2   11 ];
  2         11  
51              
52             #------------------------------------------------------------------------------
53              
54             my @oeis_anum;
55              
56             $oeis_anum[10] =
57             {
58             # Any fixed-length repeating sequence is a fraction of some sort in
59             # some radix. There's many more not expressed here, and constant
60             # digits sequences can be done by more than one fraction, etc.
61              
62             '1/7' => 'A020806', # 1/7 decimal
63             # OEIS-Catalogue: A020806 fraction=1/7
64              
65             # OFFSET=1, unlike other fractions which are OFFSET=0
66             # # '22/7' => 'A068028', # 22/7 decimal
67             # # # OEIS-Catalogue: A068028 fraction=22/7
68              
69             '1/9' => 'A000012', # 1/9 decimal, is just 1,1,1,1
70             # pending something better for a constant sequence
71             # OEIS-Catalogue: A000012 fraction=1/9
72              
73             '1/11' => 'A010680', # 1/11 decimal
74             # OEIS-Catalogue: A010680 fraction=1/11
75              
76             # OEIS-Catalogue: A021015 fraction=1/11 # duplicate of A010680
77             # OEIS-Catalogue: A021016 fraction=1/12
78             # OEIS-Catalogue: A021017 fraction=1/13
79             # OEIS-Catalogue: A021018 fraction=1/14
80             # OEIS-Catalogue: A021019 fraction=1/15
81             # OEIS-Catalogue: A021020 fraction=1/16
82              
83             '1/17' => 'A007450', # 1/17 decimal
84             # OEIS-Catalogue: A007450 fraction=1/17
85              
86             # Math::NumSeq::OEIS::Catalogue::Plugin::FractionDigits has A021022
87             # through A021999, being 1/18 to 1/995.
88             # A022000 is not 1/996, that fraction missing apparently.
89             #
90             # OEIS-Catalogue: A022001 fraction=1/997
91             # OEIS-Catalogue: A022002 fraction=1/998
92             # OEIS-Catalogue: A022003 fraction=1/999
93              
94             # OFFSET ?
95             # '1/999999' => 'A172051',
96             # # OEIS-Catalogue: A172051 fraction=1/999999
97              
98             #---------------
99              
100             # extra 10 in the denominator to give the leading 0
101             '13717421/1111111110' => 'A010888', # .012345678912...
102             # OEIS-Catalogue: A010888 fraction=13717421/1111111110
103              
104             #---------------
105              
106             # constant digits 3,3,3,...
107             '10/3' => 'A010701',
108             # ENHANCE-ME: of course can generate 3s more efficiently just as a
109             # constant sequence, in which case would prefer that over this for the
110             # catalogue.
111             # OEIS-Catalogue: A010701 fraction=10/3
112             };
113             sub oeis_anum {
114 1     1 1 7 my ($self) = @_;
115             ### oeis_anum() ...
116 1         3 my $radix = $self->{'radix'};
117 1         4 my $fraction = $self->{'fraction'};
118 1 50       9 if (my $anum = $oeis_anum[$radix]->{$fraction}) {
119 1         4 return $anum;
120             }
121 0 0 0     0 if ($radix == 10
      0        
      0        
      0        
      0        
      0        
      0        
122             && $fraction =~ m{(\d+)/(\d+)}
123             && $1 == 1
124             && $2 >= 12 && $2 <= 999 && $2 != 996
125             && ($2 % 10) != 0
126             && $2 != 25) {
127 0         0 return 'A0'.($2 + 21016-12);
128             }
129             ### $fraction
130 0         0 return undef;
131             }
132              
133             #------------------------------------------------------------------------------
134              
135             sub new {
136 3     3 1 574 my $self = shift->SUPER::new(@_);
137              
138 3         6 my $radix = $self->{'radix'};
139 3         7 my $fraction = $self->{'fraction'};
140              
141 3         4 my $num = 0; # 0/0 if unrecognised
142 3         5 my $den = 0;
143 3         26 ($num, $den) = ($fraction =~ m{^\s*
144             ([.[:digit:]]+)?
145             \s*
146             (?:/\s*
147             ([.[:digit:]]+)?
148             )?
149             \s*$}x);
150 3 50       12 if (! defined $num) { $num = 1; }
  0         0  
151 3 50       11 if (! defined $den) { $den = 1; }
  0         0  
152             ### $num
153             ### $den
154 3         7 $fraction = "$num/$den";
155              
156             # decimals like 1.5/2.75 become 150/275
157             {
158 3         6 ($num, my $num_decimals) = _to_int_and_decimals ($num);
  3         8  
159 3         11 ($den, my $den_decimals) = _to_int_and_decimals ($den);
160 3         21 $num .= '0' x max(0, $den_decimals - $num_decimals);
161 3         10 $den .= '0' x max(0, $num_decimals - $den_decimals);
162             }
163              
164 3 100       28 if (max(length($num),length($den)) >= length(int (~0 / $radix))) {
165 1         4 $num = _to_bigint($num);
166 1         103 $den = _to_bigint($den);
167             }
168              
169             # increase den so first digit is 0 to radix-1
170 3   33     51 while ($den != 0 && $num >= $den) {
171 0         0 $den *= $radix;
172             }
173              
174             ### create
175             ### $num
176             ### $den
177 3         207 $self->{'fraction'} = $fraction;
178 3         6 $self->{'initial_num'} = $num;
179 3         8 $self->{'den'} = $den;
180              
181 3         9 $self->rewind;
182 3         9 return $self;
183             }
184              
185             sub _to_int_and_decimals {
186 14     14   2558 my ($n) = @_;
187 14 100       60 if ($n =~ m{^(\d*)\.(\d*?)0*$}) {
188 7         32 return ($1 . $2,
189             length($2));
190             } else {
191 7         20 return ($n, 0);
192             }
193             }
194              
195             sub rewind {
196 8     8 1 640 my ($self) = @_;
197 8         34 $self->{'i'} = $self->i_start;
198 8         28 $self->{'num'} = $self->{'initial_num'};
199             }
200              
201             sub next {
202 144     144 1 10945 my ($self) = @_;
203              
204 144   50     353 my $num = $self->{'num'} || return; # num==0 exact radix frac
205 144   50     2916 my $den = $self->{'den'} || return; # den==0 invalid
206 144         2645 my $radix = $self->{'radix'};
207             ### FractionDigits next(): "$self->{'i'} $num/$den"
208              
209 144         279 $num *= $radix;
210 144         14213 my $quot = int ($num / $den);
211 144         17962 $self->{'num'} = $num - $quot * $den;
212              
213             ### $quot
214             ### rem: $self->{'num'}
215              
216 144         22381 return ($self->{'i'}++, $quot);
217             }
218              
219             sub ith {
220 39     39 1 117 my ($self, $i) = @_;
221              
222 39 100 66     144 if ($i < 0 || _is_infinite($i)) {
223 3         10 return undef;
224             }
225              
226 36         75 my $radix = $self->{'radix'};
227 36         77 my $den = $self->{'den'};
228 36         79 my $num = (($self->{'initial_num'} * _modpow ($self->{'radix'}, $i, $den))
229             % $den);
230 36         135 return int (($num * $radix) / $den);
231             }
232              
233 2         10 use constant 1.02 _UV_MAX_SQRT => do {
234 2         5 my $uv_max = ~0;
235 2         5 my $bit = 1;
236 2         4 my $shift = 0;
237 2         4 for (;;) {
238 64         46 $shift++;
239 64         102 my $try_bit = $bit << 1;
240 64 100       108 if ($uv_max >> $shift < $try_bit) {
241 2         7 last;
242             }
243 62         69 $bit = $try_bit;
244             }
245             ### $bit
246              
247 2         3 my $uv_max_sqrt = $bit;
248 2         3 for (;;) {
249 64         63 $bit >>= 1;
250 64 100       99 last if $bit == 0;
251 62         59 my $try_sqrt = $uv_max_sqrt + $bit;
252 62 50       114 if (int($uv_max / $try_sqrt) <= $try_sqrt) {
253 0         0 $uv_max_sqrt = $try_sqrt;
254             }
255             }
256              
257             ### $uv_max_sqrt
258             ### uv_max_sqrt: sprintf '%#X', $uv_max_sqrt
259             ### squared: $uv_max_sqrt*$uv_max_sqrt
260             ### squared: sprintf '%#X', $uv_max_sqrt*$uv_max_sqrt
261              
262 2         476 $uv_max_sqrt
263 2     2   16 };
  2         49  
264              
265             sub _modpow {
266 56     56   46489 my ($base, $exp, $mod) = @_;
267             ### _modpow(): "$base $exp $mod"
268              
269 56         71 my $ret = 1;
270 56 50 33     241 if (ref $mod || $mod > _UV_MAX_SQRT) {
271 0         0 return _to_bigint($base)->bmodpow($exp,$mod);
272             }
273              
274             # only if base and mod have no common factor ...
275             # $exp %= $mod-1;
276              
277 56         70 my $power = $base;
278 56         64 for (;;) {
279             ### $exp
280 160 100       298 if ($exp % 2) {
281             ### step: "power=$power"
282 91         110 $ret = ($ret * $power) % $mod;
283             }
284 160   100     334 $exp = int($exp/2) || last;
285 104         124 $power = ($power*$power) % $mod;
286             }
287 56         164 return $ret;
288             }
289              
290              
291             # ENHANCE-ME: only some digits occur, being the modulo den residue class
292             # containing num.
293             # sub pred {
294             # my ($self, $value) = @_;
295             # }
296             #
297             # =item C<$bool = $seq-Epred($value)>
298             #
299             # Return true if C<$value> occurs as a digit in the fraction.
300              
301             1;
302             __END__