Sidef/Types/Number/Polynomial.pm untested

filter: Statementstmt 0.0% 0 / 683 Branchbran 0.0% 0 / 208 Conditioncond 0.0% 0 / 180 MC/DCmcdc 0.0% 0 / 105 Subroutinesub 0.0% 0 / 79 Podpod 0.0% 0 / 72 totaltotal 0.0% 0 / 1327 CC 105 SCAR 40.7
CC
105
Cov
0%
roots
272.0
new
210.0
__stringify__
72.0
CRAP 58.6
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 = \&real;
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 = \&degree;
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__ . '::' . '/'} = \&div;
1232 *{__PACKAGE__ . '::' . '//'} = \&idiv;
1233 *{__PACKAGE__ . '::' . '÷'} = \&div;
1234 *{__PACKAGE__ . '::' . '*'} = \&mul;
1235 *{__PACKAGE__ . '::' . '%'} = \&mod;
1236 *{__PACKAGE__ . '::' . '+'} = \&add;
1237 *{__PACKAGE__ . '::' . '-'} = \&sub;
1238 *{__PACKAGE__ . '::' . '**'} = \&pow;
1239 *{__PACKAGE__ . '::' . '++'} = \&inc;
1240 *{__PACKAGE__ . '::' . '--'} = \&dec;
1241 *{__PACKAGE__ . '::' . '<'} = \&lt;
1242 *{__PACKAGE__ . '::' . '>'} = \&gt;
1243 *{__PACKAGE__ . '::' . '<=>'} = \&cmp;
1244 *{__PACKAGE__ . '::' . '<='} = \&le;
1245 *{__PACKAGE__ . '::' . '≤'} = \&le;
1246 *{__PACKAGE__ . '::' . '>='} = \&ge;
1247 *{__PACKAGE__ . '::' . '≥'} = \&ge;
1248 *{__PACKAGE__ . '::' . '=='} = \&eq;
1249 *{__PACKAGE__ . '::' . '!='} = \&ne;
1250 }
1251  
1252 1