Coverage for /usr/lib/python3/dist-packages/sympy/polys/densebasic.py: 14%
568 statements
« prev ^ index » next coverage.py v7.9.1, created at 2025-06-14 15:55 +0200
1"""Basic tools for dense recursive polynomials in ``K[x]`` or ``K[X]``. """
4from sympy.core.numbers import oo
5from sympy.core import igcd
6from sympy.polys.monomials import monomial_min, monomial_div
7from sympy.polys.orderings import monomial_key
9import random
11def poly_LC(f, K):
12 """
13 Return leading coefficient of ``f``.
15 Examples
16 ========
18 >>> from sympy.polys.domains import ZZ
19 >>> from sympy.polys.densebasic import poly_LC
21 >>> poly_LC([], ZZ)
22 0
23 >>> poly_LC([ZZ(1), ZZ(2), ZZ(3)], ZZ)
24 1
26 """
27 if not f:
28 return K.zero
29 else:
30 return f[0]
33def poly_TC(f, K):
34 """
35 Return trailing coefficient of ``f``.
37 Examples
38 ========
40 >>> from sympy.polys.domains import ZZ
41 >>> from sympy.polys.densebasic import poly_TC
43 >>> poly_TC([], ZZ)
44 0
45 >>> poly_TC([ZZ(1), ZZ(2), ZZ(3)], ZZ)
46 3
48 """
49 if not f:
50 return K.zero
51 else:
52 return f[-1]
54dup_LC = dmp_LC = poly_LC
55dup_TC = dmp_TC = poly_TC
58def dmp_ground_LC(f, u, K):
59 """
60 Return the ground leading coefficient.
62 Examples
63 ========
65 >>> from sympy.polys.domains import ZZ
66 >>> from sympy.polys.densebasic import dmp_ground_LC
68 >>> f = ZZ.map([[[1], [2, 3]]])
70 >>> dmp_ground_LC(f, 2, ZZ)
71 1
73 """
74 while u:
75 f = dmp_LC(f, K)
76 u -= 1
78 return dup_LC(f, K)
81def dmp_ground_TC(f, u, K):
82 """
83 Return the ground trailing coefficient.
85 Examples
86 ========
88 >>> from sympy.polys.domains import ZZ
89 >>> from sympy.polys.densebasic import dmp_ground_TC
91 >>> f = ZZ.map([[[1], [2, 3]]])
93 >>> dmp_ground_TC(f, 2, ZZ)
94 3
96 """
97 while u:
98 f = dmp_TC(f, K)
99 u -= 1
101 return dup_TC(f, K)
104def dmp_true_LT(f, u, K):
105 """
106 Return the leading term ``c * x_1**n_1 ... x_k**n_k``.
108 Examples
109 ========
111 >>> from sympy.polys.domains import ZZ
112 >>> from sympy.polys.densebasic import dmp_true_LT
114 >>> f = ZZ.map([[4], [2, 0], [3, 0, 0]])
116 >>> dmp_true_LT(f, 1, ZZ)
117 ((2, 0), 4)
119 """
120 monom = []
122 while u:
123 monom.append(len(f) - 1)
124 f, u = f[0], u - 1
126 if not f:
127 monom.append(0)
128 else:
129 monom.append(len(f) - 1)
131 return tuple(monom), dup_LC(f, K)
134def dup_degree(f):
135 """
136 Return the leading degree of ``f`` in ``K[x]``.
138 Note that the degree of 0 is negative infinity (the SymPy object -oo).
140 Examples
141 ========
143 >>> from sympy.polys.domains import ZZ
144 >>> from sympy.polys.densebasic import dup_degree
146 >>> f = ZZ.map([1, 2, 0, 3])
148 >>> dup_degree(f)
149 3
151 """
152 if not f:
153 return -oo
154 return len(f) - 1
157def dmp_degree(f, u):
158 """
159 Return the leading degree of ``f`` in ``x_0`` in ``K[X]``.
161 Note that the degree of 0 is negative infinity (the SymPy object -oo).
163 Examples
164 ========
166 >>> from sympy.polys.domains import ZZ
167 >>> from sympy.polys.densebasic import dmp_degree
169 >>> dmp_degree([[[]]], 2)
170 -oo
172 >>> f = ZZ.map([[2], [1, 2, 3]])
174 >>> dmp_degree(f, 1)
175 1
177 """
178 if dmp_zero_p(f, u):
179 return -oo
180 else:
181 return len(f) - 1
184def _rec_degree_in(g, v, i, j):
185 """Recursive helper function for :func:`dmp_degree_in`."""
186 if i == j:
187 return dmp_degree(g, v)
189 v, i = v - 1, i + 1
191 return max([ _rec_degree_in(c, v, i, j) for c in g ])
194def dmp_degree_in(f, j, u):
195 """
196 Return the leading degree of ``f`` in ``x_j`` in ``K[X]``.
198 Examples
199 ========
201 >>> from sympy.polys.domains import ZZ
202 >>> from sympy.polys.densebasic import dmp_degree_in
204 >>> f = ZZ.map([[2], [1, 2, 3]])
206 >>> dmp_degree_in(f, 0, 1)
207 1
208 >>> dmp_degree_in(f, 1, 1)
209 2
211 """
212 if not j:
213 return dmp_degree(f, u)
214 if j < 0 or j > u:
215 raise IndexError("0 <= j <= %s expected, got %s" % (u, j))
217 return _rec_degree_in(f, u, 0, j)
220def _rec_degree_list(g, v, i, degs):
221 """Recursive helper for :func:`dmp_degree_list`."""
222 degs[i] = max(degs[i], dmp_degree(g, v))
224 if v > 0:
225 v, i = v - 1, i + 1
227 for c in g:
228 _rec_degree_list(c, v, i, degs)
231def dmp_degree_list(f, u):
232 """
233 Return a list of degrees of ``f`` in ``K[X]``.
235 Examples
236 ========
238 >>> from sympy.polys.domains import ZZ
239 >>> from sympy.polys.densebasic import dmp_degree_list
241 >>> f = ZZ.map([[1], [1, 2, 3]])
243 >>> dmp_degree_list(f, 1)
244 (1, 2)
246 """
247 degs = [-oo]*(u + 1)
248 _rec_degree_list(f, u, 0, degs)
249 return tuple(degs)
252def dup_strip(f):
253 """
254 Remove leading zeros from ``f`` in ``K[x]``.
256 Examples
257 ========
259 >>> from sympy.polys.densebasic import dup_strip
261 >>> dup_strip([0, 0, 1, 2, 3, 0])
262 [1, 2, 3, 0]
264 """
265 if not f or f[0]:
266 return f
268 i = 0
270 for cf in f:
271 if cf:
272 break
273 else:
274 i += 1
276 return f[i:]
279def dmp_strip(f, u):
280 """
281 Remove leading zeros from ``f`` in ``K[X]``.
283 Examples
284 ========
286 >>> from sympy.polys.densebasic import dmp_strip
288 >>> dmp_strip([[], [0, 1, 2], [1]], 1)
289 [[0, 1, 2], [1]]
291 """
292 if not u:
293 return dup_strip(f)
295 if dmp_zero_p(f, u):
296 return f
298 i, v = 0, u - 1
300 for c in f:
301 if not dmp_zero_p(c, v):
302 break
303 else:
304 i += 1
306 if i == len(f):
307 return dmp_zero(u)
308 else:
309 return f[i:]
312def _rec_validate(f, g, i, K):
313 """Recursive helper for :func:`dmp_validate`."""
314 if not isinstance(g, list):
315 if K is not None and not K.of_type(g):
316 raise TypeError("%s in %s in not of type %s" % (g, f, K.dtype))
318 return {i - 1}
319 elif not g:
320 return {i}
321 else:
322 levels = set()
324 for c in g:
325 levels |= _rec_validate(f, c, i + 1, K)
327 return levels
330def _rec_strip(g, v):
331 """Recursive helper for :func:`_rec_strip`."""
332 if not v:
333 return dup_strip(g)
335 w = v - 1
337 return dmp_strip([ _rec_strip(c, w) for c in g ], v)
340def dmp_validate(f, K=None):
341 """
342 Return the number of levels in ``f`` and recursively strip it.
344 Examples
345 ========
347 >>> from sympy.polys.densebasic import dmp_validate
349 >>> dmp_validate([[], [0, 1, 2], [1]])
350 ([[1, 2], [1]], 1)
352 >>> dmp_validate([[1], 1])
353 Traceback (most recent call last):
354 ...
355 ValueError: invalid data structure for a multivariate polynomial
357 """
358 levels = _rec_validate(f, f, 0, K)
360 u = levels.pop()
362 if not levels:
363 return _rec_strip(f, u), u
364 else:
365 raise ValueError(
366 "invalid data structure for a multivariate polynomial")
369def dup_reverse(f):
370 """
371 Compute ``x**n * f(1/x)``, i.e.: reverse ``f`` in ``K[x]``.
373 Examples
374 ========
376 >>> from sympy.polys.domains import ZZ
377 >>> from sympy.polys.densebasic import dup_reverse
379 >>> f = ZZ.map([1, 2, 3, 0])
381 >>> dup_reverse(f)
382 [3, 2, 1]
384 """
385 return dup_strip(list(reversed(f)))
388def dup_copy(f):
389 """
390 Create a new copy of a polynomial ``f`` in ``K[x]``.
392 Examples
393 ========
395 >>> from sympy.polys.domains import ZZ
396 >>> from sympy.polys.densebasic import dup_copy
398 >>> f = ZZ.map([1, 2, 3, 0])
400 >>> dup_copy([1, 2, 3, 0])
401 [1, 2, 3, 0]
403 """
404 return list(f)
407def dmp_copy(f, u):
408 """
409 Create a new copy of a polynomial ``f`` in ``K[X]``.
411 Examples
412 ========
414 >>> from sympy.polys.domains import ZZ
415 >>> from sympy.polys.densebasic import dmp_copy
417 >>> f = ZZ.map([[1], [1, 2]])
419 >>> dmp_copy(f, 1)
420 [[1], [1, 2]]
422 """
423 if not u:
424 return list(f)
426 v = u - 1
428 return [ dmp_copy(c, v) for c in f ]
431def dup_to_tuple(f):
432 """
433 Convert `f` into a tuple.
435 This is needed for hashing. This is similar to dup_copy().
437 Examples
438 ========
440 >>> from sympy.polys.domains import ZZ
441 >>> from sympy.polys.densebasic import dup_copy
443 >>> f = ZZ.map([1, 2, 3, 0])
445 >>> dup_copy([1, 2, 3, 0])
446 [1, 2, 3, 0]
448 """
449 return tuple(f)
452def dmp_to_tuple(f, u):
453 """
454 Convert `f` into a nested tuple of tuples.
456 This is needed for hashing. This is similar to dmp_copy().
458 Examples
459 ========
461 >>> from sympy.polys.domains import ZZ
462 >>> from sympy.polys.densebasic import dmp_to_tuple
464 >>> f = ZZ.map([[1], [1, 2]])
466 >>> dmp_to_tuple(f, 1)
467 ((1,), (1, 2))
469 """
470 if not u:
471 return tuple(f)
472 v = u - 1
474 return tuple(dmp_to_tuple(c, v) for c in f)
477def dup_normal(f, K):
478 """
479 Normalize univariate polynomial in the given domain.
481 Examples
482 ========
484 >>> from sympy.polys.domains import ZZ
485 >>> from sympy.polys.densebasic import dup_normal
487 >>> dup_normal([0, 1.5, 2, 3], ZZ)
488 [1, 2, 3]
490 """
491 return dup_strip([ K.normal(c) for c in f ])
494def dmp_normal(f, u, K):
495 """
496 Normalize a multivariate polynomial in the given domain.
498 Examples
499 ========
501 >>> from sympy.polys.domains import ZZ
502 >>> from sympy.polys.densebasic import dmp_normal
504 >>> dmp_normal([[], [0, 1.5, 2]], 1, ZZ)
505 [[1, 2]]
507 """
508 if not u:
509 return dup_normal(f, K)
511 v = u - 1
513 return dmp_strip([ dmp_normal(c, v, K) for c in f ], u)
516def dup_convert(f, K0, K1):
517 """
518 Convert the ground domain of ``f`` from ``K0`` to ``K1``.
520 Examples
521 ========
523 >>> from sympy.polys.rings import ring
524 >>> from sympy.polys.domains import ZZ
525 >>> from sympy.polys.densebasic import dup_convert
527 >>> R, x = ring("x", ZZ)
529 >>> dup_convert([R(1), R(2)], R.to_domain(), ZZ)
530 [1, 2]
531 >>> dup_convert([ZZ(1), ZZ(2)], ZZ, R.to_domain())
532 [1, 2]
534 """
535 if K0 is not None and K0 == K1:
536 return f
537 else:
538 return dup_strip([ K1.convert(c, K0) for c in f ])
541def dmp_convert(f, u, K0, K1):
542 """
543 Convert the ground domain of ``f`` from ``K0`` to ``K1``.
545 Examples
546 ========
548 >>> from sympy.polys.rings import ring
549 >>> from sympy.polys.domains import ZZ
550 >>> from sympy.polys.densebasic import dmp_convert
552 >>> R, x = ring("x", ZZ)
554 >>> dmp_convert([[R(1)], [R(2)]], 1, R.to_domain(), ZZ)
555 [[1], [2]]
556 >>> dmp_convert([[ZZ(1)], [ZZ(2)]], 1, ZZ, R.to_domain())
557 [[1], [2]]
559 """
560 if not u:
561 return dup_convert(f, K0, K1)
562 if K0 is not None and K0 == K1:
563 return f
565 v = u - 1
567 return dmp_strip([ dmp_convert(c, v, K0, K1) for c in f ], u)
570def dup_from_sympy(f, K):
571 """
572 Convert the ground domain of ``f`` from SymPy to ``K``.
574 Examples
575 ========
577 >>> from sympy import S
578 >>> from sympy.polys.domains import ZZ
579 >>> from sympy.polys.densebasic import dup_from_sympy
581 >>> dup_from_sympy([S(1), S(2)], ZZ) == [ZZ(1), ZZ(2)]
582 True
584 """
585 return dup_strip([ K.from_sympy(c) for c in f ])
588def dmp_from_sympy(f, u, K):
589 """
590 Convert the ground domain of ``f`` from SymPy to ``K``.
592 Examples
593 ========
595 >>> from sympy import S
596 >>> from sympy.polys.domains import ZZ
597 >>> from sympy.polys.densebasic import dmp_from_sympy
599 >>> dmp_from_sympy([[S(1)], [S(2)]], 1, ZZ) == [[ZZ(1)], [ZZ(2)]]
600 True
602 """
603 if not u:
604 return dup_from_sympy(f, K)
606 v = u - 1
608 return dmp_strip([ dmp_from_sympy(c, v, K) for c in f ], u)
611def dup_nth(f, n, K):
612 """
613 Return the ``n``-th coefficient of ``f`` in ``K[x]``.
615 Examples
616 ========
618 >>> from sympy.polys.domains import ZZ
619 >>> from sympy.polys.densebasic import dup_nth
621 >>> f = ZZ.map([1, 2, 3])
623 >>> dup_nth(f, 0, ZZ)
624 3
625 >>> dup_nth(f, 4, ZZ)
626 0
628 """
629 if n < 0:
630 raise IndexError("'n' must be non-negative, got %i" % n)
631 elif n >= len(f):
632 return K.zero
633 else:
634 return f[dup_degree(f) - n]
637def dmp_nth(f, n, u, K):
638 """
639 Return the ``n``-th coefficient of ``f`` in ``K[x]``.
641 Examples
642 ========
644 >>> from sympy.polys.domains import ZZ
645 >>> from sympy.polys.densebasic import dmp_nth
647 >>> f = ZZ.map([[1], [2], [3]])
649 >>> dmp_nth(f, 0, 1, ZZ)
650 [3]
651 >>> dmp_nth(f, 4, 1, ZZ)
652 []
654 """
655 if n < 0:
656 raise IndexError("'n' must be non-negative, got %i" % n)
657 elif n >= len(f):
658 return dmp_zero(u - 1)
659 else:
660 return f[dmp_degree(f, u) - n]
663def dmp_ground_nth(f, N, u, K):
664 """
665 Return the ground ``n``-th coefficient of ``f`` in ``K[x]``.
667 Examples
668 ========
670 >>> from sympy.polys.domains import ZZ
671 >>> from sympy.polys.densebasic import dmp_ground_nth
673 >>> f = ZZ.map([[1], [2, 3]])
675 >>> dmp_ground_nth(f, (0, 1), 1, ZZ)
676 2
678 """
679 v = u
681 for n in N:
682 if n < 0:
683 raise IndexError("`n` must be non-negative, got %i" % n)
684 elif n >= len(f):
685 return K.zero
686 else:
687 d = dmp_degree(f, v)
688 if d == -oo:
689 d = -1
690 f, v = f[d - n], v - 1
692 return f
695def dmp_zero_p(f, u):
696 """
697 Return ``True`` if ``f`` is zero in ``K[X]``.
699 Examples
700 ========
702 >>> from sympy.polys.densebasic import dmp_zero_p
704 >>> dmp_zero_p([[[[[]]]]], 4)
705 True
706 >>> dmp_zero_p([[[[[1]]]]], 4)
707 False
709 """
710 while u:
711 if len(f) != 1:
712 return False
714 f = f[0]
715 u -= 1
717 return not f
720def dmp_zero(u):
721 """
722 Return a multivariate zero.
724 Examples
725 ========
727 >>> from sympy.polys.densebasic import dmp_zero
729 >>> dmp_zero(4)
730 [[[[[]]]]]
732 """
733 r = []
735 for i in range(u):
736 r = [r]
738 return r
741def dmp_one_p(f, u, K):
742 """
743 Return ``True`` if ``f`` is one in ``K[X]``.
745 Examples
746 ========
748 >>> from sympy.polys.domains import ZZ
749 >>> from sympy.polys.densebasic import dmp_one_p
751 >>> dmp_one_p([[[ZZ(1)]]], 2, ZZ)
752 True
754 """
755 return dmp_ground_p(f, K.one, u)
758def dmp_one(u, K):
759 """
760 Return a multivariate one over ``K``.
762 Examples
763 ========
765 >>> from sympy.polys.domains import ZZ
766 >>> from sympy.polys.densebasic import dmp_one
768 >>> dmp_one(2, ZZ)
769 [[[1]]]
771 """
772 return dmp_ground(K.one, u)
775def dmp_ground_p(f, c, u):
776 """
777 Return True if ``f`` is constant in ``K[X]``.
779 Examples
780 ========
782 >>> from sympy.polys.densebasic import dmp_ground_p
784 >>> dmp_ground_p([[[3]]], 3, 2)
785 True
786 >>> dmp_ground_p([[[4]]], None, 2)
787 True
789 """
790 if c is not None and not c:
791 return dmp_zero_p(f, u)
793 while u:
794 if len(f) != 1:
795 return False
796 f = f[0]
797 u -= 1
799 if c is None:
800 return len(f) <= 1
801 else:
802 return f == [c]
805def dmp_ground(c, u):
806 """
807 Return a multivariate constant.
809 Examples
810 ========
812 >>> from sympy.polys.densebasic import dmp_ground
814 >>> dmp_ground(3, 5)
815 [[[[[[3]]]]]]
816 >>> dmp_ground(1, -1)
817 1
819 """
820 if not c:
821 return dmp_zero(u)
823 for i in range(u + 1):
824 c = [c]
826 return c
829def dmp_zeros(n, u, K):
830 """
831 Return a list of multivariate zeros.
833 Examples
834 ========
836 >>> from sympy.polys.domains import ZZ
837 >>> from sympy.polys.densebasic import dmp_zeros
839 >>> dmp_zeros(3, 2, ZZ)
840 [[[[]]], [[[]]], [[[]]]]
841 >>> dmp_zeros(3, -1, ZZ)
842 [0, 0, 0]
844 """
845 if not n:
846 return []
848 if u < 0:
849 return [K.zero]*n
850 else:
851 return [ dmp_zero(u) for i in range(n) ]
854def dmp_grounds(c, n, u):
855 """
856 Return a list of multivariate constants.
858 Examples
859 ========
861 >>> from sympy.polys.domains import ZZ
862 >>> from sympy.polys.densebasic import dmp_grounds
864 >>> dmp_grounds(ZZ(4), 3, 2)
865 [[[[4]]], [[[4]]], [[[4]]]]
866 >>> dmp_grounds(ZZ(4), 3, -1)
867 [4, 4, 4]
869 """
870 if not n:
871 return []
873 if u < 0:
874 return [c]*n
875 else:
876 return [ dmp_ground(c, u) for i in range(n) ]
879def dmp_negative_p(f, u, K):
880 """
881 Return ``True`` if ``LC(f)`` is negative.
883 Examples
884 ========
886 >>> from sympy.polys.domains import ZZ
887 >>> from sympy.polys.densebasic import dmp_negative_p
889 >>> dmp_negative_p([[ZZ(1)], [-ZZ(1)]], 1, ZZ)
890 False
891 >>> dmp_negative_p([[-ZZ(1)], [ZZ(1)]], 1, ZZ)
892 True
894 """
895 return K.is_negative(dmp_ground_LC(f, u, K))
898def dmp_positive_p(f, u, K):
899 """
900 Return ``True`` if ``LC(f)`` is positive.
902 Examples
903 ========
905 >>> from sympy.polys.domains import ZZ
906 >>> from sympy.polys.densebasic import dmp_positive_p
908 >>> dmp_positive_p([[ZZ(1)], [-ZZ(1)]], 1, ZZ)
909 True
910 >>> dmp_positive_p([[-ZZ(1)], [ZZ(1)]], 1, ZZ)
911 False
913 """
914 return K.is_positive(dmp_ground_LC(f, u, K))
917def dup_from_dict(f, K):
918 """
919 Create a ``K[x]`` polynomial from a ``dict``.
921 Examples
922 ========
924 >>> from sympy.polys.domains import ZZ
925 >>> from sympy.polys.densebasic import dup_from_dict
927 >>> dup_from_dict({(0,): ZZ(7), (2,): ZZ(5), (4,): ZZ(1)}, ZZ)
928 [1, 0, 5, 0, 7]
929 >>> dup_from_dict({}, ZZ)
930 []
932 """
933 if not f:
934 return []
936 n, h = max(f.keys()), []
938 if isinstance(n, int):
939 for k in range(n, -1, -1):
940 h.append(f.get(k, K.zero))
941 else:
942 (n,) = n
944 for k in range(n, -1, -1):
945 h.append(f.get((k,), K.zero))
947 return dup_strip(h)
950def dup_from_raw_dict(f, K):
951 """
952 Create a ``K[x]`` polynomial from a raw ``dict``.
954 Examples
955 ========
957 >>> from sympy.polys.domains import ZZ
958 >>> from sympy.polys.densebasic import dup_from_raw_dict
960 >>> dup_from_raw_dict({0: ZZ(7), 2: ZZ(5), 4: ZZ(1)}, ZZ)
961 [1, 0, 5, 0, 7]
963 """
964 if not f:
965 return []
967 n, h = max(f.keys()), []
969 for k in range(n, -1, -1):
970 h.append(f.get(k, K.zero))
972 return dup_strip(h)
975def dmp_from_dict(f, u, K):
976 """
977 Create a ``K[X]`` polynomial from a ``dict``.
979 Examples
980 ========
982 >>> from sympy.polys.domains import ZZ
983 >>> from sympy.polys.densebasic import dmp_from_dict
985 >>> dmp_from_dict({(0, 0): ZZ(3), (0, 1): ZZ(2), (2, 1): ZZ(1)}, 1, ZZ)
986 [[1, 0], [], [2, 3]]
987 >>> dmp_from_dict({}, 0, ZZ)
988 []
990 """
991 if not u:
992 return dup_from_dict(f, K)
993 if not f:
994 return dmp_zero(u)
996 coeffs = {}
998 for monom, coeff in f.items():
999 head, tail = monom[0], monom[1:]
1001 if head in coeffs:
1002 coeffs[head][tail] = coeff
1003 else:
1004 coeffs[head] = { tail: coeff }
1006 n, v, h = max(coeffs.keys()), u - 1, []
1008 for k in range(n, -1, -1):
1009 coeff = coeffs.get(k)
1011 if coeff is not None:
1012 h.append(dmp_from_dict(coeff, v, K))
1013 else:
1014 h.append(dmp_zero(v))
1016 return dmp_strip(h, u)
1019def dup_to_dict(f, K=None, zero=False):
1020 """
1021 Convert ``K[x]`` polynomial to a ``dict``.
1023 Examples
1024 ========
1026 >>> from sympy.polys.densebasic import dup_to_dict
1028 >>> dup_to_dict([1, 0, 5, 0, 7])
1029 {(0,): 7, (2,): 5, (4,): 1}
1030 >>> dup_to_dict([])
1031 {}
1033 """
1034 if not f and zero:
1035 return {(0,): K.zero}
1037 n, result = len(f) - 1, {}
1039 for k in range(0, n + 1):
1040 if f[n - k]:
1041 result[(k,)] = f[n - k]
1043 return result
1046def dup_to_raw_dict(f, K=None, zero=False):
1047 """
1048 Convert a ``K[x]`` polynomial to a raw ``dict``.
1050 Examples
1051 ========
1053 >>> from sympy.polys.densebasic import dup_to_raw_dict
1055 >>> dup_to_raw_dict([1, 0, 5, 0, 7])
1056 {0: 7, 2: 5, 4: 1}
1058 """
1059 if not f and zero:
1060 return {0: K.zero}
1062 n, result = len(f) - 1, {}
1064 for k in range(0, n + 1):
1065 if f[n - k]:
1066 result[k] = f[n - k]
1068 return result
1071def dmp_to_dict(f, u, K=None, zero=False):
1072 """
1073 Convert a ``K[X]`` polynomial to a ``dict````.
1075 Examples
1076 ========
1078 >>> from sympy.polys.densebasic import dmp_to_dict
1080 >>> dmp_to_dict([[1, 0], [], [2, 3]], 1)
1081 {(0, 0): 3, (0, 1): 2, (2, 1): 1}
1082 >>> dmp_to_dict([], 0)
1083 {}
1085 """
1086 if not u:
1087 return dup_to_dict(f, K, zero=zero)
1089 if dmp_zero_p(f, u) and zero:
1090 return {(0,)*(u + 1): K.zero}
1092 n, v, result = dmp_degree(f, u), u - 1, {}
1094 if n == -oo:
1095 n = -1
1097 for k in range(0, n + 1):
1098 h = dmp_to_dict(f[n - k], v)
1100 for exp, coeff in h.items():
1101 result[(k,) + exp] = coeff
1103 return result
1106def dmp_swap(f, i, j, u, K):
1107 """
1108 Transform ``K[..x_i..x_j..]`` to ``K[..x_j..x_i..]``.
1110 Examples
1111 ========
1113 >>> from sympy.polys.domains import ZZ
1114 >>> from sympy.polys.densebasic import dmp_swap
1116 >>> f = ZZ.map([[[2], [1, 0]], []])
1118 >>> dmp_swap(f, 0, 1, 2, ZZ)
1119 [[[2], []], [[1, 0], []]]
1120 >>> dmp_swap(f, 1, 2, 2, ZZ)
1121 [[[1], [2, 0]], [[]]]
1122 >>> dmp_swap(f, 0, 2, 2, ZZ)
1123 [[[1, 0]], [[2, 0], []]]
1125 """
1126 if i < 0 or j < 0 or i > u or j > u:
1127 raise IndexError("0 <= i < j <= %s expected" % u)
1128 elif i == j:
1129 return f
1131 F, H = dmp_to_dict(f, u), {}
1133 for exp, coeff in F.items():
1134 H[exp[:i] + (exp[j],) +
1135 exp[i + 1:j] +
1136 (exp[i],) + exp[j + 1:]] = coeff
1138 return dmp_from_dict(H, u, K)
1141def dmp_permute(f, P, u, K):
1142 """
1143 Return a polynomial in ``K[x_{P(1)},..,x_{P(n)}]``.
1145 Examples
1146 ========
1148 >>> from sympy.polys.domains import ZZ
1149 >>> from sympy.polys.densebasic import dmp_permute
1151 >>> f = ZZ.map([[[2], [1, 0]], []])
1153 >>> dmp_permute(f, [1, 0, 2], 2, ZZ)
1154 [[[2], []], [[1, 0], []]]
1155 >>> dmp_permute(f, [1, 2, 0], 2, ZZ)
1156 [[[1], []], [[2, 0], []]]
1158 """
1159 F, H = dmp_to_dict(f, u), {}
1161 for exp, coeff in F.items():
1162 new_exp = [0]*len(exp)
1164 for e, p in zip(exp, P):
1165 new_exp[p] = e
1167 H[tuple(new_exp)] = coeff
1169 return dmp_from_dict(H, u, K)
1172def dmp_nest(f, l, K):
1173 """
1174 Return a multivariate value nested ``l``-levels.
1176 Examples
1177 ========
1179 >>> from sympy.polys.domains import ZZ
1180 >>> from sympy.polys.densebasic import dmp_nest
1182 >>> dmp_nest([[ZZ(1)]], 2, ZZ)
1183 [[[[1]]]]
1185 """
1186 if not isinstance(f, list):
1187 return dmp_ground(f, l)
1189 for i in range(l):
1190 f = [f]
1192 return f
1195def dmp_raise(f, l, u, K):
1196 """
1197 Return a multivariate polynomial raised ``l``-levels.
1199 Examples
1200 ========
1202 >>> from sympy.polys.domains import ZZ
1203 >>> from sympy.polys.densebasic import dmp_raise
1205 >>> f = ZZ.map([[], [1, 2]])
1207 >>> dmp_raise(f, 2, 1, ZZ)
1208 [[[[]]], [[[1]], [[2]]]]
1210 """
1211 if not l:
1212 return f
1214 if not u:
1215 if not f:
1216 return dmp_zero(l)
1218 k = l - 1
1220 return [ dmp_ground(c, k) for c in f ]
1222 v = u - 1
1224 return [ dmp_raise(c, l, v, K) for c in f ]
1227def dup_deflate(f, K):
1228 """
1229 Map ``x**m`` to ``y`` in a polynomial in ``K[x]``.
1231 Examples
1232 ========
1234 >>> from sympy.polys.domains import ZZ
1235 >>> from sympy.polys.densebasic import dup_deflate
1237 >>> f = ZZ.map([1, 0, 0, 1, 0, 0, 1])
1239 >>> dup_deflate(f, ZZ)
1240 (3, [1, 1, 1])
1242 """
1243 if dup_degree(f) <= 0:
1244 return 1, f
1246 g = 0
1248 for i in range(len(f)):
1249 if not f[-i - 1]:
1250 continue
1252 g = igcd(g, i)
1254 if g == 1:
1255 return 1, f
1257 return g, f[::g]
1260def dmp_deflate(f, u, K):
1261 """
1262 Map ``x_i**m_i`` to ``y_i`` in a polynomial in ``K[X]``.
1264 Examples
1265 ========
1267 >>> from sympy.polys.domains import ZZ
1268 >>> from sympy.polys.densebasic import dmp_deflate
1270 >>> f = ZZ.map([[1, 0, 0, 2], [], [3, 0, 0, 4]])
1272 >>> dmp_deflate(f, 1, ZZ)
1273 ((2, 3), [[1, 2], [3, 4]])
1275 """
1276 if dmp_zero_p(f, u):
1277 return (1,)*(u + 1), f
1279 F = dmp_to_dict(f, u)
1280 B = [0]*(u + 1)
1282 for M in F.keys():
1283 for i, m in enumerate(M):
1284 B[i] = igcd(B[i], m)
1286 for i, b in enumerate(B):
1287 if not b:
1288 B[i] = 1
1290 B = tuple(B)
1292 if all(b == 1 for b in B):
1293 return B, f
1295 H = {}
1297 for A, coeff in F.items():
1298 N = [ a // b for a, b in zip(A, B) ]
1299 H[tuple(N)] = coeff
1301 return B, dmp_from_dict(H, u, K)
1304def dup_multi_deflate(polys, K):
1305 """
1306 Map ``x**m`` to ``y`` in a set of polynomials in ``K[x]``.
1308 Examples
1309 ========
1311 >>> from sympy.polys.domains import ZZ
1312 >>> from sympy.polys.densebasic import dup_multi_deflate
1314 >>> f = ZZ.map([1, 0, 2, 0, 3])
1315 >>> g = ZZ.map([4, 0, 0])
1317 >>> dup_multi_deflate((f, g), ZZ)
1318 (2, ([1, 2, 3], [4, 0]))
1320 """
1321 G = 0
1323 for p in polys:
1324 if dup_degree(p) <= 0:
1325 return 1, polys
1327 g = 0
1329 for i in range(len(p)):
1330 if not p[-i - 1]:
1331 continue
1333 g = igcd(g, i)
1335 if g == 1:
1336 return 1, polys
1338 G = igcd(G, g)
1340 return G, tuple([ p[::G] for p in polys ])
1343def dmp_multi_deflate(polys, u, K):
1344 """
1345 Map ``x_i**m_i`` to ``y_i`` in a set of polynomials in ``K[X]``.
1347 Examples
1348 ========
1350 >>> from sympy.polys.domains import ZZ
1351 >>> from sympy.polys.densebasic import dmp_multi_deflate
1353 >>> f = ZZ.map([[1, 0, 0, 2], [], [3, 0, 0, 4]])
1354 >>> g = ZZ.map([[1, 0, 2], [], [3, 0, 4]])
1356 >>> dmp_multi_deflate((f, g), 1, ZZ)
1357 ((2, 1), ([[1, 0, 0, 2], [3, 0, 0, 4]], [[1, 0, 2], [3, 0, 4]]))
1359 """
1360 if not u:
1361 M, H = dup_multi_deflate(polys, K)
1362 return (M,), H
1364 F, B = [], [0]*(u + 1)
1366 for p in polys:
1367 f = dmp_to_dict(p, u)
1369 if not dmp_zero_p(p, u):
1370 for M in f.keys():
1371 for i, m in enumerate(M):
1372 B[i] = igcd(B[i], m)
1374 F.append(f)
1376 for i, b in enumerate(B):
1377 if not b:
1378 B[i] = 1
1380 B = tuple(B)
1382 if all(b == 1 for b in B):
1383 return B, polys
1385 H = []
1387 for f in F:
1388 h = {}
1390 for A, coeff in f.items():
1391 N = [ a // b for a, b in zip(A, B) ]
1392 h[tuple(N)] = coeff
1394 H.append(dmp_from_dict(h, u, K))
1396 return B, tuple(H)
1399def dup_inflate(f, m, K):
1400 """
1401 Map ``y`` to ``x**m`` in a polynomial in ``K[x]``.
1403 Examples
1404 ========
1406 >>> from sympy.polys.domains import ZZ
1407 >>> from sympy.polys.densebasic import dup_inflate
1409 >>> f = ZZ.map([1, 1, 1])
1411 >>> dup_inflate(f, 3, ZZ)
1412 [1, 0, 0, 1, 0, 0, 1]
1414 """
1415 if m <= 0:
1416 raise IndexError("'m' must be positive, got %s" % m)
1417 if m == 1 or not f:
1418 return f
1420 result = [f[0]]
1422 for coeff in f[1:]:
1423 result.extend([K.zero]*(m - 1))
1424 result.append(coeff)
1426 return result
1429def _rec_inflate(g, M, v, i, K):
1430 """Recursive helper for :func:`dmp_inflate`."""
1431 if not v:
1432 return dup_inflate(g, M[i], K)
1433 if M[i] <= 0:
1434 raise IndexError("all M[i] must be positive, got %s" % M[i])
1436 w, j = v - 1, i + 1
1438 g = [ _rec_inflate(c, M, w, j, K) for c in g ]
1440 result = [g[0]]
1442 for coeff in g[1:]:
1443 for _ in range(1, M[i]):
1444 result.append(dmp_zero(w))
1446 result.append(coeff)
1448 return result
1451def dmp_inflate(f, M, u, K):
1452 """
1453 Map ``y_i`` to ``x_i**k_i`` in a polynomial in ``K[X]``.
1455 Examples
1456 ========
1458 >>> from sympy.polys.domains import ZZ
1459 >>> from sympy.polys.densebasic import dmp_inflate
1461 >>> f = ZZ.map([[1, 2], [3, 4]])
1463 >>> dmp_inflate(f, (2, 3), 1, ZZ)
1464 [[1, 0, 0, 2], [], [3, 0, 0, 4]]
1466 """
1467 if not u:
1468 return dup_inflate(f, M[0], K)
1470 if all(m == 1 for m in M):
1471 return f
1472 else:
1473 return _rec_inflate(f, M, u, 0, K)
1476def dmp_exclude(f, u, K):
1477 """
1478 Exclude useless levels from ``f``.
1480 Return the levels excluded, the new excluded ``f``, and the new ``u``.
1482 Examples
1483 ========
1485 >>> from sympy.polys.domains import ZZ
1486 >>> from sympy.polys.densebasic import dmp_exclude
1488 >>> f = ZZ.map([[[1]], [[1], [2]]])
1490 >>> dmp_exclude(f, 2, ZZ)
1491 ([2], [[1], [1, 2]], 1)
1493 """
1494 if not u or dmp_ground_p(f, None, u):
1495 return [], f, u
1497 J, F = [], dmp_to_dict(f, u)
1499 for j in range(0, u + 1):
1500 for monom in F.keys():
1501 if monom[j]:
1502 break
1503 else:
1504 J.append(j)
1506 if not J:
1507 return [], f, u
1509 f = {}
1511 for monom, coeff in F.items():
1512 monom = list(monom)
1514 for j in reversed(J):
1515 del monom[j]
1517 f[tuple(monom)] = coeff
1519 u -= len(J)
1521 return J, dmp_from_dict(f, u, K), u
1524def dmp_include(f, J, u, K):
1525 """
1526 Include useless levels in ``f``.
1528 Examples
1529 ========
1531 >>> from sympy.polys.domains import ZZ
1532 >>> from sympy.polys.densebasic import dmp_include
1534 >>> f = ZZ.map([[1], [1, 2]])
1536 >>> dmp_include(f, [2], 1, ZZ)
1537 [[[1]], [[1], [2]]]
1539 """
1540 if not J:
1541 return f
1543 F, f = dmp_to_dict(f, u), {}
1545 for monom, coeff in F.items():
1546 monom = list(monom)
1548 for j in J:
1549 monom.insert(j, 0)
1551 f[tuple(monom)] = coeff
1553 u += len(J)
1555 return dmp_from_dict(f, u, K)
1558def dmp_inject(f, u, K, front=False):
1559 """
1560 Convert ``f`` from ``K[X][Y]`` to ``K[X,Y]``.
1562 Examples
1563 ========
1565 >>> from sympy.polys.rings import ring
1566 >>> from sympy.polys.domains import ZZ
1567 >>> from sympy.polys.densebasic import dmp_inject
1569 >>> R, x,y = ring("x,y", ZZ)
1571 >>> dmp_inject([R(1), x + 2], 0, R.to_domain())
1572 ([[[1]], [[1], [2]]], 2)
1573 >>> dmp_inject([R(1), x + 2], 0, R.to_domain(), front=True)
1574 ([[[1]], [[1, 2]]], 2)
1576 """
1577 f, h = dmp_to_dict(f, u), {}
1579 v = K.ngens - 1
1581 for f_monom, g in f.items():
1582 g = g.to_dict()
1584 for g_monom, c in g.items():
1585 if front:
1586 h[g_monom + f_monom] = c
1587 else:
1588 h[f_monom + g_monom] = c
1590 w = u + v + 1
1592 return dmp_from_dict(h, w, K.dom), w
1595def dmp_eject(f, u, K, front=False):
1596 """
1597 Convert ``f`` from ``K[X,Y]`` to ``K[X][Y]``.
1599 Examples
1600 ========
1602 >>> from sympy.polys.domains import ZZ
1603 >>> from sympy.polys.densebasic import dmp_eject
1605 >>> dmp_eject([[[1]], [[1], [2]]], 2, ZZ['x', 'y'])
1606 [1, x + 2]
1608 """
1609 f, h = dmp_to_dict(f, u), {}
1611 n = K.ngens
1612 v = u - K.ngens + 1
1614 for monom, c in f.items():
1615 if front:
1616 g_monom, f_monom = monom[:n], monom[n:]
1617 else:
1618 g_monom, f_monom = monom[-n:], monom[:-n]
1620 if f_monom in h:
1621 h[f_monom][g_monom] = c
1622 else:
1623 h[f_monom] = {g_monom: c}
1625 for monom, c in h.items():
1626 h[monom] = K(c)
1628 return dmp_from_dict(h, v - 1, K)
1631def dup_terms_gcd(f, K):
1632 """
1633 Remove GCD of terms from ``f`` in ``K[x]``.
1635 Examples
1636 ========
1638 >>> from sympy.polys.domains import ZZ
1639 >>> from sympy.polys.densebasic import dup_terms_gcd
1641 >>> f = ZZ.map([1, 0, 1, 0, 0])
1643 >>> dup_terms_gcd(f, ZZ)
1644 (2, [1, 0, 1])
1646 """
1647 if dup_TC(f, K) or not f:
1648 return 0, f
1650 i = 0
1652 for c in reversed(f):
1653 if not c:
1654 i += 1
1655 else:
1656 break
1658 return i, f[:-i]
1661def dmp_terms_gcd(f, u, K):
1662 """
1663 Remove GCD of terms from ``f`` in ``K[X]``.
1665 Examples
1666 ========
1668 >>> from sympy.polys.domains import ZZ
1669 >>> from sympy.polys.densebasic import dmp_terms_gcd
1671 >>> f = ZZ.map([[1, 0], [1, 0, 0], [], []])
1673 >>> dmp_terms_gcd(f, 1, ZZ)
1674 ((2, 1), [[1], [1, 0]])
1676 """
1677 if dmp_ground_TC(f, u, K) or dmp_zero_p(f, u):
1678 return (0,)*(u + 1), f
1680 F = dmp_to_dict(f, u)
1681 G = monomial_min(*list(F.keys()))
1683 if all(g == 0 for g in G):
1684 return G, f
1686 f = {}
1688 for monom, coeff in F.items():
1689 f[monomial_div(monom, G)] = coeff
1691 return G, dmp_from_dict(f, u, K)
1694def _rec_list_terms(g, v, monom):
1695 """Recursive helper for :func:`dmp_list_terms`."""
1696 d, terms = dmp_degree(g, v), []
1698 if not v:
1699 for i, c in enumerate(g):
1700 if not c:
1701 continue
1703 terms.append((monom + (d - i,), c))
1704 else:
1705 w = v - 1
1707 for i, c in enumerate(g):
1708 terms.extend(_rec_list_terms(c, w, monom + (d - i,)))
1710 return terms
1713def dmp_list_terms(f, u, K, order=None):
1714 """
1715 List all non-zero terms from ``f`` in the given order ``order``.
1717 Examples
1718 ========
1720 >>> from sympy.polys.domains import ZZ
1721 >>> from sympy.polys.densebasic import dmp_list_terms
1723 >>> f = ZZ.map([[1, 1], [2, 3]])
1725 >>> dmp_list_terms(f, 1, ZZ)
1726 [((1, 1), 1), ((1, 0), 1), ((0, 1), 2), ((0, 0), 3)]
1727 >>> dmp_list_terms(f, 1, ZZ, order='grevlex')
1728 [((1, 1), 1), ((1, 0), 1), ((0, 1), 2), ((0, 0), 3)]
1730 """
1731 def sort(terms, O):
1732 return sorted(terms, key=lambda term: O(term[0]), reverse=True)
1734 terms = _rec_list_terms(f, u, ())
1736 if not terms:
1737 return [((0,)*(u + 1), K.zero)]
1739 if order is None:
1740 return terms
1741 else:
1742 return sort(terms, monomial_key(order))
1745def dup_apply_pairs(f, g, h, args, K):
1746 """
1747 Apply ``h`` to pairs of coefficients of ``f`` and ``g``.
1749 Examples
1750 ========
1752 >>> from sympy.polys.domains import ZZ
1753 >>> from sympy.polys.densebasic import dup_apply_pairs
1755 >>> h = lambda x, y, z: 2*x + y - z
1757 >>> dup_apply_pairs([1, 2, 3], [3, 2, 1], h, (1,), ZZ)
1758 [4, 5, 6]
1760 """
1761 n, m = len(f), len(g)
1763 if n != m:
1764 if n > m:
1765 g = [K.zero]*(n - m) + g
1766 else:
1767 f = [K.zero]*(m - n) + f
1769 result = []
1771 for a, b in zip(f, g):
1772 result.append(h(a, b, *args))
1774 return dup_strip(result)
1777def dmp_apply_pairs(f, g, h, args, u, K):
1778 """
1779 Apply ``h`` to pairs of coefficients of ``f`` and ``g``.
1781 Examples
1782 ========
1784 >>> from sympy.polys.domains import ZZ
1785 >>> from sympy.polys.densebasic import dmp_apply_pairs
1787 >>> h = lambda x, y, z: 2*x + y - z
1789 >>> dmp_apply_pairs([[1], [2, 3]], [[3], [2, 1]], h, (1,), 1, ZZ)
1790 [[4], [5, 6]]
1792 """
1793 if not u:
1794 return dup_apply_pairs(f, g, h, args, K)
1796 n, m, v = len(f), len(g), u - 1
1798 if n != m:
1799 if n > m:
1800 g = dmp_zeros(n - m, v, K) + g
1801 else:
1802 f = dmp_zeros(m - n, v, K) + f
1804 result = []
1806 for a, b in zip(f, g):
1807 result.append(dmp_apply_pairs(a, b, h, args, v, K))
1809 return dmp_strip(result, u)
1812def dup_slice(f, m, n, K):
1813 """Take a continuous subsequence of terms of ``f`` in ``K[x]``. """
1814 k = len(f)
1816 if k >= m:
1817 M = k - m
1818 else:
1819 M = 0
1820 if k >= n:
1821 N = k - n
1822 else:
1823 N = 0
1825 f = f[N:M]
1827 if not f:
1828 return []
1829 else:
1830 return f + [K.zero]*m
1833def dmp_slice(f, m, n, u, K):
1834 """Take a continuous subsequence of terms of ``f`` in ``K[X]``. """
1835 return dmp_slice_in(f, m, n, 0, u, K)
1838def dmp_slice_in(f, m, n, j, u, K):
1839 """Take a continuous subsequence of terms of ``f`` in ``x_j`` in ``K[X]``. """
1840 if j < 0 or j > u:
1841 raise IndexError("-%s <= j < %s expected, got %s" % (u, u, j))
1843 if not u:
1844 return dup_slice(f, m, n, K)
1846 f, g = dmp_to_dict(f, u), {}
1848 for monom, coeff in f.items():
1849 k = monom[j]
1851 if k < m or k >= n:
1852 monom = monom[:j] + (0,) + monom[j + 1:]
1854 if monom in g:
1855 g[monom] += coeff
1856 else:
1857 g[monom] = coeff
1859 return dmp_from_dict(g, u, K)
1862def dup_random(n, a, b, K):
1863 """
1864 Return a polynomial of degree ``n`` with coefficients in ``[a, b]``.
1866 Examples
1867 ========
1869 >>> from sympy.polys.domains import ZZ
1870 >>> from sympy.polys.densebasic import dup_random
1872 >>> dup_random(3, -10, 10, ZZ) #doctest: +SKIP
1873 [-2, -8, 9, -4]
1875 """
1876 f = [ K.convert(random.randint(a, b)) for _ in range(0, n + 1) ]
1878 while not f[0]:
1879 f[0] = K.convert(random.randint(a, b))
1881 return f