| 1 | package Sidef::Types::Number::Polynomial; | ||
| 2 | |||
| 3 | # References: | ||
| 4 | # https://en.wikipedia.org/wiki/Polynomial | ||
| 5 | # https://metacpan.org/pod/Math::Polynomial | ||
| 6 | # https://metacpan.org/pod/Math::Polynomial::Cyclotomic | ||
| 7 | |||
| 8 | use utf8; | ||
| 9 | use 5.016; | ||
| 10 | |||
| 11 | use List::Util qw(); | ||
| 12 | use Scalar::Util qw(); | ||
| 13 | |||
| 14 | use parent qw( | ||
| 15 | Sidef::Types::Number::Number | ||
| 16 | ); | ||
| 17 | |||
| 18 | use overload | ||
| 19 | q{bool} => sub { (@_) = ($_[0]); goto &__boolify__ }, | ||
| 20 | q{""} => sub { (@_) = ($_[0]); goto &__stringify__ }, | ||
| 21 | q{${}} => \&to_n, | ||
| 22 | q{0+} => \&to_n; | ||
| 23 | |||
| 24 | sub new { | ||
| 25 | my (undef, @args) = @_; | ||
| 26 | |||
| 27 | if (scalar(@args) == 1) { | ||
| 28 | my $value = $args[0]; | ||
| 29 | |||
| 30 | if (ref($_[0]) eq __PACKAGE__) { | ||
| 31 | return $_[0]->eval($value); | ||
| 32 | } | ||
| 33 | |||
| 34 | if (ref($value) eq 'Sidef::Types::String::String') { | ||
| 35 | my $str = "$value"; | ||
| 36 | |||
| 37 | # Basic support for fractions of polynomials | ||
| 38 | if ( | ||
| 39 | |||
| 40 | # (anything)/(anything) | ||
| 41 | # anything/(anything) | ||
| 42 | $str =~ m{^\s*+ | ||
| 43 | \(?+(?<numerator>.*?)\)?+ | ||
| 44 | \s*+/\s*+ | ||
| 45 | \((?<denominator>.*)\) | ||
| 46 | \s*+\z}x | ||
| 47 | |||
| 48 | # (anything)/x | ||
| 49 | # anything/x | ||
| 50 | # anything/x^5 | ||
| 51 | or $str =~ m{^\s*+ | ||
| 52 | \(?+(?<numerator>.*?)\)?+ | ||
| 53 | \s*+/\s*+ | ||
| 54 | (?<denominator>[-+]?+\s*x(?>\^[-+]?+[0-9]++)?+) | ||
| 55 | \s*+\z}x | ||
| 56 | |||
| 57 | # (anything)/integer | ||
| 58 | or $str =~ m{^\s*+ | ||
| 59 | \((?<numerator>.*?)\) | ||
| 60 | \s*+/\s*+ | ||
| 61 | (?<denominator>[-+]?+[0-9]++) | ||
| 62 | \s*+\z}x | ||
| 63 | ) { | ||
| 64 | my $num = $+{numerator}; | ||
| 65 | my $den = $+{denominator}; | ||
| 66 | my $poly1 = __PACKAGE__->new(Sidef::Types::String::String->new($num)); | ||
| 67 | my $poly2 = __PACKAGE__->new(Sidef::Types::String::String->new($den)); | ||
| 68 | return $poly1->div($poly2); | ||
| 69 | } | ||
| 70 | |||
| 71 | my %pairs; | ||
| 72 | while ( | ||
| 73 | $str =~ m{\G\s*+ | ||
| 74 | (?<sign>[-+])?+\s*+ | ||
| 75 | (?<coeff>[0-9]++\s*+(?>/\s*[1-9]+[0-9]*)?)?+ | ||
| 76 | (?>\s*\*\s*)?+ | ||
| 77 | (?>(?<x>x)(?>\^\(?(?<exp>[-+]?[0-9]++))?+\)?+)?+ | ||
| 78 | \s*+}gcx | ||
| 79 | ) { | ||
| 80 | my $sign = $+{sign} // '+'; | ||
| 81 | my $exp = defined($+{x}) ? ($+{exp} // '1') : '0'; | ||
| 82 | my $coeff = Sidef::Types::Number::Number->new($+{coeff} // 1); | ||
| 83 | $coeff = $coeff->neg if $sign eq '-'; | ||
| 84 | $pairs{$exp} = $coeff; | ||
| 85 | last if $str =~ /\G\z/; | ||
| 86 | } | ||
| 87 | |||
| 88 | # Failed to parse the entire string: return NaN | ||
| 89 | if ($str !~ /\G\z/) { | ||
| 90 | return __PACKAGE__->new('0' => Sidef::Types::Number::Number::nan()); | ||
| 91 | } | ||
| 92 | |||
| 93 | # Create and return the parsed polynomial | ||
| 94 | return __PACKAGE__->new(%pairs); | ||
| 95 | } | ||
| 96 | |||
| 97 | if (Scalar::Util::reftype($value) eq 'ARRAY') { | ||
| 98 | my $end = $#{$value}; | ||
| 99 | return __PACKAGE__->new( | ||
| 100 | map { | ||
| 101 | my $t = $value->[$_]; | ||
| 102 | (Scalar::Util::reftype($t) eq 'ARRAY') ? (($t->[0], $t->[1])) : (($end - $_) => $t) | ||
| 103 | } 0 .. $end | ||
| 104 | ); | ||
| 105 | } | ||
| 106 | |||
| 107 | if (UNIVERSAL::isa($value, 'Sidef::Types::Number::Number')) { # monomial | ||
| 108 | return __PACKAGE__->new($value => Sidef::Types::Number::Number::ONE); | ||
| 109 | } | ||
| 110 | |||
| 111 | return __PACKAGE__->new(0 => $value); | ||
| 112 | } | ||
| 113 | |||
| 114 | my %poly; | ||
| 115 | |||
| 116 | my %pairs = @args; | ||
| 117 | foreach my $key (CORE::keys(%pairs)) { | ||
| 118 | |||
| 119 | my $value = $pairs{$key} // next; | ||
| 120 | $value = Sidef::Types::Number::Number->new($value) if !UNIVERSAL::isa($value, 'Sidef::Types::Number::Number'); | ||
| 121 | |||
| 122 | unless ($value->is_zero) { | ||
| 123 | $poly{$key} = $value; | ||
| 124 | } | ||
| 125 | } | ||
| 126 | |||
| 127 | bless \%poly; | ||
| 128 | } | ||
| 129 | |||
| 130 | *call = \&new; | ||
| 131 | |||
| 132 | sub with_value { | ||
| 133 | my ($self, $value) = @_; | ||
| 134 | __PACKAGE__->new(0 => $value); | ||
| 135 | } | ||
| 136 | |||
| 137 | sub to_poly { | ||
| 138 | $_[0]; | ||
| 139 | } | ||
| 140 | |||
| 141 | sub to_n { | ||
| 142 | my ($x) = @_; | ||
| 143 | my $d = scalar keys(%$x); | ||
| 144 | |||
| 145 | return Sidef::Types::Number::Number::ZERO if ($d == 0); | ||
| 146 | |||
| 147 | if ($d == 1 and exists $x->{0}) { | ||
| 148 | return $x->{0}->to_n; | ||
| 149 | } | ||
| 150 | |||
| 151 | return Sidef::Types::Number::Number::nan(); | ||
| 152 | } | ||
| 153 | |||
| 154 | sub real { | ||
| 155 | my ($x) = @_; | ||
| 156 | |||
| 157 | if (exists $x->{0}) { | ||
| 158 | return $x->{0}; | ||
| 159 | } | ||
| 160 | |||
| 161 | return Sidef::Types::Number::Number::ZERO; | ||
| 162 | } | ||
| 163 | |||
| 164 | *re = \ℜ | ||
| 165 | |||
| 166 | sub is_real { | ||
| 167 | my ($x) = @_; | ||
| 168 | my $d = scalar keys(%$x); | ||
| 169 | |||
| 170 | ($d == 0 or ($d == 1 and exists($x->{0}) and $x->{0}->is_real)) | ||
| 171 | ? Sidef::Types::Bool::Bool::TRUE | ||
| 172 | : Sidef::Types::Bool::Bool::FALSE; | ||
| 173 | } | ||
| 174 | |||
| 175 | sub is_nan { | ||
| 176 | my ($x) = @_; | ||
| 177 | foreach my $key (keys %$x) { | ||
| 178 | if ($x->{$key}->is_nan) { | ||
| 179 | return Sidef::Types::Bool::Bool::TRUE; | ||
| 180 | } | ||
| 181 | } | ||
| 182 | Sidef::Types::Bool::Bool::FALSE; | ||
| 183 | } | ||
| 184 | |||
| 185 | sub is_inf { | ||
| 186 | my ($x) = @_; | ||
| 187 | foreach my $key (keys %$x) { | ||
| 188 | if ($x->{$key}->is_inf) { | ||
| 189 | return Sidef::Types::Bool::Bool::TRUE; | ||
| 190 | } | ||
| 191 | } | ||
| 192 | Sidef::Types::Bool::Bool::FALSE; | ||
| 193 | } | ||
| 194 | |||
| 195 | sub is_ninf { | ||
| 196 | my ($x) = @_; | ||
| 197 | foreach my $key (keys %$x) { | ||
| 198 | if ($x->{$key}->is_ninf) { | ||
| 199 | return Sidef::Types::Bool::Bool::TRUE; | ||
| 200 | } | ||
| 201 | } | ||
| 202 | Sidef::Types::Bool::Bool::FALSE; | ||
| 203 | } | ||
| 204 | |||
| 205 | sub norm { | ||
| 206 | $_[0]->real->norm; | ||
| 207 | } | ||
| 208 | |||
| 209 | sub content { | ||
| 210 | my ($x) = @_; | ||
| 211 | Sidef::Types::Number::Number::gcd(CORE::values %$x); | ||
| 212 | } | ||
| 213 | |||
| 214 | *cont = \&content; | ||
| 215 | |||
| 216 | sub primitive_part { | ||
| 217 | my ($x) = @_; | ||
| 218 | $x->div($x->content); | ||
| 219 | } | ||
| 220 | |||
| 221 | *prim_part = \&primitive_part; | ||
| 222 | *primpart = \&primitive_part; | ||
| 223 | |||
| 224 | sub leading_term { | ||
| 225 | my ($x) = @_; | ||
| 226 | my ($deg) = List::Util::max(CORE::keys(%$x)) // return __PACKAGE__->new(); | ||
| 227 | __PACKAGE__->new($deg => $x->{$deg}); | ||
| 228 | } | ||
| 229 | |||
| 230 | sub leading_coefficient { | ||
| 231 | my ($x) = @_; | ||
| 232 | my ($deg) = List::Util::max(CORE::keys(%$x)) // return Sidef::Types::Number::Number::ZERO; | ||
| 233 | $x->{$deg}; | ||
| 234 | } | ||
| 235 | |||
| 236 | *leading_coeff = \&leading_coefficient; | ||
| 237 | |||
| 238 | sub leading_monomial { | ||
| 239 | my ($x) = @_; | ||
| 240 | my ($deg) = List::Util::max(CORE::keys(%$x)) // return __PACKAGE__->new(); | ||
| 241 | __PACKAGE__->new($deg => Sidef::Types::Number::Number::ONE); | ||
| 242 | } | ||
| 243 | |||
| 244 | sub height { | ||
| 245 | my ($x) = @_; | ||
| 246 | Sidef::Types::Number::Number::max(map { $_->abs } CORE::values %$x); | ||
| 247 | } | ||
| 248 | |||
| 249 | sub is_squarefree { | ||
| 250 | my ($x) = @_; | ||
| 251 | $x->gcd($x->derivative)->is_one; | ||
| 252 | } | ||
| 253 | |||
| 254 | sub squarefree_part { | ||
| 255 | my ($x) = @_; | ||
| 256 | $x->div($x->gcd($x->derivative)); | ||
| 257 | } | ||
| 258 | |||
| 259 | sub __dump__ { | ||
| 260 | my ($x) = @_; | ||
| 261 | my $str = join(", ", map { join(' => ', $_, $x->{$_}->dump) } sort { ($a <=> $b) || ($a cmp $b) } CORE::keys %$x); | ||
| 262 | 'Polynomial(' . $str . ')'; | ||
| 263 | } | ||
| 264 | |||
| 265 | sub __boolify__ { | ||
| 266 | my ($x) = @_; | ||
| 267 | ($x->{0} // 0); | ||
| 268 | } | ||
| 269 | |||
| 270 | sub __stringify__ { | ||
| 271 | my ($x, $method) = @_; | ||
| 272 | |||
| 273 | $method //= 'to_s'; | ||
| 274 | |||
| 275 | my $str = ''; | ||
| 276 | my @keys = sort { ($b <=> $a) || ($b cmp $a) } CORE::keys(%$x); | ||
| 277 | |||
| 278 | foreach my $key (@keys) { | ||
| 279 | |||
| 280 | $str .= ' + '; | ||
| 281 | |||
| 282 | my $v = $x->{$key}; | ||
| 283 | my $c_str = | ||
| 284 | (ref($v) eq 'Sidef::Types::Number::Number' and ref($$v) eq 'Math::GMPq') | ||
| 285 | ? Math::GMPq::Rmpq_get_str($$v, 10) | ||
| 286 | : ${$v->$method}; | ||
| 287 | |||
| 288 | if ($c_str =~ s/^-//) { | ||
| 289 | $str =~ s/ \+ \z/ - /; | ||
| 290 | } | ||
| 291 | |||
| 292 | if ($c_str =~ /[+-]/ and $c_str !~ /^\w+\(.*\)\z/) { | ||
| 293 | $c_str = "($c_str)"; | ||
| 294 | } | ||
| 295 | |||
| 296 | $str .= $c_str if ($key eq '0' or $c_str ne '1'); | ||
| 297 | |||
| 298 | if ($key ne '0') { | ||
| 299 | $str .= '*' if ($c_str ne '1'); | ||
| 300 | $str .= "x"; | ||
| 301 | $str .= "^$key" if ($key != 1); | ||
| 302 | } | ||
| 303 | } | ||
| 304 | |||
| 305 | $str =~ s/^ \+ //; | ||
| 306 | $str =~ s/ \+ \z//; | ||
| 307 | $str =~ s/^ \- /-/; | ||
| 308 | $str =~ s/^\((.*)\)\z/$1/; | ||
| 309 | $str || '0'; | ||
| 310 | } | ||
| 311 | |||
| 312 | sub to_s { | ||
| 313 | my ($x) = @_; | ||
| 314 | Sidef::Types::String::String->new($x->__stringify__); | ||
| 315 | } | ||
| 316 | |||
| 317 | *stringify = \&to_s; | ||
| 318 | |||
| 319 | sub pretty { | ||
| 320 | my ($x) = @_; | ||
| 321 | Sidef::Types::String::String->new($x->__stringify__('pretty')); | ||
| 322 | } | ||
| 323 | |||
| 324 | sub dump { | ||
| 325 | my ($x) = @_; | ||
| 326 | Sidef::Types::String::String->new($x->__dump__); | ||
| 327 | } | ||
| 328 | |||
| 329 | sub degree { | ||
| 330 | my ($x) = @_; | ||
| 331 | my $deg = List::Util::max(CORE::keys(%$x)) // return Sidef::Types::Number::Number::ZERO; | ||
| 332 | Sidef::Types::Number::Number::_set_int($deg); | ||
| 333 | } | ||
| 334 | |||
| 335 | *deg = \°ree; | ||
| 336 | |||
| 337 | sub derivative { | ||
| 338 | my ($x) = @_; | ||
| 339 | __PACKAGE__->new(map { (Math::Prime::Util::GMP::subint($_, 1), $x->{$_}->mul(Sidef::Types::Number::Number::_set_int($_))) } CORE::keys(%$x)); | ||
| 340 | } | ||
| 341 | |||
| 342 | sub eval { | ||
| 343 | my ($x, $value) = @_; | ||
| 344 | |||
| 345 | my @exponents = CORE::keys(%$x); | ||
| 346 | @exponents || return Sidef::Types::Number::Number::ZERO; | ||
| 347 | |||
| 348 | if (ref($value) eq __PACKAGE__ and exists($value->{'1'}) and $value->{'1'}->is_one) { | ||
| 349 | if (scalar(keys %$value) == 1) { # evaluation at x | ||
| 350 | return $x; | ||
| 351 | } | ||
| 352 | } | ||
| 353 | |||
| 354 | # Evaluate via Horner's method (nested multiplication), visiting terms | ||
| 355 | # from the highest exponent down to the lowest, instead of computing | ||
| 356 | # value^k from scratch for every single term independently. Between | ||
| 357 | # two consecutive exponents e_i > e_{i+1}, the accumulator advances | ||
| 358 | # with a single multiplication by value^(e_i - e_{i+1}), which is much | ||
| 359 | # cheaper than an unrelated full exponentiation per term for dense or | ||
| 360 | # closely-spaced polynomials. | ||
| 361 | @exponents = CORE::sort { $b <=> $a } @exponents; | ||
| 362 | |||
| 363 | my $prev_exp = CORE::shift(@exponents); | ||
| 364 | my $result = $x->{$prev_exp}->eval($value); | ||
| 365 | |||
| 366 | foreach my $exp (@exponents) { | ||
| 367 | my $gap = Sidef::Types::Number::Number::_set_int(Math::Prime::Util::GMP::subint($prev_exp, $exp)); | ||
| 368 | my $factor = $value->pow($gap); | ||
| 369 | |||
| 370 | $result = $result->mul($factor)->add($x->{$exp}->eval($value)); | ||
| 371 | $prev_exp = $exp; | ||
| 372 | } | ||
| 373 | |||
| 374 | # Bring the accumulator down from the lowest nonzero exponent to x^0. | ||
| 375 | if ($prev_exp != 0) { | ||
| 376 | $result = $result->mul($value->pow(Sidef::Types::Number::Number::_set_int($prev_exp))); | ||
| 377 | } | ||
| 378 | |||
| 379 | return $result; | ||
| 380 | } | ||
| 381 | |||
| 382 | sub compose { | ||
| 383 | my ($x, $y) = @_; | ||
| 384 | if (ref($y) ne __PACKAGE__) { | ||
| 385 | $y = __PACKAGE__->new(0 => $y); | ||
| 386 | } | ||
| 387 | my @keys = CORE::keys(%$x); | ||
| 388 | @keys || return __PACKAGE__->new(0 => Sidef::Types::Number::Number::ZERO); | ||
| 389 | my $result; | ||
| 390 | foreach my $k (@keys) { | ||
| 391 | my $term = $y->pow(Sidef::Types::Number::Number::_set_int($k))->mul($x->{$k}); | ||
| 392 | $result = defined($result) ? $result->add($term) : $term; | ||
| 393 | } | ||
| 394 | return $result; | ||
| 395 | } | ||
| 396 | |||
| 397 | sub exponents { | ||
| 398 | my ($x) = @_; | ||
| 399 | Sidef::Types::Array::Array->new(map { Sidef::Types::Number::Number::_set_int($_) } sort { ($a <=> $b) || ($a cmp $b) } CORE::keys(%$x)); | ||
| 400 | } | ||
| 401 | |||
| 402 | sub coeff { | ||
| 403 | my ($x, $key) = @_; | ||
| 404 | $x->{$key} // Sidef::Types::Number::Number::ZERO; | ||
| 405 | } | ||
| 406 | |||
| 407 | *coefficient = \&coeff; | ||
| 408 | |||
| 409 | sub coeffs { | ||
| 410 | my ($x) = @_; | ||
| 411 | Sidef::Types::Array::Array->new( | ||
| 412 | [map { Sidef::Types::Array::Array->new([Sidef::Types::Number::Number::_set_int($_), $x->{$_}]) } | ||
| 413 | sort { ($a <=> $b) || ($a cmp $b) } CORE::keys(%$x) | ||
| 414 | ] | ||
| 415 | ); | ||
| 416 | } | ||
| 417 | |||
| 418 | *coefficients = \&coeffs; | ||
| 419 | |||
| 420 | sub newton_method { | ||
| 421 | my ($f, $x, $df) = @_; | ||
| 422 | |||
| 423 | $x //= Sidef::Types::Number::Number->i; | ||
| 424 | $df //= $f->derivative; | ||
| 425 | |||
| 426 | for (0 .. CORE::int($Sidef::Types::Number::Number::PREC)) { | ||
| 427 | my $fx = $f->eval($x); | ||
| 428 | if ($fx->approx_eq(Sidef::Types::Number::Number::ZERO)) { | ||
| 429 | return $x; | ||
| 430 | } | ||
| 431 | my $dfx = $df->eval($x); | ||
| 432 | $x = $x->sub($fx->div($dfx)); | ||
| 433 | } | ||
| 434 | |||
| 435 | return $x; | ||
| 436 | } | ||
| 437 | |||
| 438 | sub roots { | ||
| 439 | my ($f) = @_; | ||
| 440 | |||
| 441 | my $degree_obj = $f->degree; | ||
| 442 | my @roots_of_unity = @{$degree_obj->roots_of_unity}; | ||
| 443 | |||
| 444 | @roots_of_unity || return Sidef::Types::Array::Array->new; | ||
| 445 | |||
| 446 | my $df = $f->derivative; | ||
| 447 | |||
| 448 | my $prec_bits = CORE::int($Sidef::Types::Number::Number::PREC); | ||
| 449 | my $prec = Sidef::Types::Number::Number::_set_int(-(($prec_bits >> 2) - 1)); | ||
| 450 | my $prec_min = Sidef::Types::Number::Number::_set_int(-($prec_bits >> 3)); | ||
| 451 | |||
| 452 | my $degree = CORE::int($degree_obj); | ||
| 453 | |||
| 454 | # '1' and '0' using the Sidef Number objects | ||
| 455 | state $one = Sidef::Types::Number::Number::ONE; | ||
| 456 | state $zero = Sidef::Types::Number::Number::ZERO; | ||
| 457 | |||
| 458 | # PHASE 1: Aberth-Ehrlich Initialization | ||
| 459 | # We slightly scale and rotate the roots of unity to break perfect symmetry. | ||
| 460 | # Newton methods easily stall on axes when handling symmetric biquadratic polynomials. | ||
| 461 | my $perturbation = Sidef::Types::Number::Complex->new(Sidef::Types::Number::Number->new('1.1'), Sidef::Types::Number::Number->new('0.2')); # 1.1 + 0.2i | ||
| 462 | my @z = map { $perturbation->mul($_) } @roots_of_unity; | ||
| 463 | |||
| 464 | my $I = Sidef::Types::Number::Complex->new($zero, $one); | ||
| 465 | |||
| 466 | # Calculate dynamic max_iter | ||
| 467 | # Example: Base 50 + (2 * degree) + log2(precision) | ||
| 468 | my $log2_prec = CORE::log($prec_bits > 0 ? $prec_bits : 2) / CORE::log(2); | ||
| 469 | my $max_iter = 50 + (2 * $degree) + CORE::int($log2_prec); | ||
| 470 | |||
| 471 | # PHASE 2: Aberth-Ehrlich Simultaneous Iteration | ||
| 472 | for my $iter (1 .. $max_iter) { | ||
| 473 | my $all_converged = 1; | ||
| 474 | my @z_next; | ||
| 475 | |||
| 476 | for my $i (0 .. $#z) { | ||
| 477 | my $zi = $z[$i]; | ||
| 478 | |||
| 479 | my $pz = $f->eval($zi); | ||
| 480 | if ($pz->round($prec)->is_zero) { | ||
| 481 | push @z_next, $zi; | ||
| 482 | next; | ||
| 483 | } | ||
| 484 | |||
| 485 | my $dpz = $df->eval($zi); | ||
| 486 | if ($dpz->round($prec)->is_zero) { | ||
| 487 | $zi = $zi->add($I); # Perturb slightly to avoid division by zero | ||
| 488 | $pz = $f->eval($zi); | ||
| 489 | $dpz = $df->eval($zi); | ||
| 490 | } | ||
| 491 | |||
| 492 | my $w = $pz->div($dpz); # Standard Newton step | ||
| 493 | my $sum = $zero; | ||
| 494 | |||
| 495 | # Electrostatic repulsion term from all other roots | ||
| 496 | for my $j (0 .. $#z) { | ||
| 497 | next if $i == $j; | ||
| 498 | my $diff = $zi->sub($z[$j]); | ||
| 499 | if (!$diff->round($prec)->is_zero) { | ||
| 500 | $sum = $sum->add($diff->inv); | ||
| 501 | } | ||
| 502 | } | ||
| 503 | |||
| 504 | my $denom = $one->sub($w->mul($sum)); | ||
| 505 | my $step; | ||
| 506 | |||
| 507 | if ($denom->round($prec)->is_zero) { | ||
| 508 | $step = $w; # Fallback to standard Newton if repulsion cancels out | ||
| 509 | } | ||
| 510 | else { | ||
| 511 | $step = $w->div($denom); | ||
| 512 | } | ||
| 513 | |||
| 514 | my $zi_new = $zi->sub($step); | ||
| 515 | push @z_next, $zi_new; | ||
| 516 | |||
| 517 | if (!$step->round($prec)->is_zero) { | ||
| 518 | $all_converged = 0; | ||
| 519 | } | ||
| 520 | } | ||
| 521 | |||
| 522 | @z = @z_next; | ||
| 523 | last if $all_converged; | ||
| 524 | } | ||
| 525 | |||
| 526 | # PHASE 3: Polish and Verify | ||
| 527 | # We run the separated roots through the original Newton polisher | ||
| 528 | # to guarantee they meet Sidef's exact deduplication and precision standards. | ||
| 529 | my %seen; | ||
| 530 | my @polynomial_roots; | ||
| 531 | |||
| 532 | foreach my $root (@z) { | ||
| 533 | my $solution = $f->newton_method($root, $df); | ||
| 534 | if (defined($solution)) { | ||
| 535 | my $key = join('', $solution->round($prec)); | ||
| 536 | if (!exists($seen{$key}) and $f->eval($solution)->round($prec_min)->is_zero) { | ||
| 537 | push @polynomial_roots, $solution; | ||
| 538 | $seen{$key} = 1; | ||
| 539 | } | ||
| 540 | } | ||
| 541 | } | ||
| 542 | |||
| 543 | # PHASE 4: Safety Fallback | ||
| 544 | # In the incredibly rare case Aberth misses a root, we retain the old transformation | ||
| 545 | # fallback to ensure this implementation is strictly >= in success rate to the original. | ||
| 546 | if (scalar(@polynomial_roots) != $degree) { | ||
| 547 | |||
| 548 | my @transformations = ( | ||
| 549 | sub { $_[0]->i }, | ||
| 550 | sub { $_[0]->exp }, | ||
| 551 | sub { $_[0]->neg }, | ||
| 552 | sub { $_[0]->sqr->dec }, | ||
| 553 | sub { $_[0]->sqr->inc }, | ||
| 554 | sub { $_[0]->sqrt }, | ||
| 555 | sub { $_[0]->conj }, | ||
| 556 | sub { $_[0]->neg }, | ||
| 557 | ); | ||
| 558 | |||
| 559 | while (@transformations) { | ||
| 560 | my $transform = CORE::shift(@transformations); | ||
| 561 | @roots_of_unity = map { $transform->($_) } @roots_of_unity; | ||
| 562 | |||
| 563 | foreach my $root (@roots_of_unity) { | ||
| 564 | my $solution = $f->newton_method($root, $df); | ||
| 565 | if (defined($solution)) { | ||
| 566 | my $key = join('', $solution->round($prec)); | ||
| 567 | if (!exists($seen{$key}) and $f->eval($solution)->round($prec_min)->is_zero) { | ||
| 568 | push @polynomial_roots, $solution; | ||
| 569 | $seen{$key} = 1; | ||
| 570 | } | ||
| 571 | last if (scalar(@polynomial_roots) == $degree); | ||
| 572 | } | ||
| 573 | } | ||
| 574 | last if (scalar(@polynomial_roots) == $degree); | ||
| 575 | } | ||
| 576 | } | ||
| 577 | |||
| 578 | Sidef::Types::Array::Array->new(\@polynomial_roots)->sort; | ||
| 579 | } | ||
| 580 | |||
| 581 | sub roots_mod { | ||
| 582 | my ($x, $m) = @_; | ||
| 583 | |||
| 584 | my @coeffs; | ||
| 585 | foreach my $pair (@{$x->coeffs}) { | ||
| 586 | my $d = ${$pair->[0]}; | ||
| 587 | my $v = $pair->[1]; | ||
| 588 | $coeffs[$d] = $v; | ||
| 589 | } | ||
| 590 | |||
| 591 | $_ //= Sidef::Types::Number::Number::ZERO for @coeffs; | ||
| 592 | |||
| 593 | my $roots = Sidef::Types::Number::Number::_solve_polynomial_congruence_all($m, \@coeffs); | ||
| 594 | $roots = [map { Sidef::Types::Number::Number::_set_int($_) } @$roots]; | ||
| 595 | Sidef::Types::Array::Array->new($roots); | ||
| 596 | } | ||
| 597 | |||
| 598 | sub binomial { | ||
| 599 | my ($n, $k) = @_; | ||
| 600 | |||
| 601 | my $k_int = CORE::int($k); | ||
| 602 | my @terms; | ||
| 603 | |||
| 604 | foreach my $i (0 .. $k_int - 1) { | ||
| 605 | push @terms, $n; | ||
| 606 | $n = $n->dec; | ||
| 607 | } | ||
| 608 | |||
| 609 | @terms || return __PACKAGE__->new(0 => Sidef::Types::Number::Number::ONE); | ||
| 610 | |||
| 611 | my $prod = Sidef::Types::Number::Number::_binsplit(\@terms, \&Sidef::Types::Number::Polynomial::mul); | ||
| 612 | $prod->div($k->factorial); | ||
| 613 | } | ||
| 614 | |||
| 615 | sub add { | ||
| 616 | my ($x, $y) = @_; | ||
| 617 | |||
| 618 | if (ref($y) eq __PACKAGE__) { | ||
| 619 | return | ||
| 620 | __PACKAGE__->new((map { $_ => (exists($y->{$_}) ? $x->{$_}->add($y->{$_}) : $x->{$_}) } CORE::keys %$x), | ||
| 621 | (map { exists($x->{$_}) ? () : ($_ => $y->{$_}) } CORE::keys %$y)); | ||
| 622 | } | ||
| 623 | |||
| 624 | if (not exists $x->{0}) { | ||
| 625 | return __PACKAGE__->new(0 => $y, %$x); | ||
| 626 | } | ||
| 627 | |||
| 628 | __PACKAGE__->new(map { $_ => (($_ eq '0') ? $x->{$_}->add($y) : $x->{$_}) } CORE::keys(%$x)); | ||
| 629 | } | ||
| 630 | |||
| 631 | sub sub { | ||
| 632 | my ($x, $y) = @_; | ||
| 633 | |||
| 634 | if (ref($y) eq __PACKAGE__) { | ||
| 635 | return | ||
| 636 | __PACKAGE__->new((map { $_ => (exists($y->{$_}) ? $x->{$_}->sub($y->{$_}) : $x->{$_}) } CORE::keys %$x), | ||
| 637 | (map { exists($x->{$_}) ? () : ($_ => $y->{$_}->neg) } CORE::keys %$y)); | ||
| 638 | } | ||
| 639 | |||
| 640 | if (not exists $x->{0}) { | ||
| 641 | return __PACKAGE__->new(0 => $y->neg, %$x); | ||
| 642 | } | ||
| 643 | |||
| 644 | __PACKAGE__->new(map { $_ => (($_ eq '0') ? $x->{$_}->sub($y) : $x->{$_}) } CORE::keys(%$x)); | ||
| 645 | } | ||
| 646 | |||
| 647 | sub mul { | ||
| 648 | my ($x, $y) = @_; | ||
| 649 | |||
| 650 | if (ref($y) eq __PACKAGE__) { | ||
| 651 | |||
| 652 | my @keys_x = CORE::keys %$x; | ||
| 653 | my @keys_y = CORE::keys %$y; | ||
| 654 | |||
| 655 | my %poly; | ||
| 656 | foreach my $key_x (@keys_x) { | ||
| 657 | foreach my $key_y (@keys_y) { | ||
| 658 | |||
| 659 | my $coeff = $x->{$key_x}->mul($y->{$key_y}); | ||
| 660 | my $key_z = Math::Prime::Util::GMP::addint($key_x, $key_y); | ||
| 661 | |||
| 662 | if (exists $poly{$key_z}) { | ||
| 663 | $poly{$key_z} = $poly{$key_z}->add($coeff); | ||
| 664 | } | ||
| 665 | else { | ||
| 666 | $poly{$key_z} = $coeff; | ||
| 667 | } | ||
| 668 | } | ||
| 669 | } | ||
| 670 | |||
| 671 | return __PACKAGE__->new(%poly); | ||
| 672 | } | ||
| 673 | |||
| 674 | __PACKAGE__->new(map { $_ => $x->{$_}->mul($y) } CORE::keys %$x); | ||
| 675 | } | ||
| 676 | |||
| 677 | sub sqr { | ||
| 678 | my ($x) = @_; | ||
| 679 | $x->mul($x); | ||
| 680 | } | ||
| 681 | |||
| 682 | sub divmod { | ||
| 683 | my ($x, $y) = @_; | ||
| 684 | |||
| 685 | # Reference: | ||
| 686 | # https://en.wikipedia.org/wiki/Polynomial_greatest_common_divisor#Euclidean_division | ||
| 687 | |||
| 688 | # Get degree of x | ||
| 689 | my $deg_r = List::Util::max(CORE::keys(%$x)); | ||
| 690 | $deg_r // return (__PACKAGE__->new(), __PACKAGE__->new()); | ||
| 691 | |||
| 692 | if ($deg_r > ~0) { | ||
| 693 | $deg_r = Math::GMPz::Rmpz_init_set_str("$deg_r", 10); | ||
| 694 | } | ||
| 695 | |||
| 696 | # Get degree of y | ||
| 697 | my $deg_y = List::Util::max(CORE::keys(%$y)); | ||
| 698 | $deg_y // return (__PACKAGE__->new(0 => Sidef::Types::Number::Number::inf()), __PACKAGE__->new()); | ||
| 699 | |||
| 700 | if ($deg_y > ~0) { | ||
| 701 | $deg_y = Math::GMPz::Rmpz_init_set_str("$deg_y", 10); | ||
| 702 | } | ||
| 703 | |||
| 704 | my $q = __PACKAGE__->new(); | ||
| 705 | my $r = $x; | ||
| 706 | my $c = $y->{$deg_y}; # Leading coefficient of y | ||
| 707 | |||
| 708 | # Handle zero or NaN leading coefficient | ||
| 709 | if (!defined($c) || $c->is_zero() || $c->is_nan()) { | ||
| 710 | return (__PACKAGE__->new(0 => Sidef::Types::Number::Number::nan()), __PACKAGE__->new()); | ||
| 711 | } | ||
| 712 | |||
| 713 | # Track deg(r) incrementally with a lazy-deletion max-heap instead of | ||
| 714 | # rescanning every remaining term of r on each step. Each subtraction | ||
| 715 | # only ever touches exponents within [deg(r)-deg(y), deg(r)], so a | ||
| 716 | # candidate exponent, once confirmed absent from r, can never become | ||
| 717 | # present again in a later step (all later steps operate on strictly | ||
| 718 | # smaller degrees) -- so each exponent is pushed and permanently | ||
| 719 | # discarded from the heap at most once over the whole division. This | ||
| 720 | # keeps the per-step cost proportional to deg(y) instead of the size | ||
| 721 | # of the (possibly still-large) remainder r. | ||
| 722 | my @deg_heap; | ||
| 723 | _heap_push(\@deg_heap, $_) for CORE::keys(%$x); | ||
| 724 | |||
| 725 | while ($deg_r >= $deg_y) { | ||
| 726 | |||
| 727 | my $lc = $r->{$deg_r}; # Leading coefficient of r | ||
| 728 | my $t = $lc->div($c); # Quotient of leading coefficients | ||
| 729 | |||
| 730 | # Check for NaN result | ||
| 731 | if ($t->is_nan()) { | ||
| 732 | return (__PACKAGE__->new(0 => Sidef::Types::Number::Number::nan()), __PACKAGE__->new()); | ||
| 733 | } | ||
| 734 | |||
| 735 | # s := t * x^(deg(r) - deg(y)) | ||
| 736 | my $s = __PACKAGE__->new(Math::Prime::Util::GMP::subint($deg_r, $deg_y), $t); | ||
| 737 | my $sub_term = $s->mul($y); | ||
| 738 | $q = $q->add($s); | ||
| 739 | $r = $r->sub($sub_term); | ||
| 740 | |||
| 741 | # Only the exponents touched by this step's subtraction can have | ||
| 742 | # changed, so only they need to become new degree candidates. | ||
| 743 | _heap_push(\@deg_heap, $_) for CORE::keys(%$sub_term); | ||
| 744 | |||
| 745 | # Find new degree of r by lazily discarding stale candidates. | ||
| 746 | $deg_r = undef; | ||
| 747 | while (@deg_heap) { | ||
| 748 | my $top = $deg_heap[0]; | ||
| 749 | if (CORE::exists($r->{$top})) { | ||
| 750 | $deg_r = $top; | ||
| 751 | last; | ||
| 752 | } | ||
| 753 | _heap_pop_max(\@deg_heap); | ||
| 754 | } | ||
| 755 | defined($deg_r) or last; | ||
| 756 | |||
| 757 | if ($deg_r > ~0) { | ||
| 758 | $deg_r = Math::GMPz::Rmpz_init_set_str("$deg_r", 10); | ||
| 759 | } | ||
| 760 | } | ||
| 761 | |||
| 762 | return ($q, $r); | ||
| 763 | } | ||
| 764 | |||
| 765 | # --- Private lazy-deletion binary max-heap, used by divmod() above to --- | ||
| 766 | # --- track the remainder's degree without rescanning all of its keys. --- | ||
| 767 | |||
| 768 | sub _heap_push { | ||
| 769 | my ($heap, $val) = @_; | ||
| 770 | CORE::push(@$heap, $val); | ||
| 771 | my $i = $#$heap; | ||
| 772 | while ($i > 0) { | ||
| 773 | my $parent = ($i - 1) >> 1; | ||
| 774 | last if !($heap->[$i] > $heap->[$parent]); | ||
| 775 | @{$heap}[$i, $parent] = @{$heap}[$parent, $i]; | ||
| 776 | $i = $parent; | ||
| 777 | } | ||
| 778 | } | ||
| 779 | |||
| 780 | sub _heap_pop_max { | ||
| 781 | my ($heap) = @_; | ||
| 782 | return undef if !@$heap; | ||
| 783 | my $top = $heap->[0]; | ||
| 784 | my $last = CORE::pop(@$heap); | ||
| 785 | if (@$heap) { | ||
| 786 | $heap->[0] = $last; | ||
| 787 | my $i = 0; | ||
| 788 | my $n = scalar(@$heap); | ||
| 789 | while (1) { | ||
| 790 | my $l = 2 * $i + 1; | ||
| 791 | my $r = 2 * $i + 2; | ||
| 792 | my $largest = $i; | ||
| 793 | $largest = $l if ($l < $n && $heap->[$l] > $heap->[$largest]); | ||
| 794 | $largest = $r if ($r < $n && $heap->[$r] > $heap->[$largest]); | ||
| 795 | last if ($largest == $i); | ||
| 796 | @{$heap}[$i, $largest] = @{$heap}[$largest, $i]; | ||
| 797 | $i = $largest; | ||
| 798 | } | ||
| 799 | } | ||
| 800 | return $top; | ||
| 801 | } | ||
| 802 | |||
| 803 | sub sgn { | ||
| 804 | my ($x) = @_; | ||
| 805 | my $deg = List::Util::max(CORE::keys(%$x)) // return Sidef::Types::Number::Number::ZERO; | ||
| 806 | $x->{$deg}->sgn; | ||
| 807 | } | ||
| 808 | |||
| 809 | sub abs { | ||
| 810 | my ($x) = @_; | ||
| 811 | $x->mul($x->sgn); | ||
| 812 | } | ||
| 813 | |||
| 814 | sub lcm { | ||
| 815 | my ($x, $y) = @_; | ||
| 816 | $x->mul($y)->abs->div($x->gcd($y)); | ||
| 817 | } | ||
| 818 | |||
| 819 | sub normalize_to_monic { | ||
| 820 | my ($x) = @_; | ||
| 821 | |||
| 822 | # Normalize to monic polynomial (leading coefficient = 1) | ||
| 823 | my $deg = List::Util::max(CORE::keys(%$x)); | ||
| 824 | if (defined($deg) && exists($x->{$deg})) { | ||
| 825 | my $lc = $x->{$deg}; | ||
| 826 | if (!$lc->is_zero() && !$lc->is_one()) { | ||
| 827 | |||
| 828 | # Go through the normal constructor (rather than assigning | ||
| 829 | # directly into a bare-blessed hash) so that any coefficient | ||
| 830 | # which happens to divide out to exactly zero is dropped, | ||
| 831 | # preserving this class's invariant that only nonzero | ||
| 832 | # coefficients are ever stored. | ||
| 833 | return __PACKAGE__->new(map { $_ => $x->{$_}->div($lc) } CORE::keys(%$x)); | ||
| 834 | } | ||
| 835 | } | ||
| 836 | |||
| 837 | return $x; | ||
| 838 | } | ||
| 839 | |||
| 840 | sub is_monic { | ||
| 841 | my ($x) = @_; | ||
| 842 | $x->leading_coefficient->is_one; | ||
| 843 | } | ||
| 844 | |||
| 845 | sub gcd { | ||
| 846 | my ($x, $y) = @_; | ||
| 847 | |||
| 848 | # Handle zero polynomials | ||
| 849 | return $y if $x->is_zero(); | ||
| 850 | return $x if $y->is_zero(); | ||
| 851 | |||
| 852 | # Euclidean algorithm | ||
| 853 | while (!$y->is_zero()) { | ||
| 854 | my ($q, $r) = $x->divmod($y); | ||
| 855 | |||
| 856 | # Check if division produced invalid result | ||
| 857 | my $deg_q = List::Util::max(CORE::keys(%$q)); | ||
| 858 | if (defined($deg_q) && exists $q->{$deg_q}) { | ||
| 859 | my $coef = $q->{$deg_q}; | ||
| 860 | last if ($coef->is_nan() || $coef->is_inf() || $coef->is_ninf); | ||
| 861 | } | ||
| 862 | |||
| 863 | ($x, $y) = ($y, $r); | ||
| 864 | } | ||
| 865 | |||
| 866 | return $x->normalize_to_monic; | ||
| 867 | } | ||
| 868 | |||
| 869 | sub gcdext { | ||
| 870 | my ($x, $y) = @_; | ||
| 871 | |||
| 872 | # Reference: | ||
| 873 | # https://en.wikipedia.org/wiki/Polynomial_greatest_common_divisor#B%C3%A9zout's_identity_and_extended_GCD_algorithm | ||
| 874 | |||
| 875 | if (ref($y) ne __PACKAGE__) { | ||
| 876 | $y = __PACKAGE__->new(0 => $y); | ||
| 877 | } | ||
| 878 | |||
| 879 | my $r0 = $x; | ||
| 880 | my $r1 = $y; | ||
| 881 | |||
| 882 | my $s0 = Sidef::Types::Number::Number::ONE; | ||
| 883 | my $s1 = Sidef::Types::Number::Number::ZERO; | ||
| 884 | my $t0 = Sidef::Types::Number::Number::ZERO; | ||
| 885 | my $t1 = Sidef::Types::Number::Number::ONE; | ||
| 886 | |||
| 887 | my $i = 1; | ||
| 888 | until ($r1->is_zero) { | ||
| 889 | my ($q, $r) = $r0->divmod($r1); | ||
| 890 | ($r0, $r1) = ($r1, $r); | ||
| 891 | ($s0, $s1) = ($s1, $s0->sub($q->mul($s1))); | ||
| 892 | ($t0, $t1) = ($t1, $t0->sub($q->mul($t1))); | ||
| 893 | ++$i; | ||
| 894 | } | ||
| 895 | |||
| 896 | my $g = $r0; | ||
| 897 | my $u = $s0; | ||
| 898 | my $v = $t0; | ||
| 899 | my $a1 = $t1->mul(Sidef::Types::Number::Number::MONE->ipow(Sidef::Types::Number::Number::_set_int($i - 1))); | ||
| 900 | my $b1 = $s1->mul(Sidef::Types::Number::Number::MONE->ipow(Sidef::Types::Number::Number::_set_int($i))); | ||
| 901 | |||
| 902 | # Normalize all outputs | ||
| 903 | my $deg_g = List::Util::max(CORE::keys(%$g)); | ||
| 904 | |||
| 905 | if (defined($deg_g) && exists($g->{$deg_g})) { | ||
| 906 | my $lc = $g->{$deg_g}; | ||
| 907 | |||
| 908 | if (!$lc->is_zero() && !$lc->is_one()) { | ||
| 909 | $g = $g->div($lc); | ||
| 910 | $u = $u->div($lc); | ||
| 911 | $v = $v->div($lc); | ||
| 912 | $a1 = $a1->mul($lc); | ||
| 913 | $b1 = $b1->mul($lc); | ||
| 914 | } | ||
| 915 | } | ||
| 916 | |||
| 917 | return ($g, $u, $v, $a1, $b1); | ||
| 918 | } | ||
| 919 | |||
| 920 | sub idiv { | ||
| 921 | my ($x, $y) = @_; | ||
| 922 | |||
| 923 | if (ref($y) ne __PACKAGE__) { | ||
| 924 | $y = __PACKAGE__->new(0 => $y); | ||
| 925 | } | ||
| 926 | |||
| 927 | my ($quot, $rem) = $x->divmod($y); | ||
| 928 | return $quot; | ||
| 929 | } | ||
| 930 | |||
| 931 | # Probably not right? | ||
| 932 | *idiv_ceil = \&idiv; | ||
| 933 | *idiv_trunc = \&idiv; | ||
| 934 | *idiv_round = \&idiv; | ||
| 935 | *idiv_floor = \&idiv; | ||
| 936 | |||
| 937 | sub div { | ||
| 938 | my ($x, $y) = @_; | ||
| 939 | |||
| 940 | if (ref($y) eq __PACKAGE__) { | ||
| 941 | |||
| 942 | my ($quot, $rem) = $x->divmod($y); | ||
| 943 | |||
| 944 | if ($rem->is_zero) { | ||
| 945 | return $quot; | ||
| 946 | } | ||
| 947 | |||
| 948 | my $frac = Sidef::Types::Number::Fraction->new($quot->mul($y)->add($rem), $y); | ||
| 949 | |||
| 950 | if ($frac->is_zero) { | ||
| 951 | return Sidef::Types::Number::Polynomial->new(); | ||
| 952 | } | ||
| 953 | |||
| 954 | return $frac; | ||
| 955 | } | ||
| 956 | |||
| 957 | if ($y->is_zero) { | ||
| 958 | return __PACKAGE__->new(0 => Sidef::Types::Number::Number::inf()); | ||
| 959 | } | ||
| 960 | |||
| 961 | __PACKAGE__->new(map { $_ => $x->{$_}->div($y) } CORE::keys %$x); | ||
| 962 | } | ||
| 963 | |||
| 964 | sub neg { | ||
| 965 | my ($x) = @_; | ||
| 966 | __PACKAGE__->new(map { $_ => $x->{$_}->neg } CORE::keys %$x); | ||
| 967 | } | ||
| 968 | |||
| 969 | sub float { | ||
| 970 | my ($x) = @_; | ||
| 971 | __PACKAGE__->new(map { $_ => $x->{$_}->float } CORE::keys %$x); | ||
| 972 | } | ||
| 973 | |||
| 974 | sub rat { | ||
| 975 | my ($x) = @_; | ||
| 976 | __PACKAGE__->new(map { $_ => $x->{$_}->rat } CORE::keys %$x); | ||
| 977 | } | ||
| 978 | |||
| 979 | sub rat_approx { | ||
| 980 | my ($x) = @_; | ||
| 981 | __PACKAGE__->new(map { $_ => $x->{$_}->rat_approx } CORE::keys %$x); | ||
| 982 | } | ||
| 983 | |||
| 984 | sub floor { | ||
| 985 | my ($x) = @_; | ||
| 986 | __PACKAGE__->new(map { $_ => $x->{$_}->floor } CORE::keys %$x); | ||
| 987 | } | ||
| 988 | |||
| 989 | sub ceil { | ||
| 990 | my ($x) = @_; | ||
| 991 | __PACKAGE__->new(map { $_ => $x->{$_}->ceil } CORE::keys %$x); | ||
| 992 | } | ||
| 993 | |||
| 994 | sub round { | ||
| 995 | my ($x, $r) = @_; | ||
| 996 | __PACKAGE__->new(map { $_ => $x->{$_}->round($r) } CORE::keys %$x); | ||
| 997 | } | ||
| 998 | |||
| 999 | sub mod { | ||
| 1000 | my ($x, $y) = @_; | ||
| 1001 | |||
| 1002 | if (ref($y) eq __PACKAGE__) { | ||
| 1003 | |||
| 1004 | # mod(a, b) = a - b * floor(a/b) | ||
| 1005 | # return $x->sub($y->mul($x->div($y)->floor)); | ||
| 1006 | |||
| 1007 | my ($quot, $rem) = $x->divmod($y); | ||
| 1008 | return $rem; | ||
| 1009 | } | ||
| 1010 | |||
| 1011 | __PACKAGE__->new(map { $_ => Sidef::Types::Number::Mod->new($x->{$_}, $y) } CORE::keys %$x); | ||
| 1012 | } | ||
| 1013 | |||
| 1014 | sub lift { | ||
| 1015 | my ($x) = @_; | ||
| 1016 | __PACKAGE__->new(map { $_ => $x->{$_}->lift } CORE::keys %$x); | ||
| 1017 | } | ||
| 1018 | |||
| 1019 | sub inv { | ||
| 1020 | my ($x) = @_; | ||
| 1021 | __PACKAGE__->new(0 => Sidef::Types::Number::Number::ONE)->div($x); | ||
| 1022 | } | ||
| 1023 | |||
| 1024 | sub invmod { | ||
| 1025 | my ($x, $m) = @_; | ||
| 1026 | $x->mod($m)->inv; | ||
| 1027 | } | ||
| 1028 | |||
| 1029 | sub is_zero { | ||
| 1030 | my ($x) = @_; | ||
| 1031 | $x->eq(Sidef::Types::Number::Number::ZERO); | ||
| 1032 | } | ||
| 1033 | |||
| 1034 | sub is_one { | ||
| 1035 | my ($x) = @_; | ||
| 1036 | $x->eq(Sidef::Types::Number::Number::ONE); | ||
| 1037 | } | ||
| 1038 | |||
| 1039 | sub is_mone { | ||
| 1040 | my ($x) = @_; | ||
| 1041 | $x->eq(Sidef::Types::Number::Number::MONE); | ||
| 1042 | } | ||
| 1043 | |||
| 1044 | sub inc { | ||
| 1045 | my ($x) = @_; | ||
| 1046 | __PACKAGE__->new(%$x, 0 => ($x->{0} // Sidef::Types::Number::Number::ZERO)->inc); | ||
| 1047 | } | ||
| 1048 | |||
| 1049 | sub dec { | ||
| 1050 | my ($x) = @_; | ||
| 1051 | __PACKAGE__->new(%$x, 0 => ($x->{0} // Sidef::Types::Number::Number::ZERO)->dec); | ||
| 1052 | } | ||
| 1053 | |||
| 1054 | sub pow { | ||
| 1055 | my ($x, $n) = @_; | ||
| 1056 | |||
| 1057 | $n->is_int || return $x->to_n->pow($n); | ||
| 1058 | |||
| 1059 | my $negative_power = 0; | ||
| 1060 | |||
| 1061 | if ($n->is_neg) { | ||
| 1062 | $n = $n->abs; | ||
| 1063 | $negative_power = 1; | ||
| 1064 | } | ||
| 1065 | |||
| 1066 | my $c = __PACKAGE__->new(0 => Sidef::Types::Number::Number::ONE); | ||
| 1067 | |||
| 1068 | foreach my $bit (reverse split(//, $n->as_bin)) { | ||
| 1069 | |||
| 1070 | # c *= x if bit | ||
| 1071 | # x *= x | ||
| 1072 | |||
| 1073 | $c = $c->mul($x) if $bit; | ||
| 1074 | $x = $x->mul($x); | ||
| 1075 | } | ||
| 1076 | |||
| 1077 | if ($negative_power) { | ||
| 1078 | $c = $c->inv; | ||
| 1079 | } | ||
| 1080 | |||
| 1081 | return $c; | ||
| 1082 | } | ||
| 1083 | |||
| 1084 | sub powmod { | ||
| 1085 | my ($x, $n, $m) = @_; | ||
| 1086 | |||
| 1087 | $x = $x->mod($m); | ||
| 1088 | |||
| 1089 | my $negative_power = 0; | ||
| 1090 | |||
| 1091 | if ($n->is_neg) { | ||
| 1092 | $n = $n->abs; | ||
| 1093 | $negative_power = 1; | ||
| 1094 | } | ||
| 1095 | |||
| 1096 | my $c = __PACKAGE__->new(0 => Sidef::Types::Number::Number::ONE); | ||
| 1097 | |||
| 1098 | foreach my $bit (reverse split(//, $n->as_bin)) { | ||
| 1099 | |||
| 1100 | # c = (c*x)%m if bit | ||
| 1101 | # x = (x*x)%m | ||
| 1102 | |||
| 1103 | $c = $c->mul($x)->mod($m) if $bit; | ||
| 1104 | $x = $x->mul($x)->mod($m); | ||
| 1105 | } | ||
| 1106 | |||
| 1107 | if ($negative_power) { | ||
| 1108 | $c = $c->inv; | ||
| 1109 | } | ||
| 1110 | |||
| 1111 | return $c; | ||
| 1112 | } | ||
| 1113 | |||
| 1114 | sub cmp { | ||
| 1115 | my ($x, $y) = @_; | ||
| 1116 | |||
| 1117 | if (ref($y) eq __PACKAGE__) { | ||
| 1118 | |||
| 1119 | # Cheap pre-checks (no sorting) that catch the common case of two | ||
| 1120 | # polynomials that are obviously different -- either in how many | ||
| 1121 | # nonzero terms they have, or in their highest-degree term -- so | ||
| 1122 | # the full O(n log n) sort-and-walk below only runs when it's | ||
| 1123 | # actually needed to find where they differ. | ||
| 1124 | my $n_x = scalar(CORE::keys(%$x)); | ||
| 1125 | my $n_y = scalar(CORE::keys(%$y)); | ||
| 1126 | |||
| 1127 | $n_x == $n_y | ||
| 1128 | or return Sidef::Types::Number::Number::_set_int($n_x <=> $n_y); | ||
| 1129 | |||
| 1130 | if ($n_x > 0) { | ||
| 1131 | my $max_x = List::Util::max(CORE::keys(%$x)); | ||
| 1132 | my $max_y = List::Util::max(CORE::keys(%$y)); | ||
| 1133 | |||
| 1134 | if ($max_x != $max_y) { | ||
| 1135 | return ($max_x > $max_y) ? Sidef::Types::Number::Number::ONE : Sidef::Types::Number::Number::MONE; | ||
| 1136 | } | ||
| 1137 | } | ||
| 1138 | |||
| 1139 | my @keys_x = sort { ($a <=> $b) || ($a cmp $b) } CORE::keys %$x; | ||
| 1140 | my @keys_y = sort { ($a <=> $b) || ($a cmp $b) } CORE::keys %$y; | ||
| 1141 | |||
| 1142 | while (@keys_x and @keys_y) { | ||
| 1143 | |||
| 1144 | my $key_x = pop(@keys_x); | ||
| 1145 | my $key_y = pop(@keys_y); | ||
| 1146 | |||
| 1147 | if ($key_x eq $key_y) { | ||
| 1148 | my $cmp = $x->{$key_x}->cmp($y->{$key_y}); | ||
| 1149 | $cmp && return $cmp; | ||
| 1150 | } | ||
| 1151 | elsif ($key_x > $key_y) { | ||
| 1152 | return Sidef::Types::Number::Number::ONE; | ||
| 1153 | } | ||
| 1154 | elsif ($key_y > $key_x) { | ||
| 1155 | return Sidef::Types::Number::Number::MONE; | ||
| 1156 | } | ||
| 1157 | } | ||
| 1158 | |||
| 1159 | return Sidef::Types::Number::Number::ZERO; | ||
| 1160 | } | ||
| 1161 | |||
| 1162 | exists($x->{0}) || return undef; | ||
| 1163 | |||
| 1164 | foreach my $key (CORE::keys(%$x)) { | ||
| 1165 | ($key eq '0' or $x->{$key}->is_zero) | ||
| 1166 | or return undef; | ||
| 1167 | } | ||
| 1168 | |||
| 1169 | $x->{0}->cmp($y); | ||
| 1170 | } | ||
| 1171 | |||
| 1172 | sub eq { | ||
| 1173 | my ($x, $y) = @_; | ||
| 1174 | |||
| 1175 | if (ref($y) eq __PACKAGE__) { | ||
| 1176 | |||
| 1177 | foreach my $key (CORE::keys %$x) { | ||
| 1178 | if (exists $y->{$key}) { | ||
| 1179 | $x->{$key}->eq($y->{$key}) | ||
| 1180 | or return Sidef::Types::Bool::Bool::FALSE; | ||
| 1181 | } | ||
| 1182 | else { | ||
| 1183 | $x->{$key}->is_zero | ||
| 1184 | or return Sidef::Types::Bool::Bool::FALSE; | ||
| 1185 | } | ||
| 1186 | } | ||
| 1187 | |||
| 1188 | foreach my $key (CORE::keys %$y) { | ||
| 1189 | if (exists $x->{$key}) { | ||
| 1190 | ## ok | ||
| 1191 | } | ||
| 1192 | else { | ||
| 1193 | $y->{$key}->is_zero | ||
| 1194 | or return Sidef::Types::Bool::Bool::FALSE; | ||
| 1195 | } | ||
| 1196 | } | ||
| 1197 | |||
| 1198 | return Sidef::Types::Bool::Bool::TRUE; | ||
| 1199 | } | ||
| 1200 | |||
| 1201 | if (!scalar(CORE::keys(%$x))) { | ||
| 1202 | return $y->is_zero; | ||
| 1203 | } | ||
| 1204 | |||
| 1205 | (exists($x->{0}) and $x->{0}->eq($y)) | ||
| 1206 | || return Sidef::Types::Bool::Bool::FALSE; | ||
| 1207 | |||
| 1208 | foreach my $key (CORE::keys(%$x)) { | ||
| 1209 | ($key eq '0' or $x->{$key}->is_zero) | ||
| 1210 | or return Sidef::Types::Bool::Bool::FALSE; | ||
| 1211 | } | ||
| 1212 | |||
| 1213 | Sidef::Types::Bool::Bool::TRUE; | ||
| 1214 | } | ||
| 1215 | |||
| 1216 | sub ne { | ||
| 1217 | my ($x, $y) = @_; | ||
| 1218 | $x->eq($y)->not; | ||
| 1219 | } | ||
| 1220 | |||
| 1221 | { | ||
| 1222 | no strict 'refs'; | ||
| 1223 | |||
| 1224 | foreach my $method (qw(ge gt lt le)) { | ||
| 1225 | *{__PACKAGE__ . '::' . $method} = sub { | ||
| 1226 | my ($x, $y) = @_; | ||
| 1227 | ($x->cmp($y) // return undef)->$method(Sidef::Types::Number::Number::ZERO); | ||
| 1228 | }; | ||
| 1229 | } | ||
| 1230 | |||
| 1231 | *{__PACKAGE__ . '::' . '/'} = \÷ | ||
| 1232 | *{__PACKAGE__ . '::' . '//'} = \&idiv; | ||
| 1233 | *{__PACKAGE__ . '::' . '÷'} = \÷ | ||
| 1234 | *{__PACKAGE__ . '::' . '*'} = \&mul; | ||
| 1235 | *{__PACKAGE__ . '::' . '%'} = \&mod; | ||
| 1236 | *{__PACKAGE__ . '::' . '+'} = \&add; | ||
| 1237 | *{__PACKAGE__ . '::' . '-'} = \⊂ | ||
| 1238 | *{__PACKAGE__ . '::' . '**'} = \&pow; | ||
| 1239 | *{__PACKAGE__ . '::' . '++'} = \&inc; | ||
| 1240 | *{__PACKAGE__ . '::' . '--'} = \&dec; | ||
| 1241 | *{__PACKAGE__ . '::' . '<'} = \< | ||
| 1242 | *{__PACKAGE__ . '::' . '>'} = \> | ||
| 1243 | *{__PACKAGE__ . '::' . '<=>'} = \&cmp; | ||
| 1244 | *{__PACKAGE__ . '::' . '<='} = \≤ | ||
| 1245 | *{__PACKAGE__ . '::' . '≤'} = \≤ | ||
| 1246 | *{__PACKAGE__ . '::' . '>='} = \≥ | ||
| 1247 | *{__PACKAGE__ . '::' . '≥'} = \≥ | ||
| 1248 | *{__PACKAGE__ . '::' . '=='} = \&eq; | ||
| 1249 | *{__PACKAGE__ . '::' . '!='} = \≠ | ||
| 1250 | } | ||
| 1251 | |||
| 1252 | 1 |