| 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 |