Hot-keys on this page
r m x p toggle line displays
j k next/prev highlighted chunk
0 (zero) top of page
1 (one) first highlighted chunk
"""Basic tools for dense recursive polynomials in ``K[x]`` or ``K[X]``. """
from __future__ import print_function, division
from sympy.core import igcd from sympy import oo
from sympy.polys.monomials import monomial_min, monomial_div from sympy.polys.orderings import monomial_key from sympy.core.compatibility import range
import random
def poly_LC(f, K): """ Return leading coefficient of ``f``.
Examples ========
>>> from sympy.polys.domains import ZZ >>> from sympy.polys.densebasic import poly_LC
>>> poly_LC([], ZZ) 0 >>> poly_LC([ZZ(1), ZZ(2), ZZ(3)], ZZ) 1
""" else:
def poly_TC(f, K): """ Return trailing coefficient of ``f``.
Examples ========
>>> from sympy.polys.domains import ZZ >>> from sympy.polys.densebasic import poly_TC
>>> poly_TC([], ZZ) 0 >>> poly_TC([ZZ(1), ZZ(2), ZZ(3)], ZZ) 3
""" else:
dup_LC = dmp_LC = poly_LC dup_TC = dmp_TC = poly_TC
def dmp_ground_LC(f, u, K): """ Return the ground leading coefficient.
Examples ========
>>> from sympy.polys.domains import ZZ >>> from sympy.polys.densebasic import dmp_ground_LC
>>> f = ZZ.map([[[1], [2, 3]]])
>>> dmp_ground_LC(f, 2, ZZ) 1
"""
def dmp_ground_TC(f, u, K): """ Return the ground trailing coefficient.
Examples ========
>>> from sympy.polys.domains import ZZ >>> from sympy.polys.densebasic import dmp_ground_TC
>>> f = ZZ.map([[[1], [2, 3]]])
>>> dmp_ground_TC(f, 2, ZZ) 3
"""
def dmp_true_LT(f, u, K): """ Return the leading term ``c * x_1**n_1 ... x_k**n_k``.
Examples ========
>>> from sympy.polys.domains import ZZ >>> from sympy.polys.densebasic import dmp_true_LT
>>> f = ZZ.map([[4], [2, 0], [3, 0, 0]])
>>> dmp_true_LT(f, 1, ZZ) ((2, 0), 4)
""" monom = []
while u: monom.append(len(f) - 1) f, u = f[0], u - 1
if not f: monom.append(0) else: monom.append(len(f) - 1)
return tuple(monom), dup_LC(f, K)
def dup_degree(f): """ Return the leading degree of ``f`` in ``K[x]``.
Note that the degree of 0 is negative infinity (the SymPy object -oo).
Examples ========
>>> from sympy.polys.domains import ZZ >>> from sympy.polys.densebasic import dup_degree
>>> f = ZZ.map([1, 2, 0, 3])
>>> dup_degree(f) 3
"""
def dmp_degree(f, u): """ Return the leading degree of ``f`` in ``x_0`` in ``K[X]``.
Note that the degree of 0 is negative infinity (the SymPy object -oo).
Examples ========
>>> from sympy.polys.domains import ZZ >>> from sympy.polys.densebasic import dmp_degree
>>> dmp_degree([[[]]], 2) -oo
>>> f = ZZ.map([[2], [1, 2, 3]])
>>> dmp_degree(f, 1) 1
""" else:
def _rec_degree_in(g, v, i, j): """Recursive helper function for :func:`dmp_degree_in`."""
def dmp_degree_in(f, j, u): """ Return the leading degree of ``f`` in ``x_j`` in ``K[X]``.
Examples ========
>>> from sympy.polys.domains import ZZ >>> from sympy.polys.densebasic import dmp_degree_in
>>> f = ZZ.map([[2], [1, 2, 3]])
>>> dmp_degree_in(f, 0, 1) 1 >>> dmp_degree_in(f, 1, 1) 2
""" raise IndexError("0 <= j <= %s expected, got %s" % (u, j))
def _rec_degree_list(g, v, i, degs): """Recursive helper for :func:`dmp_degree_list`."""
def dmp_degree_list(f, u): """ Return a list of degrees of ``f`` in ``K[X]``.
Examples ========
>>> from sympy.polys.domains import ZZ >>> from sympy.polys.densebasic import dmp_degree_list
>>> f = ZZ.map([[1], [1, 2, 3]])
>>> dmp_degree_list(f, 1) (1, 2)
"""
def dup_strip(f): """ Remove leading zeros from ``f`` in ``K[x]``.
Examples ========
>>> from sympy.polys.densebasic import dup_strip
>>> dup_strip([0, 0, 1, 2, 3, 0]) [1, 2, 3, 0]
"""
else:
def dmp_strip(f, u): """ Remove leading zeros from ``f`` in ``K[X]``.
Examples ========
>>> from sympy.polys.densebasic import dmp_strip
>>> dmp_strip([[], [0, 1, 2], [1]], 1) [[0, 1, 2], [1]]
"""
else:
else:
def _rec_validate(f, g, i, K): """Recursive helper for :func:`dmp_validate`.""" raise TypeError("%s in %s in not of type %s" % (g, f, K.dtype))
return set([i]) else:
def _rec_strip(g, v): """Recursive helper for :func:`_rec_strip`."""
w = v - 1
return dmp_strip([ _rec_strip(c, w) for c in g ], v)
def dmp_validate(f, K=None): """ Return the number of levels in ``f`` and recursively strip it.
Examples ========
>>> from sympy.polys.densebasic import dmp_validate
>>> dmp_validate([[], [0, 1, 2], [1]]) ([[1, 2], [1]], 1)
>>> dmp_validate([[1], 1]) Traceback (most recent call last): ... ValueError: invalid data structure for a multivariate polynomial
"""
else: raise ValueError( "invalid data structure for a multivariate polynomial")
def dup_reverse(f): """ Compute ``x**n * f(1/x)``, i.e.: reverse ``f`` in ``K[x]``.
Examples ========
>>> from sympy.polys.domains import ZZ >>> from sympy.polys.densebasic import dup_reverse
>>> f = ZZ.map([1, 2, 3, 0])
>>> dup_reverse(f) [3, 2, 1]
"""
def dup_copy(f): """ Create a new copy of a polynomial ``f`` in ``K[x]``.
Examples ========
>>> from sympy.polys.domains import ZZ >>> from sympy.polys.densebasic import dup_copy
>>> f = ZZ.map([1, 2, 3, 0])
>>> dup_copy([1, 2, 3, 0]) [1, 2, 3, 0]
""" return list(f)
def dmp_copy(f, u): """ Create a new copy of a polynomial ``f`` in ``K[X]``.
Examples ========
>>> from sympy.polys.domains import ZZ >>> from sympy.polys.densebasic import dmp_copy
>>> f = ZZ.map([[1], [1, 2]])
>>> dmp_copy(f, 1) [[1], [1, 2]]
""" if not u: return list(f)
v = u - 1
return [ dmp_copy(c, v) for c in f ]
def dup_to_tuple(f): """ Convert `f` into a tuple.
This is needed for hashing. This is similar to dup_copy().
Examples ========
>>> from sympy.polys.domains import ZZ >>> from sympy.polys.densebasic import dup_copy
>>> f = ZZ.map([1, 2, 3, 0])
>>> dup_copy([1, 2, 3, 0]) [1, 2, 3, 0]
""" return tuple(f)
def dmp_to_tuple(f, u): """ Convert `f` into a nested tuple of tuples.
This is needed for hashing. This is similar to dmp_copy().
Examples ========
>>> from sympy.polys.domains import ZZ >>> from sympy.polys.densebasic import dmp_to_tuple
>>> f = ZZ.map([[1], [1, 2]])
>>> dmp_to_tuple(f, 1) ((1,), (1, 2))
"""
def dup_normal(f, K): """ Normalize univariate polynomial in the given domain.
Examples ========
>>> from sympy.polys.domains import ZZ >>> from sympy.polys.densebasic import dup_normal
>>> dup_normal([0, 1.5, 2, 3], ZZ) [1, 2, 3]
""" return dup_strip([ K.normal(c) for c in f ])
def dmp_normal(f, u, K): """ Normalize a multivariate polynomial in the given domain.
Examples ========
>>> from sympy.polys.domains import ZZ >>> from sympy.polys.densebasic import dmp_normal
>>> dmp_normal([[], [0, 1.5, 2]], 1, ZZ) [[1, 2]]
""" if not u: return dup_normal(f, K)
v = u - 1
return dmp_strip([ dmp_normal(c, v, K) for c in f ], u)
def dup_convert(f, K0, K1): """ Convert the ground domain of ``f`` from ``K0`` to ``K1``.
Examples ========
>>> from sympy.polys.rings import ring >>> from sympy.polys.domains import ZZ >>> from sympy.polys.densebasic import dup_convert
>>> R, x = ring("x", ZZ)
>>> dup_convert([R(1), R(2)], R.to_domain(), ZZ) [1, 2] >>> dup_convert([ZZ(1), ZZ(2)], ZZ, R.to_domain()) [1, 2]
""" return f else:
def dmp_convert(f, u, K0, K1): """ Convert the ground domain of ``f`` from ``K0`` to ``K1``.
Examples ========
>>> from sympy.polys.rings import ring >>> from sympy.polys.domains import ZZ >>> from sympy.polys.densebasic import dmp_convert
>>> R, x = ring("x", ZZ)
>>> dmp_convert([[R(1)], [R(2)]], 1, R.to_domain(), ZZ) [[1], [2]] >>> dmp_convert([[ZZ(1)], [ZZ(2)]], 1, ZZ, R.to_domain()) [[1], [2]]
""" return f
def dup_from_sympy(f, K): """ Convert the ground domain of ``f`` from SymPy to ``K``.
Examples ========
>>> from sympy import S >>> from sympy.polys.domains import ZZ >>> from sympy.polys.densebasic import dup_from_sympy
>>> dup_from_sympy([S(1), S(2)], ZZ) == [ZZ(1), ZZ(2)] True
""" return dup_strip([ K.from_sympy(c) for c in f ])
def dmp_from_sympy(f, u, K): """ Convert the ground domain of ``f`` from SymPy to ``K``.
Examples ========
>>> from sympy import S >>> from sympy.polys.domains import ZZ >>> from sympy.polys.densebasic import dmp_from_sympy
>>> dmp_from_sympy([[S(1)], [S(2)]], 1, ZZ) == [[ZZ(1)], [ZZ(2)]] True
""" if not u: return dup_from_sympy(f, K)
v = u - 1
return dmp_strip([ dmp_from_sympy(c, v, K) for c in f ], u)
def dup_nth(f, n, K): """ Return the ``n``-th coefficient of ``f`` in ``K[x]``.
Examples ========
>>> from sympy.polys.domains import ZZ >>> from sympy.polys.densebasic import dup_nth
>>> f = ZZ.map([1, 2, 3])
>>> dup_nth(f, 0, ZZ) 3 >>> dup_nth(f, 4, ZZ) 0
""" if n < 0: raise IndexError("'n' must be non-negative, got %i" % n) elif n >= len(f): return K.zero else: return f[dup_degree(f) - n]
def dmp_nth(f, n, u, K): """ Return the ``n``-th coefficient of ``f`` in ``K[x]``.
Examples ========
>>> from sympy.polys.domains import ZZ >>> from sympy.polys.densebasic import dmp_nth
>>> f = ZZ.map([[1], [2], [3]])
>>> dmp_nth(f, 0, 1, ZZ) [3] >>> dmp_nth(f, 4, 1, ZZ) []
""" if n < 0: raise IndexError("'n' must be non-negative, got %i" % n) elif n >= len(f): return dmp_zero(u - 1) else: return f[dmp_degree(f, u) - n]
def dmp_ground_nth(f, N, u, K): """ Return the ground ``n``-th coefficient of ``f`` in ``K[x]``.
Examples ========
>>> from sympy.polys.domains import ZZ >>> from sympy.polys.densebasic import dmp_ground_nth
>>> f = ZZ.map([[1], [2, 3]])
>>> dmp_ground_nth(f, (0, 1), 1, ZZ) 2
"""
raise IndexError("`n` must be non-negative, got %i" % n) return K.zero else: d = -1
def dmp_zero_p(f, u): """ Return ``True`` if ``f`` is zero in ``K[X]``.
Examples ========
>>> from sympy.polys.densebasic import dmp_zero_p
>>> dmp_zero_p([[[[[]]]]], 4) True >>> dmp_zero_p([[[[[1]]]]], 4) False
"""
def dmp_zero(u): """ Return a multivariate zero.
Examples ========
>>> from sympy.polys.densebasic import dmp_zero
>>> dmp_zero(4) [[[[[]]]]]
"""
def dmp_one_p(f, u, K): """ Return ``True`` if ``f`` is one in ``K[X]``.
Examples ========
>>> from sympy.polys.domains import ZZ >>> from sympy.polys.densebasic import dmp_one_p
>>> dmp_one_p([[[ZZ(1)]]], 2, ZZ) True
"""
def dmp_one(u, K): """ Return a multivariate one over ``K``.
Examples ========
>>> from sympy.polys.domains import ZZ >>> from sympy.polys.densebasic import dmp_one
>>> dmp_one(2, ZZ) [[[1]]]
"""
def dmp_ground_p(f, c, u): """ Return True if ``f`` is constant in ``K[X]``.
Examples ========
>>> from sympy.polys.densebasic import dmp_ground_p
>>> dmp_ground_p([[[3]]], 3, 2) True >>> dmp_ground_p([[[4]]], None, 2) True
""" return dmp_zero_p(f, u)
else:
def dmp_ground(c, u): """ Return a multivariate constant.
Examples ========
>>> from sympy.polys.densebasic import dmp_ground
>>> dmp_ground(3, 5) [[[[[[3]]]]]] >>> dmp_ground(1, -1) 1
"""
def dmp_zeros(n, u, K): """ Return a list of multivariate zeros.
Examples ========
>>> from sympy.polys.domains import ZZ >>> from sympy.polys.densebasic import dmp_zeros
>>> dmp_zeros(3, 2, ZZ) [[[[]]], [[[]]], [[[]]]] >>> dmp_zeros(3, -1, ZZ) [0, 0, 0]
"""
return [K.zero]*n else:
def dmp_grounds(c, n, u): """ Return a list of multivariate constants.
Examples ========
>>> from sympy.polys.domains import ZZ >>> from sympy.polys.densebasic import dmp_grounds
>>> dmp_grounds(ZZ(4), 3, 2) [[[[4]]], [[[4]]], [[[4]]]] >>> dmp_grounds(ZZ(4), 3, -1) [4, 4, 4]
""" if not n: return []
if u < 0: return [c]*n else: return [ dmp_ground(c, u) for i in range(n) ]
def dmp_negative_p(f, u, K): """ Return ``True`` if ``LC(f)`` is negative.
Examples ========
>>> from sympy.polys.domains import ZZ >>> from sympy.polys.densebasic import dmp_negative_p
>>> dmp_negative_p([[ZZ(1)], [-ZZ(1)]], 1, ZZ) False >>> dmp_negative_p([[-ZZ(1)], [ZZ(1)]], 1, ZZ) True
""" return K.is_negative(dmp_ground_LC(f, u, K))
def dmp_positive_p(f, u, K): """ Return ``True`` if ``LC(f)`` is positive.
Examples ========
>>> from sympy.polys.domains import ZZ >>> from sympy.polys.densebasic import dmp_positive_p
>>> dmp_positive_p([[ZZ(1)], [-ZZ(1)]], 1, ZZ) True >>> dmp_positive_p([[-ZZ(1)], [ZZ(1)]], 1, ZZ) False
""" return K.is_positive(dmp_ground_LC(f, u, K))
def dup_from_dict(f, K): """ Create a ``K[x]`` polynomial from a ``dict``.
Examples ========
>>> from sympy.polys.domains import ZZ >>> from sympy.polys.densebasic import dup_from_dict
>>> dup_from_dict({(0,): ZZ(7), (2,): ZZ(5), (4,): ZZ(1)}, ZZ) [1, 0, 5, 0, 7] >>> dup_from_dict({}, ZZ) []
""" return []
for k in range(n, -1, -1): h.append(f.get(k, K.zero)) else:
def dup_from_raw_dict(f, K): """ Create a ``K[x]`` polynomial from a raw ``dict``.
Examples ========
>>> from sympy.polys.domains import ZZ >>> from sympy.polys.densebasic import dup_from_raw_dict
>>> dup_from_raw_dict({0: ZZ(7), 2: ZZ(5), 4: ZZ(1)}, ZZ) [1, 0, 5, 0, 7]
""" return []
def dmp_from_dict(f, u, K): """ Create a ``K[X]`` polynomial from a ``dict``.
Examples ========
>>> from sympy.polys.domains import ZZ >>> from sympy.polys.densebasic import dmp_from_dict
>>> dmp_from_dict({(0, 0): ZZ(3), (0, 1): ZZ(2), (2, 1): ZZ(1)}, 1, ZZ) [[1, 0], [], [2, 3]] >>> dmp_from_dict({}, 0, ZZ) []
"""
else:
else:
def dup_to_dict(f, K=None, zero=False): """ Convert ``K[x]`` polynomial to a ``dict``.
Examples ========
>>> from sympy.polys.densebasic import dup_to_dict
>>> dup_to_dict([1, 0, 5, 0, 7]) {(0,): 7, (2,): 5, (4,): 1} >>> dup_to_dict([]) {}
""" return {(0,): K.zero}
def dup_to_raw_dict(f, K=None, zero=False): """ Convert a ``K[x]`` polynomial to a raw ``dict``.
Examples ========
>>> from sympy.polys.densebasic import dup_to_raw_dict
>>> dup_to_raw_dict([1, 0, 5, 0, 7]) {0: 7, 2: 5, 4: 1}
""" return {0: K.zero}
def dmp_to_dict(f, u, K=None, zero=False): """ Convert a ``K[X]`` polynomial to a ``dict````.
Examples ========
>>> from sympy.polys.densebasic import dmp_to_dict
>>> dmp_to_dict([[1, 0], [], [2, 3]], 1) {(0, 0): 3, (0, 1): 2, (2, 1): 1} >>> dmp_to_dict([], 0) {}
"""
return {(0,)*(u + 1): K.zero}
def dmp_swap(f, i, j, u, K): """ Transform ``K[..x_i..x_j..]`` to ``K[..x_j..x_i..]``.
Examples ========
>>> from sympy.polys.domains import ZZ >>> from sympy.polys.densebasic import dmp_swap
>>> f = ZZ.map([[[2], [1, 0]], []])
>>> dmp_swap(f, 0, 1, 2, ZZ) [[[2], []], [[1, 0], []]] >>> dmp_swap(f, 1, 2, 2, ZZ) [[[1], [2, 0]], [[]]] >>> dmp_swap(f, 0, 2, 2, ZZ) [[[1, 0]], [[2, 0], []]]
""" if i < 0 or j < 0 or i > u or j > u: raise IndexError("0 <= i < j <= %s expected" % u) elif i == j: return f
F, H = dmp_to_dict(f, u), {}
for exp, coeff in F.items(): H[exp[:i] + (exp[j],) + exp[i + 1:j] + (exp[i],) + exp[j + 1:]] = coeff
return dmp_from_dict(H, u, K)
def dmp_permute(f, P, u, K): """ Return a polynomial in ``K[x_{P(1)},..,x_{P(n)}]``.
Examples ========
>>> from sympy.polys.domains import ZZ >>> from sympy.polys.densebasic import dmp_permute
>>> f = ZZ.map([[[2], [1, 0]], []])
>>> dmp_permute(f, [1, 0, 2], 2, ZZ) [[[2], []], [[1, 0], []]] >>> dmp_permute(f, [1, 2, 0], 2, ZZ) [[[1], []], [[2, 0], []]]
""" F, H = dmp_to_dict(f, u), {}
for exp, coeff in F.items(): new_exp = [0]*len(exp)
for e, p in zip(exp, P): new_exp[p] = e
H[tuple(new_exp)] = coeff
return dmp_from_dict(H, u, K)
def dmp_nest(f, l, K): """ Return a multivariate value nested ``l``-levels.
Examples ========
>>> from sympy.polys.domains import ZZ >>> from sympy.polys.densebasic import dmp_nest
>>> dmp_nest([[ZZ(1)]], 2, ZZ) [[[[1]]]]
""" return dmp_ground(f, l)
def dmp_raise(f, l, u, K): """ Return a multivariate polynomial raised ``l``-levels.
Examples ========
>>> from sympy.polys.domains import ZZ >>> from sympy.polys.densebasic import dmp_raise
>>> f = ZZ.map([[], [1, 2]])
>>> dmp_raise(f, 2, 1, ZZ) [[[[]]], [[[1]], [[2]]]]
""" return f
v = u - 1
return [ dmp_raise(c, l, v, K) for c in f ]
def dup_deflate(f, K): """ Map ``x**m`` to ``y`` in a polynomial in ``K[x]``.
Examples ========
>>> from sympy.polys.domains import ZZ >>> from sympy.polys.densebasic import dup_deflate
>>> f = ZZ.map([1, 0, 0, 1, 0, 0, 1])
>>> dup_deflate(f, ZZ) (3, [1, 1, 1])
""" if dup_degree(f) <= 0: return 1, f
g = 0
for i in range(len(f)): if not f[-i - 1]: continue
g = igcd(g, i)
if g == 1: return 1, f
return g, f[::g]
def dmp_deflate(f, u, K): """ Map ``x_i**m_i`` to ``y_i`` in a polynomial in ``K[X]``.
Examples ========
>>> from sympy.polys.domains import ZZ >>> from sympy.polys.densebasic import dmp_deflate
>>> f = ZZ.map([[1, 0, 0, 2], [], [3, 0, 0, 4]])
>>> dmp_deflate(f, 1, ZZ) ((2, 3), [[1, 2], [3, 4]])
""" if dmp_zero_p(f, u): return (1,)*(u + 1), f
F = dmp_to_dict(f, u) B = [0]*(u + 1)
for M in F.keys(): for i, m in enumerate(M): B[i] = igcd(B[i], m)
for i, b in enumerate(B): if not b: B[i] = 1
B = tuple(B)
if all(b == 1 for b in B): return B, f
H = {}
for A, coeff in F.items(): N = [ a // b for a, b in zip(A, B) ] H[tuple(N)] = coeff
return B, dmp_from_dict(H, u, K)
def dup_multi_deflate(polys, K): """ Map ``x**m`` to ``y`` in a set of polynomials in ``K[x]``.
Examples ========
>>> from sympy.polys.domains import ZZ >>> from sympy.polys.densebasic import dup_multi_deflate
>>> f = ZZ.map([1, 0, 2, 0, 3]) >>> g = ZZ.map([4, 0, 0])
>>> dup_multi_deflate((f, g), ZZ) (2, ([1, 2, 3], [4, 0]))
""" G = 0
for p in polys: if dup_degree(p) <= 0: return 1, polys
g = 0
for i in range(len(p)): if not p[-i - 1]: continue
g = igcd(g, i)
if g == 1: return 1, polys
G = igcd(G, g)
return G, tuple([ p[::G] for p in polys ])
def dmp_multi_deflate(polys, u, K): """ Map ``x_i**m_i`` to ``y_i`` in a set of polynomials in ``K[X]``.
Examples ========
>>> from sympy.polys.domains import ZZ >>> from sympy.polys.densebasic import dmp_multi_deflate
>>> f = ZZ.map([[1, 0, 0, 2], [], [3, 0, 0, 4]]) >>> g = ZZ.map([[1, 0, 2], [], [3, 0, 4]])
>>> dmp_multi_deflate((f, g), 1, ZZ) ((2, 1), ([[1, 0, 0, 2], [3, 0, 0, 4]], [[1, 0, 2], [3, 0, 4]]))
""" M, H = dup_multi_deflate(polys, K) return (M,), H
def dup_inflate(f, m, K): """ Map ``y`` to ``x**m`` in a polynomial in ``K[x]``.
Examples ========
>>> from sympy.polys.domains import ZZ >>> from sympy.polys.densebasic import dup_inflate
>>> f = ZZ.map([1, 1, 1])
>>> dup_inflate(f, 3, ZZ) [1, 0, 0, 1, 0, 0, 1]
""" raise IndexError("'m' must be positive, got %s" % m)
def _rec_inflate(g, M, v, i, K): """Recursive helper for :func:`dmp_inflate`.""" raise IndexError("all M[i] must be positive, got %s" % M[i])
def dmp_inflate(f, M, u, K): """ Map ``y_i`` to ``x_i**k_i`` in a polynomial in ``K[X]``.
Examples ========
>>> from sympy.polys.domains import ZZ >>> from sympy.polys.densebasic import dmp_inflate
>>> f = ZZ.map([[1, 2], [3, 4]])
>>> dmp_inflate(f, (2, 3), 1, ZZ) [[1, 0, 0, 2], [], [3, 0, 0, 4]]
""" return dup_inflate(f, M[0], K)
else:
def dmp_exclude(f, u, K): """ Exclude useless levels from ``f``.
Return the levels excluded, the new excluded ``f``, and the new ``u``.
Examples ========
>>> from sympy.polys.domains import ZZ >>> from sympy.polys.densebasic import dmp_exclude
>>> f = ZZ.map([[[1]], [[1], [2]]])
>>> dmp_exclude(f, 2, ZZ) ([2], [[1], [1, 2]], 1)
"""
else:
def dmp_include(f, J, u, K): """ Include useless levels in ``f``.
Examples ========
>>> from sympy.polys.domains import ZZ >>> from sympy.polys.densebasic import dmp_include
>>> f = ZZ.map([[1], [1, 2]])
>>> dmp_include(f, [2], 1, ZZ) [[[1]], [[1], [2]]]
"""
def dmp_inject(f, u, K, front=False): """ Convert ``f`` from ``K[X][Y]`` to ``K[X,Y]``.
Examples ========
>>> from sympy.polys.rings import ring >>> from sympy.polys.domains import ZZ >>> from sympy.polys.densebasic import dmp_inject
>>> R, x,y = ring("x,y", ZZ)
>>> dmp_inject([R(1), x + 2], 0, R.to_domain()) ([[[1]], [[1], [2]]], 2) >>> dmp_inject([R(1), x + 2], 0, R.to_domain(), front=True) ([[[1]], [[1, 2]]], 2)
"""
h[g_monom + f_monom] = c else:
def dmp_eject(f, u, K, front=False): """ Convert ``f`` from ``K[X,Y]`` to ``K[X][Y]``.
Examples ========
>>> from sympy.polys.domains import ZZ >>> from sympy.polys.densebasic import dmp_eject
>>> dmp_eject([[[1]], [[1], [2]]], 2, ZZ['x', 'y']) [1, x + 2]
"""
g_monom, f_monom = monom[:n], monom[n:] else:
h[f_monom][g_monom] = c else:
def dup_terms_gcd(f, K): """ Remove GCD of terms from ``f`` in ``K[x]``.
Examples ========
>>> from sympy.polys.domains import ZZ >>> from sympy.polys.densebasic import dup_terms_gcd
>>> f = ZZ.map([1, 0, 1, 0, 0])
>>> dup_terms_gcd(f, ZZ) (2, [1, 0, 1])
"""
else:
def dmp_terms_gcd(f, u, K): """ Remove GCD of terms from ``f`` in ``K[X]``.
Examples ========
>>> from sympy.polys.domains import ZZ >>> from sympy.polys.densebasic import dmp_terms_gcd
>>> f = ZZ.map([[1, 0], [1, 0, 0], [], []])
>>> dmp_terms_gcd(f, 1, ZZ) ((2, 1), [[1], [1, 0]])
"""
def _rec_list_terms(g, v, monom): """Recursive helper for :func:`dmp_list_terms`."""
else:
def dmp_list_terms(f, u, K, order=None): """ List all non-zero terms from ``f`` in the given order ``order``.
Examples ========
>>> from sympy.polys.domains import ZZ >>> from sympy.polys.densebasic import dmp_list_terms
>>> f = ZZ.map([[1, 1], [2, 3]])
>>> dmp_list_terms(f, 1, ZZ) [((1, 1), 1), ((1, 0), 1), ((0, 1), 2), ((0, 0), 3)] >>> dmp_list_terms(f, 1, ZZ, order='grevlex') [((1, 1), 1), ((1, 0), 1), ((0, 1), 2), ((0, 0), 3)]
"""
return [((0,)*(u + 1), K.zero)]
else:
def dup_apply_pairs(f, g, h, args, K): """ Apply ``h`` to pairs of coefficients of ``f`` and ``g``.
Examples ========
>>> from sympy.polys.domains import ZZ >>> from sympy.polys.densebasic import dup_apply_pairs
>>> h = lambda x, y, z: 2*x + y - z
>>> dup_apply_pairs([1, 2, 3], [3, 2, 1], h, (1,), ZZ) [4, 5, 6]
""" n, m = len(f), len(g)
if n != m: if n > m: g = [K.zero]*(n - m) + g else: f = [K.zero]*(m - n) + f
result = []
for a, b in zip(f, g): result.append(h(a, b, *args))
return dup_strip(result)
def dmp_apply_pairs(f, g, h, args, u, K): """ Apply ``h`` to pairs of coefficients of ``f`` and ``g``.
Examples ========
>>> from sympy.polys.domains import ZZ >>> from sympy.polys.densebasic import dmp_apply_pairs
>>> h = lambda x, y, z: 2*x + y - z
>>> dmp_apply_pairs([[1], [2, 3]], [[3], [2, 1]], h, (1,), 1, ZZ) [[4], [5, 6]]
""" if not u: return dup_apply_pairs(f, g, h, args, K)
n, m, v = len(f), len(g), u - 1
if n != m: if n > m: g = dmp_zeros(n - m, v, K) + g else: f = dmp_zeros(m - n, v, K) + f
result = []
for a, b in zip(f, g): result.append(dmp_apply_pairs(a, b, h, args, v, K))
return dmp_strip(result, u)
def dup_slice(f, m, n, K): """Take a continuous subsequence of terms of ``f`` in ``K[x]``. """ k = len(f)
if k >= m: M = k - m else: M = 0 if k >= n: N = k - n else: N = 0
f = f[N:M]
if not f: return [] else: return f + [K.zero]*m
def dmp_slice(f, m, n, u, K): """Take a continuous subsequence of terms of ``f`` in ``K[X]``. """ return dmp_slice_in(f, m, n, 0, u, K)
def dmp_slice_in(f, m, n, j, u, K): """Take a continuous subsequence of terms of ``f`` in ``x_j`` in ``K[X]``. """ if j < 0 or j > u: raise IndexError("-%s <= j < %s expected, got %s" % (u, u, j))
if not u: return dup_slice(f, m, n, K)
f, g = dmp_to_dict(f, u), {}
for monom, coeff in f.items(): k = monom[j]
if k < m or k >= n: monom = monom[:j] + (0,) + monom[j + 1:]
if monom in g: g[monom] += coeff else: g[monom] = coeff
return dmp_from_dict(g, u, K)
def dup_random(n, a, b, K): """ Return a polynomial of degree ``n`` with coefficients in ``[a, b]``.
Examples ========
>>> from sympy.polys.domains import ZZ >>> from sympy.polys.densebasic import dup_random
>>> dup_random(3, -10, 10, ZZ) #doctest: +SKIP [-2, -8, 9, -4]
""" f = [ K.convert(random.randint(a, b)) for _ in range(0, n + 1) ]
while not f[0]: f[0] = K.convert(random.randint(a, b))
return f |