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
"""Advanced tools for dense recursive polynomials in ``K[x]`` or ``K[X]``. """
from __future__ import print_function, division
from sympy.polys.densebasic import ( dup_strip, dmp_strip, dup_convert, dmp_convert, dup_degree, dmp_degree, dmp_to_dict, dmp_from_dict, dup_LC, dmp_LC, dmp_ground_LC, dup_TC, dmp_TC, dmp_zero, dmp_ground, dmp_zero_p, dup_to_raw_dict, dup_from_raw_dict, dmp_zeros )
from sympy.polys.densearith import ( dup_add_term, dmp_add_term, dup_lshift, dup_add, dmp_add, dup_sub, dmp_sub, dup_mul, dmp_mul, dup_sqr, dup_div, dup_rem, dmp_rem, dmp_expand, dup_mul_ground, dmp_mul_ground, dup_quo_ground, dmp_quo_ground, dup_exquo_ground, dmp_exquo_ground, )
from sympy.polys.polyerrors import ( MultivariatePolynomialError, DomainError )
from sympy.utilities import variations
from math import ceil as _ceil, log as _log from sympy.core.compatibility import range
def dup_integrate(f, m, K): """ Computes the indefinite integral of ``f`` in ``K[x]``.
Examples ========
>>> from sympy.polys import ring, QQ >>> R, x = ring("x", QQ)
>>> R.dup_integrate(x**2 + 2*x, 1) 1/3*x**3 + x**2 >>> R.dup_integrate(x**2 + 2*x, 2) 1/12*x**4 + 1/3*x**3
""" if m <= 0 or not f: return f
g = [K.zero]*m
for i, c in enumerate(reversed(f)): n = i + 1
for j in range(1, m): n *= i + j + 1
g.insert(0, K.exquo(c, K(n)))
return g
def dmp_integrate(f, m, u, K): """ Computes the indefinite integral of ``f`` in ``x_0`` in ``K[X]``.
Examples ========
>>> from sympy.polys import ring, QQ >>> R, x,y = ring("x,y", QQ)
>>> R.dmp_integrate(x + 2*y, 1) 1/2*x**2 + 2*x*y >>> R.dmp_integrate(x + 2*y, 2) 1/6*x**3 + x**2*y
""" if not u: return dup_integrate(f, m, K)
if m <= 0 or dmp_zero_p(f, u): return f
g, v = dmp_zeros(m, u - 1, K), u - 1
for i, c in enumerate(reversed(f)): n = i + 1
for j in range(1, m): n *= i + j + 1
g.insert(0, dmp_quo_ground(c, K(n), v, K))
return g
def _rec_integrate_in(g, m, v, i, j, K): """Recursive helper for :func:`dmp_integrate_in`.""" if i == j: return dmp_integrate(g, m, v, K)
w, i = v - 1, i + 1
return dmp_strip([ _rec_integrate_in(c, m, w, i, j, K) for c in g ], v)
def dmp_integrate_in(f, m, j, u, K): """ Computes the indefinite integral of ``f`` in ``x_j`` in ``K[X]``.
Examples ========
>>> from sympy.polys import ring, QQ >>> R, x,y = ring("x,y", QQ)
>>> R.dmp_integrate_in(x + 2*y, 1, 0) 1/2*x**2 + 2*x*y >>> R.dmp_integrate_in(x + 2*y, 1, 1) x*y + y**2
""" if j < 0 or j > u: raise IndexError("0 <= j <= u expected, got %s" % (u, j))
return _rec_integrate_in(f, m, u, 0, j, K)
def dup_diff(f, m, K): """ ``m``-th order derivative of a polynomial in ``K[x]``.
Examples ========
>>> from sympy.polys import ring, ZZ >>> R, x = ring("x", ZZ)
>>> R.dup_diff(x**3 + 2*x**2 + 3*x + 4, 1) 3*x**2 + 4*x + 3 >>> R.dup_diff(x**3 + 2*x**2 + 3*x + 4, 2) 6*x + 4
""" return f
else: for coeff in f[:-m]: k = n
for i in range(n - 1, n - m, -1): k *= i
deriv.append(K(k)*coeff) n -= 1
def dmp_diff(f, m, u, K): """ ``m``-th order derivative in ``x_0`` of a polynomial in ``K[X]``.
Examples ========
>>> from sympy.polys import ring, ZZ >>> R, x,y = ring("x,y", ZZ)
>>> f = x*y**2 + 2*x*y + 3*x + 2*y**2 + 3*y + 1
>>> R.dmp_diff(f, 1) y**2 + 2*y + 3 >>> R.dmp_diff(f, 2) 0
""" return f
return dmp_zero(u)
else: for coeff in f[:-m]: k = n
for i in range(n - 1, n - m, -1): k *= i
deriv.append(dmp_mul_ground(coeff, K(k), v, K)) n -= 1
def _rec_diff_in(g, m, v, i, j, K): """Recursive helper for :func:`dmp_diff_in`.""" if i == j: return dmp_diff(g, m, v, K)
w, i = v - 1, i + 1
return dmp_strip([ _rec_diff_in(c, m, w, i, j, K) for c in g ], v)
def dmp_diff_in(f, m, j, u, K): """ ``m``-th order derivative in ``x_j`` of a polynomial in ``K[X]``.
Examples ========
>>> from sympy.polys import ring, ZZ >>> R, x,y = ring("x,y", ZZ)
>>> f = x*y**2 + 2*x*y + 3*x + 2*y**2 + 3*y + 1
>>> R.dmp_diff_in(f, 1, 0) y**2 + 2*y + 3 >>> R.dmp_diff_in(f, 1, 1) 2*x*y + 2*x + 4*y + 3
""" if j < 0 or j > u: raise IndexError("0 <= j <= %s expected, got %s" % (u, j))
return _rec_diff_in(f, m, u, 0, j, K)
def dup_eval(f, a, K): """ Evaluate a polynomial at ``x = a`` in ``K[x]`` using Horner scheme.
Examples ========
>>> from sympy.polys import ring, ZZ >>> R, x = ring("x", ZZ)
>>> R.dup_eval(x**2 + 2*x + 3, 2) 11
"""
def dmp_eval(f, a, u, K): """ Evaluate a polynomial at ``x_0 = a`` in ``K[X]`` using the Horner scheme.
Examples ========
>>> from sympy.polys import ring, ZZ >>> R, x,y = ring("x,y", ZZ)
>>> R.dmp_eval(2*x*y + 3*x + y + 2, 2) 5*y + 8
"""
def _rec_eval_in(g, a, v, i, j, K): """Recursive helper for :func:`dmp_eval_in`."""
def dmp_eval_in(f, a, j, u, K): """ Evaluate a polynomial at ``x_j = a`` in ``K[X]`` using the Horner scheme.
Examples ========
>>> from sympy.polys import ring, ZZ >>> R, x,y = ring("x,y", ZZ)
>>> f = 2*x*y + 3*x + y + 2
>>> R.dmp_eval_in(f, 2, 0) 5*y + 8 >>> R.dmp_eval_in(f, 2, 1) 7*x + 4
""" raise IndexError("0 <= j <= %s expected, got %s" % (u, j))
def _rec_eval_tail(g, i, A, u, K): """Recursive helper for :func:`dmp_eval_tail`.""" else:
else:
def dmp_eval_tail(f, A, u, K): """ Evaluate a polynomial at ``x_j = a_j, ...`` in ``K[X]``.
Examples ========
>>> from sympy.polys import ring, ZZ >>> R, x,y = ring("x,y", ZZ)
>>> f = 2*x*y + 3*x + y + 2
>>> R.dmp_eval_tail(f, [2]) 7*x + 4 >>> R.dmp_eval_tail(f, [2, 2]) 18
"""
return dmp_zero(u - len(A))
else:
def _rec_diff_eval(g, m, a, v, i, j, K): """Recursive helper for :func:`dmp_diff_eval`."""
def dmp_diff_eval_in(f, m, a, j, u, K): """ Differentiate and evaluate a polynomial in ``x_j`` at ``a`` in ``K[X]``.
Examples ========
>>> from sympy.polys import ring, ZZ >>> R, x,y = ring("x,y", ZZ)
>>> f = x*y**2 + 2*x*y + 3*x + 2*y**2 + 3*y + 1
>>> R.dmp_diff_eval_in(f, 1, 2, 0) y**2 + 2*y + 3 >>> R.dmp_diff_eval_in(f, 1, 2, 1) 6*x + 11
""" raise IndexError("-%s <= j < %s expected, got %s" % (u, u, j)) return dmp_eval(dmp_diff(f, m, u, K), a, u, K)
def dup_trunc(f, p, K): """ Reduce a ``K[x]`` polynomial modulo a constant ``p`` in ``K``.
Examples ========
>>> from sympy.polys import ring, ZZ >>> R, x = ring("x", ZZ)
>>> R.dup_trunc(2*x**3 + 3*x**2 + 5*x + 7, ZZ(3)) -x**3 - x + 1
"""
else: else: g = [ c % p for c in f ]
def dmp_trunc(f, p, u, K): """ Reduce a ``K[X]`` polynomial modulo a polynomial ``p`` in ``K[Y]``.
Examples ========
>>> from sympy.polys import ring, ZZ >>> R, x,y = ring("x,y", ZZ)
>>> f = 3*x**2*y + 8*x**2 + 5*x*y + 6*x + 2*y + 3 >>> g = (y - 1).drop(x)
>>> R.dmp_trunc(f, g) 11*x**2 + 11*x + 5
""" return dmp_strip([ dmp_rem(c, p, u - 1, K) for c in f ], u)
def dmp_ground_trunc(f, p, u, K): """ Reduce a ``K[X]`` polynomial modulo a constant ``p`` in ``K``.
Examples ========
>>> from sympy.polys import ring, ZZ >>> R, x,y = ring("x,y", ZZ)
>>> f = 3*x**2*y + 8*x**2 + 5*x*y + 6*x + 2*y + 3
>>> R.dmp_ground_trunc(f, ZZ(3)) -x**2 - x*y - y
"""
def dup_monic(f, K): """ Divide all coefficients by ``LC(f)`` in ``K[x]``.
Examples ========
>>> from sympy.polys import ring, ZZ, QQ
>>> R, x = ring("x", ZZ) >>> R.dup_monic(3*x**2 + 6*x + 9) x**2 + 2*x + 3
>>> R, x = ring("x", QQ) >>> R.dup_monic(3*x**2 + 4*x + 2) x**2 + 4/3*x + 2/3
""" return f
else:
def dmp_ground_monic(f, u, K): """ Divide all coefficients by ``LC(f)`` in ``K[X]``.
Examples ========
>>> from sympy.polys import ring, ZZ, QQ
>>> R, x,y = ring("x,y", ZZ) >>> f = 3*x**2*y + 6*x**2 + 3*x*y + 9*y + 3
>>> R.dmp_ground_monic(f) x**2*y + 2*x**2 + x*y + 3*y + 1
>>> R, x,y = ring("x,y", QQ) >>> f = 3*x**2*y + 8*x**2 + 5*x*y + 6*x + 2*y + 3
>>> R.dmp_ground_monic(f) x**2*y + 8/3*x**2 + 5/3*x*y + 2*x + 2/3*y + 1
"""
if dmp_zero_p(f, u): return f
lc = dmp_ground_LC(f, u, K)
if K.is_one(lc): return f else: return dmp_exquo_ground(f, lc, u, K)
def dup_content(f, K): """ Compute the GCD of coefficients of ``f`` in ``K[x]``.
Examples ========
>>> from sympy.polys import ring, ZZ, QQ
>>> R, x = ring("x", ZZ) >>> f = 6*x**2 + 8*x + 12
>>> R.dup_content(f) 2
>>> R, x = ring("x", QQ) >>> f = 6*x**2 + 8*x + 12
>>> R.dup_content(f) 2
"""
else:
def dmp_ground_content(f, u, K): """ Compute the GCD of coefficients of ``f`` in ``K[X]``.
Examples ========
>>> from sympy.polys import ring, ZZ, QQ
>>> R, x,y = ring("x,y", ZZ) >>> f = 2*x*y + 6*x + 4*y + 12
>>> R.dmp_ground_content(f) 2
>>> R, x,y = ring("x,y", QQ) >>> f = 2*x*y + 6*x + 4*y + 12
>>> R.dmp_ground_content(f) 2
"""
for c in f: cont = K.gcd(cont, dmp_ground_content(c, v, K)) else:
def dup_primitive(f, K): """ Compute content and the primitive form of ``f`` in ``K[x]``.
Examples ========
>>> from sympy.polys import ring, ZZ, QQ
>>> R, x = ring("x", ZZ) >>> f = 6*x**2 + 8*x + 12
>>> R.dup_primitive(f) (2, 3*x**2 + 4*x + 6)
>>> R, x = ring("x", QQ) >>> f = 6*x**2 + 8*x + 12
>>> R.dup_primitive(f) (2, 3*x**2 + 4*x + 6)
"""
else:
def dmp_ground_primitive(f, u, K): """ Compute content and the primitive form of ``f`` in ``K[X]``.
Examples ========
>>> from sympy.polys import ring, ZZ, QQ
>>> R, x,y = ring("x,y", ZZ) >>> f = 2*x*y + 6*x + 4*y + 12
>>> R.dmp_ground_primitive(f) (2, x*y + 3*x + 2*y + 6)
>>> R, x,y = ring("x,y", QQ) >>> f = 2*x*y + 6*x + 4*y + 12
>>> R.dmp_ground_primitive(f) (2, x*y + 3*x + 2*y + 6)
"""
return K.zero, f
else:
def dup_extract(f, g, K): """ Extract common content from a pair of polynomials in ``K[x]``.
Examples ========
>>> from sympy.polys import ring, ZZ >>> R, x = ring("x", ZZ)
>>> R.dup_extract(6*x**2 + 12*x + 18, 4*x**2 + 8*x + 12) (2, 3*x**2 + 6*x + 9, 2*x**2 + 4*x + 6)
"""
def dmp_ground_extract(f, g, u, K): """ Extract common content from a pair of polynomials in ``K[X]``.
Examples ========
>>> from sympy.polys import ring, ZZ >>> R, x,y = ring("x,y", ZZ)
>>> R.dmp_ground_extract(6*x*y + 12*x + 18, 4*x*y + 8*x + 12) (2, 3*x*y + 6*x + 9, 2*x*y + 4*x + 6)
"""
def dup_real_imag(f, K): """ Return bivariate polynomials ``f1`` and ``f2``, such that ``f = f1 + f2*I``.
Examples ========
>>> from sympy.polys import ring, ZZ >>> R, x,y = ring("x,y", ZZ)
>>> R.dup_real_imag(x**3 + x**2 + x + 1) (x**3 + x**2 - 3*x*y**2 + x - y**2 + 1, 3*x**2*y + 2*x*y - y**3 + y)
""" raise DomainError("computing real and imaginary parts is not supported over %s" % K)
return f1, f2
else:
def dup_mirror(f, K): """ Evaluate efficiently the composition ``f(-x)`` in ``K[x]``.
Examples ========
>>> from sympy.polys import ring, ZZ >>> R, x = ring("x", ZZ)
>>> R.dup_mirror(x**3 + 2*x**2 - 4*x + 2) -x**3 + 2*x**2 + 4*x + 2
"""
def dup_scale(f, a, K): """ Evaluate efficiently composition ``f(a*x)`` in ``K[x]``.
Examples ========
>>> from sympy.polys import ring, ZZ >>> R, x = ring("x", ZZ)
>>> R.dup_scale(x**2 - 2*x + 1, ZZ(2)) 4*x**2 - 4*x + 1
"""
def dup_shift(f, a, K): """ Evaluate efficiently Taylor shift ``f(x + a)`` in ``K[x]``.
Examples ========
>>> from sympy.polys import ring, ZZ >>> R, x = ring("x", ZZ)
>>> R.dup_shift(x**2 - 2*x + 1, ZZ(2)) x**2 + 2*x + 1
"""
def dup_transform(f, p, q, K): """ Evaluate functional transformation ``q**n * f(p/q)`` in ``K[x]``.
Examples ========
>>> from sympy.polys import ring, ZZ >>> R, x = ring("x", ZZ)
>>> R.dup_transform(x**2 - 2*x + 1, x**2 + 1, x - 1) x**4 - 2*x**3 + 5*x**2 - 4*x + 4
""" return []
def dup_compose(f, g, K): """ Evaluate functional composition ``f(g)`` in ``K[x]``.
Examples ========
>>> from sympy.polys import ring, ZZ >>> R, x = ring("x", ZZ)
>>> R.dup_compose(x**2 + x, x - 1) x**2 - x
""" if len(g) <= 1: return dup_strip([dup_eval(f, dup_LC(g, K), K)])
if not f: return []
h = [f[0]]
for c in f[1:]: h = dup_mul(h, g, K) h = dup_add_term(h, c, 0, K)
return h
def dmp_compose(f, g, u, K): """ Evaluate functional composition ``f(g)`` in ``K[X]``.
Examples ========
>>> from sympy.polys import ring, ZZ >>> R, x,y = ring("x,y", ZZ)
>>> R.dmp_compose(x*y + 2*x + y, y) y**2 + 3*y
""" if not u: return dup_compose(f, g, K)
if dmp_zero_p(f, u): return f
h = [f[0]]
for c in f[1:]: h = dmp_mul(h, g, u, K) h = dmp_add_term(h, c, 0, u, K)
return h
def _dup_right_decompose(f, s, K): """Helper function for :func:`_dup_decompose`."""
if not s - j in g: continue
fc, gc = f[n + j - i], g[s - j] coeff += (i - r*j)*fc*gc
def _dup_left_decompose(f, h, K): """Helper function for :func:`_dup_decompose`."""
else:
def _dup_decompose(f, K): """Helper function for :func:`dup_decompose`."""
def dup_decompose(f, K): """ Computes functional decomposition of ``f`` in ``K[x]``.
Given a univariate polynomial ``f`` with coefficients in a field of characteristic zero, returns list ``[f_1, f_2, ..., f_n]``, where::
f = f_1 o f_2 o ... f_n = f_1(f_2(... f_n))
and ``f_2, ..., f_n`` are monic and homogeneous polynomials of at least second degree.
Unlike factorization, complete functional decompositions of polynomials are not unique, consider examples:
1. ``f o g = f(x + b) o (g - b)`` 2. ``x**n o x**m = x**m o x**n`` 3. ``T_n o T_m = T_m o T_n``
where ``T_n`` and ``T_m`` are Chebyshev polynomials.
Examples ========
>>> from sympy.polys import ring, ZZ >>> R, x = ring("x", ZZ)
>>> R.dup_decompose(x**4 - 2*x**3 + x**2) [x**2, x**2 - x]
References ==========
1. [Kozen89]_
"""
else:
def dmp_lift(f, u, K): """ Convert algebraic coefficients to integers in ``K[X]``.
Examples ========
>>> from sympy.polys import ring, QQ >>> from sympy import I
>>> K = QQ.algebraic_field(I) >>> R, x = ring("x", K)
>>> f = x**2 + K([QQ(1), QQ(0)])*x + K([QQ(2), QQ(0)])
>>> R.dmp_lift(f) x**8 + 2*x**6 + 9*x**4 - 8*x**2 + 16
""" if not K.is_Algebraic: raise DomainError( 'computation can be done only in an algebraic domain')
F, monoms, polys = dmp_to_dict(f, u), [], []
for monom, coeff in F.items(): if not coeff.is_ground: monoms.append(monom)
perms = variations([-1, 1], len(monoms), repetition=True)
for perm in perms: G = dict(F)
for sign, monom in zip(perm, monoms): if sign == -1: G[monom] = -G[monom]
polys.append(dmp_from_dict(G, u, K))
return dmp_convert(dmp_expand(polys, u, K), u, K, K.dom)
def dup_sign_variations(f, K): """ Compute the number of sign variations of ``f`` in ``K[x]``.
Examples ========
>>> from sympy.polys import ring, ZZ >>> R, x = ring("x", ZZ)
>>> R.dup_sign_variations(x**4 - x**2 - x + 1) 2
"""
def dup_clear_denoms(f, K0, K1=None, convert=False): """ Clear denominators, i.e. transform ``K_0`` to ``K_1``.
Examples ========
>>> from sympy.polys import ring, QQ >>> R, x = ring("x", QQ)
>>> f = QQ(1,2)*x + QQ(1,3)
>>> R.dup_clear_denoms(f, convert=False) (6, 3*x + 2) >>> R.dup_clear_denoms(f, convert=True) (6, 3*x + 2)
""" K1 = K0.get_ring() else:
else:
def _rec_clear_denoms(g, v, K0, K1): """Recursive helper for :func:`dmp_clear_denoms`.""" common = K1.one
if not v: for c in g: common = K1.lcm(common, K0.denom(c)) else: w = v - 1
for c in g: common = K1.lcm(common, _rec_clear_denoms(c, w, K0, K1))
return common
def dmp_clear_denoms(f, u, K0, K1=None, convert=False): """ Clear denominators, i.e. transform ``K_0`` to ``K_1``.
Examples ========
>>> from sympy.polys import ring, QQ >>> R, x,y = ring("x,y", QQ)
>>> f = QQ(1,2)*x + QQ(1,3)*y + 1
>>> R.dmp_clear_denoms(f, convert=False) (6, 3*x + 2*y + 6) >>> R.dmp_clear_denoms(f, convert=True) (6, 3*x + 2*y + 6)
"""
if K1 is None: if K0.has_assoc_Ring: K1 = K0.get_ring() else: K1 = K0
common = _rec_clear_denoms(f, u, K0, K1)
if not K1.is_one(common): f = dmp_mul_ground(f, common, u, K0)
if not convert: return common, f else: return common, dmp_convert(f, u, K0, K1)
def dup_revert(f, n, K): """ Compute ``f**(-1)`` mod ``x**n`` using Newton iteration.
This function computes first ``2**n`` terms of a polynomial that is a result of inversion of a polynomial modulo ``x**n``. This is useful to efficiently compute series expansion of ``1/f``.
Examples ========
>>> from sympy.polys import ring, QQ >>> R, x = ring("x", QQ)
>>> f = -QQ(1,720)*x**6 + QQ(1,24)*x**4 - QQ(1,2)*x**2 + 1
>>> R.dup_revert(f, 8) 61/720*x**6 + 5/24*x**4 + 1/2*x**2 + 1
""" g = [K.revert(dup_TC(f, K))] h = [K.one, K.zero, K.zero]
N = int(_ceil(_log(n, 2)))
for i in range(1, N + 1): a = dup_mul_ground(g, K(2), K) b = dup_mul(f, dup_sqr(g, K), K) g = dup_rem(dup_sub(a, b, K), h, K) h = dup_lshift(h, dup_degree(h), K)
return g
def dmp_revert(f, g, u, K): """ Compute ``f**(-1)`` mod ``x**n`` using Newton iteration.
Examples ========
>>> from sympy.polys import ring, QQ >>> R, x,y = ring("x,y", QQ)
""" if not u: return dup_revert(f, g, K) else: raise MultivariatePolynomialError(f, g) |