Sidef/Math/Math.pm untested

filter: Statementstmt 0.0% 0 / 230 Branchbran 0.0% 0 / 30 Conditioncond 0.0% 0 / 29 MC/DCmcdc 0.0% 0 / 16 Subroutinesub 0.0% 0 / 38 Podpod 0.0% 0 / 33 totaltotal 0.0% 0 / 376 CC 16 SCAR 21.5
CC
16
Cov
0%
linear_recurrence
30.0
for
30.0
linear_recurrence_mod
12.0
CRAP 8.6
1 package Sidef::Math::Math;
2  
3 use utf8;
4 use 5.016;
5 use List::Util qw(all);
6  
7 use parent qw(
8 Sidef::Object::Object
9 );
10  
11 use Sidef::Types::Number::Number;
12  
13 sub new {
14 bless {}, __PACKAGE__;
15 }
16  
17 sub binsplit {
18 my ($self, $block, @list) = @_;
19 Sidef::Types::Number::Number::_binsplit(\@list, $block);
20 }
21  
22 sub binary_exp {
23 my ($self, $r, $x, $n, $block) = @_;
24  
25 ($n->is_int && not $n->is_neg)
26 || return Sidef::Types::Number::Number->nan;
27  
28 foreach my $bit (CORE::reverse(split(//, $n->as_bin))) {
29 $r = $block->run($x, $r) if $bit;
30 $x = $block->run($x, $x);
31 }
32  
33 return $r;
34 }
35  
36 sub gcd {
37 my ($self, @list) = @_;
38 Sidef::Types::Number::Number::gcd(@list);
39 }
40  
41 sub lcm {
42 my ($self, @list) = @_;
43 Sidef::Types::Number::Number::lcm(@list);
44 }
45  
46 sub sum {
47 my ($self, @list) = @_;
48 Sidef::Types::Number::Number::sum(@list);
49 }
50  
51 sub prod {
52 my ($self, @list) = @_;
53 Sidef::Types::Number::Number::prod(@list);
54 }
55  
56 *product = \∏
57  
58 sub max {
59 my ($self, @list) = @_;
60 Sidef::Types::Number::Number::max(@list);
61 }
62  
63 sub min {
64 my ($self, @list) = @_;
65 Sidef::Types::Number::Number::min(@list);
66 }
67  
68 sub arithmetic_mean {
69 my ($self, @list) = @_;
70 Sidef::Types::Number::Number::arithmetic_mean(@list);
71 }
72  
73 *avg = \&arithmetic_mean;
74  
75 sub geometric_mean {
76 my ($self, @list) = @_;
77 Sidef::Types::Number::Number::geometric_mean(@list);
78 }
79  
80 sub harmonic_mean {
81 my ($self, @list) = @_;
82 Sidef::Types::Number::Number::harmonic_mean(@list);
83 }
84  
85 sub median {
86 my ($self, @list) = @_;
87 Sidef::Types::Number::Number::median(@list);
88 }
89  
90 sub variance {
91 my ($self, @list) = @_;
92 Sidef::Types::Number::Number::variance(@list);
93 }
94  
95 sub stddev {
96 my ($self, @list) = @_;
97 Sidef::Types::Number::Number::stddev(@list);
98 }
99  
100 sub solve_seq {
101 my ($self, $seq, $offset) = @_;
102 $seq->solve_seq($offset);
103 }
104  
105 sub solve_rec_seq {
106 my ($self, $seq) = @_;
107 $seq->solve_rec_seq;
108 }
109  
110 *find_linear_recurrence = \&solve_rec_seq;
111  
112 sub linear_recurrence_matrix {
113 my ($self, $ker) = @_;
114  
115 my @A;
116 my $end = $#{$ker};
117  
118 foreach my $i (0 .. $end - 1) {
119 foreach my $j (0 .. $end) {
120 $A[$i][$j] =
121 ($i + 1 == $j)
122 ? Sidef::Types::Number::Number::ONE
123 : Sidef::Types::Number::Number::ZERO;
124 }
125 }
126  
127 my $A = Sidef::Types::Array::Matrix->new(@A);
128 $A->set_row($end, Sidef::Types::Array::Array->new([CORE::reverse(@$ker)]));
129 return $A;
130 }
131  
132 sub linear_recurrence {
133 my ($self, $ker, $init, $n_min, $n_max) = @_;
134  
135 # Fast path for integers
136 if ($n_min->ge(Sidef::Types::Number::Number::ZERO)
137 and (all { $_->is_int } (@$ker, @$init))) {
138 return Sidef::Types::Number::Number::_linear_recurrence_mpz($ker, $init, $n_min, $n_max);
139 }
140  
141 my $want_array = 1;
142  
143 if (!defined($n_max)) {
144 $n_max = $n_min;
145 $want_array = 0;
146 }
147  
148 my @init_terms = @$init;
149  
150 if ($#init_terms > $#{$ker}) {
151 $#init_terms = $#{$ker};
152 }
153  
154 my $A = $self->linear_recurrence_matrix($ker);
155 my $B = Sidef::Types::Array::Matrix->column_vector(@init_terms);
156  
157 my $C = $A->pow($n_min)->mul($B);
158 my @seq = @{$C->transpose->row(0)};
159  
160 my $result = Sidef::Types::Range::RangeNumber->new($n_min, $n_max)->map(
161 Sidef::Types::Block::Block->new(
162 code => sub {
163 CORE::push(@seq, Sidef::Types::Number::Number::sum(map { $ker->[$_]->mul($seq[-$_ - 1]) } 0 .. $#seq));
164 CORE::shift(@seq);
165 }
166 )
167 );
168  
169 $result = $result->[0] if !$want_array;
170 return $result;
171 }
172  
173 *linear_rec = \&linear_recurrence;
174  
175 sub linear_recurrence_mod {
176 my ($self, $ker, $init, $n, $m) = @_;
177  
178 # Fast path for integers
179 if ($n->ge(Sidef::Types::Number::Number::ZERO)
180 and (all { $_->is_int } (@$ker, @$init))) {
181 return Sidef::Types::Number::Number::_linear_recurrence_mod_mpz($ker, $init, $n, $m);
182 }
183  
184 my @init_terms = @$init;
185  
186 if ($#init_terms > $#{$ker}) {
187 $#init_terms = $#{$ker};
188 }
189  
190 my $A = $self->linear_recurrence_matrix($ker);
191 my $B = Sidef::Types::Array::Matrix->column_vector(@init_terms);
192  
193 my $C = $A->powmod($n, $m)->mul($B);
194 my @seq = @{$C->transpose->row(0)};
195  
196 $seq[0]->mod($m);
197 }
198  
199 *linear_recmod = \&linear_recurrence_mod;
200  
201 sub product_tree {
202 my ($self, @list) = @_;
203  
204 # Algorithm from: https://facthacks.cr.yp.to/product.html
205  
206 my @result = Sidef::Types::Array::Array->new([@list]);
207  
208 while (scalar(@list) > 1) {
209 @list =
210 map { Sidef::Types::Number::Number::prod(@list[($_ << 1) .. List::Util::min($#list, (($_ + 1) << 1) - 1)]) } 0 .. (((scalar(@list) + 1) >> 1) - 1);
211  
212 push @result, Sidef::Types::Array::Array->new([@list]);
213 }
214  
215 Sidef::Types::Array::Array->new(\@result);
216 }
217  
218 sub remainders {
219 my ($self, $n, $arr) = @_;
220  
221 # Algorithm from: https://facthacks.cr.yp.to/remainder.html
222  
223 my @result = ($n);
224  
225 foreach my $t (@{$self->product_tree(@$arr)->flip}) {
226 @result = map { $result[$_ >> 1]->mod($t->[$_]) } 0 .. $#{$t};
227 }
228  
229 Sidef::Types::Array::Array->new(\@result);
230 }
231  
232 sub batch_gcd {
233 my ($self, @X) = @_;
234  
235 # Algorithm from: https://facthacks.cr.yp.to/batchgcd.html
236  
237 my $prods = $self->product_tree(@X);
238 my @R = @{pop(@$prods) // return Sidef::Types::Array::Array->new()};
239  
240 while (@$prods) {
241 @X = @{pop(@$prods)};
242 @R = map { $R[$_ >> 1]->mod($X[$_]->sqr) } 0 .. $#X;
243 }
244  
245 Sidef::Types::Array::Array->new([map { Sidef::Types::Number::Number::gcd($R[$_]->idiv($X[$_]), $X[$_]) } 0 .. $#R]);
246 }
247  
248 sub batch_invmod {
249 my ($self, $x, $n) = @_;
250  
251 # Algorithm 2.11 MultipleInversion from Modern Computer Arithmetic
252  
253 @$x || return Sidef::Types::Array::Array->new;
254  
255 my $k = $#{$x};
256 my @z = ($x->[0]);
257  
258 foreach my $i (1 .. $k) {
259 $z[$i] = ($z[$i - 1]->mulmod($x->[$i], $n));
260 }
261  
262 my @y;
263 my $q = $z[$k]->invmod($n);
264  
265 for (my $i = $k ; $i >= 1 ; --$i) {
266 $y[$i] = $q->mulmod($z[$i - 1], $n);
267 $q = $q->mulmod($x->[$i], $n);
268 }
269  
270 $y[0] = $q;
271 Sidef::Types::Array::Array->new(\@y);
272 }
273  
274 sub gcd_factors {
275 my ($self, $n, $arr) = @_;
276 Sidef::Types::Number::Number::gcd_factors($n, $arr);
277 }
278  
279 sub smooth_numbers {
280 my ($self, @primes) = @_;
281  
282 my @s = map { [Sidef::Types::Number::Number::ONE] } @primes;
283  
284 Sidef::Object::Enumerator->new(
285 Sidef::Types::Block::Block->new(
286 code => sub {
287 my ($callback) = @_;
288  
289 while (1) {
290 my $n = Sidef::Types::Number::Number::min(map { $_->[0] } @s);
291  
292 for my $i (0 .. $#primes) {
293 shift(@{$s[$i]}) if $s[$i][0]->eq($n);
294 push(@{$s[$i]}, $n->mul($primes[$i]));
295 }
296  
297 $callback->run($n);
298 }
299 }
300 )
301 );
302 }
303  
304 sub seq {
305 my ($self, @args) = @_;
306 my $block = pop(@args);
307  
308 my @seq = (@args);
309 my $array = Sidef::Types::Array::Array->new(\@seq);
310  
311 Sidef::Object::Enumerator->new(
312 Sidef::Types::Block::Block->new(
313 code => sub {
314 my ($callback) = @_;
315  
316 foreach my $n (@seq) {
317 $callback->run($n);
318 }
319  
320 my $index = scalar(@seq);
321  
322 if (!@seq) {
323 push @seq, Sidef::Types::Number::Number::ZERO;
324 }
325  
326 while (1) {
327 ++$index;
328 my $r = $block->run($array, Sidef::Types::Number::Number::_set_int($index));
329 push @seq, $r;
330 $callback->run($r);
331 }
332 }
333 )
334 );
335 }
336  
337 sub for {
338 my ($self, $initial, $condition, $next_term) = @_;
339  
340 my $n = $initial;
341  
342 Sidef::Object::Enumerator->new(
343 Sidef::Types::Block::Block->new(
344 code => sub {
345 my ($callback) = @_;
346  
347 if (defined($condition) ? $condition->run($n) : 1) {
348 $callback->run($n);
349 }
350 else {
351 return;
352 }
353  
354 while (1) {
355 $n = $next_term->run($n);
356 if (defined($condition) ? $condition->run($n) : 1) {
357 $callback->run($n);
358 }
359 else {
360 last;
361 }
362 }
363 }
364 )
365 );
366 }
367  
368 sub chinese {
369 my ($self, @arrs) = @_;
370  
371 my @pairs;
372 foreach my $pair (@arrs) {
373 if ( Scalar::Util::reftype($pair) eq 'ARRAY'
374 and @$pair == 2
375 and ref($pair->[0]) eq 'Sidef::Types::Number::Number'
376 and ref($pair->[1]) eq 'Sidef::Types::Number::Number') {
377 push @pairs, [map { Sidef::Types::Number::Number::_big2istr($$_) } @$pair];
378 }
379 else {
380 return Sidef::Types::Number::Number->nan;
381 }
382 }
383  
384 my $res = eval { Math::Prime::Util::GMP::chinese(@pairs) } // return Sidef::Types::Number::Number->nan;
385 Sidef::Types::Number::Number::_set_int($res);
386 }
387  
388 sub range_sum {
389 my ($self, $from, $to, $step) = @_;
390 $step //= Sidef::Types::Number::Number::ONE;
391 state $two = Sidef::Types::Number::Number::_set_int(2);
392 ($from->add($to))->mul($to->sub($from)->div($step)->add(Sidef::Types::Number::Number::ONE))->div($two);
393 }
394  
395 sub range_map {
396 my ($self, $amount, $from, $to) = @_;
397 Sidef::Types::Range::RangeNumber->new($from, $to, $to->sub($from)->div($amount));
398 }
399  
400 sub map {
401 my ($self, $value, $in_min, $in_max, $out_min, $out_max) = @_;
402 ($value->sub($in_min))->mul($out_max->sub($out_min))->div($in_max->sub($in_min))->add($out_min);
403 }
404  
405 sub num2percent {
406 my ($self, $num, $from, $to) = @_;
407  
408 my $sum = $to->sub($from)->abs;
409 my $dist = $num->sub($to)->abs;
410  
411 state $hundred = Sidef::Types::Number::Number::_set_int(100);
412 ($sum->sub($dist))->div($sum)->mul($hundred);
413 }
414  
415 1