"""Arithmetics for dense recursive polynomials in ``K[x]`` or ``K[X]``. """
from sympy.polys.densebasic import (
dup_LC, dmp_LC,
dup_degree, dmp_degree,
dup_normal,
dup_strip, dmp_strip,
dmp_zero_p, dmp_zero,
dmp_one_p, dmp_one,
dmp_ground, dmp_zeros)
from sympy.polys.polyerrors import (
ExactQuotientFailed)
from sympy.utilities import cythonized
@cythonized("i,n,m")
def dup_add_term(f, c, i, K):
"""
Add ``c*x**i`` to ``f`` in ``K[x]``.
Examples
========
>>> from sympy.polys.domains import ZZ
>>> from sympy.polys.densearith import dup_add_term
>>> f = ZZ.map([1, 0, -1])
>>> dup_add_term(f, ZZ(2), 4, ZZ)
[2, 0, 1, 0, -1]
"""
if not c:
return f
n = len(f)
m = n - i - 1
if i == n - 1:
return dup_strip([f[0] + c] + f[1:])
else:
if i >= n:
return [c] + [K.zero]*(i - n) + f
else:
return f[:m] + [f[m] + c] + f[m + 1:]
@cythonized("i,u,v,n,m")
[docs]def dmp_add_term(f, c, i, u, K):
"""
Add ``c(x_2..x_u)*x_0**i`` to ``f`` in ``K[X]``.
Examples
========
>>> from sympy.polys.domains import ZZ
>>> from sympy.polys.densearith import dmp_add_term
>>> f = ZZ.map([[1, 0], [1]])
>>> c = ZZ.map([2])
>>> dmp_add_term(f, c, 2, 1, ZZ)
[[2], [1, 0], [1]]
"""
if not u:
return dup_add_term(f, c, i, K)
v = u - 1
if dmp_zero_p(c, v):
return f
n = len(f)
m = n - i - 1
if i == n - 1:
return dmp_strip([dmp_add(f[0], c, v, K)] + f[1:], u)
else:
if i >= n:
return [c] + dmp_zeros(i - n, v, K) + f
else:
return f[:m] + [dmp_add(f[m], c, v, K)] + f[m + 1:]
@cythonized("i,n,m")
def dup_sub_term(f, c, i, K):
"""
Subtract ``c*x**i`` from ``f`` in ``K[x]``.
Examples
========
>>> from sympy.polys.domains import ZZ
>>> from sympy.polys.densearith import dup_sub_term
>>> f = ZZ.map([2, 0, 1, 0, -1])
>>> dup_sub_term(f, ZZ(2), 4, ZZ)
[1, 0, -1]
"""
if not c:
return f
n = len(f)
m = n - i - 1
if i == n - 1:
return dup_strip([f[0] - c] + f[1:])
else:
if i >= n:
return [-c] + [K.zero]*(i - n) + f
else:
return f[:m] + [f[m] - c] + f[m + 1:]
@cythonized("i,u,v,n,m")
[docs]def dmp_sub_term(f, c, i, u, K):
"""
Subtract ``c(x_2..x_u)*x_0**i`` from ``f`` in ``K[X]``.
Examples
========
>>> from sympy.polys.domains import ZZ
>>> from sympy.polys.densearith import dmp_sub_term
>>> f = ZZ.map([[2], [1, 0], [1]])
>>> c = ZZ.map([2])
>>> dmp_sub_term(f, c, 2, 1, ZZ)
[[1, 0], [1]]
"""
if not u:
return dup_add_term(f, -c, i, K)
v = u - 1
if dmp_zero_p(c, v):
return f
n = len(f)
m = n - i - 1
if i == n - 1:
return dmp_strip([dmp_sub(f[0], c, v, K)] + f[1:], u)
else:
if i >= n:
return [dmp_neg(c, v, K)] + dmp_zeros(i - n, v, K) + f
else:
return f[:m] + [dmp_sub(f[m], c, v, K)] + f[m + 1:]
@cythonized("i")
def dup_mul_term(f, c, i, K):
"""
Multiply ``f`` by ``c*x**i`` in ``K[x]``.
Examples
========
>>> from sympy.polys.domains import ZZ
>>> from sympy.polys.densearith import dup_mul_term
>>> f = ZZ.map([1, 0, -1])
>>> dup_mul_term(f, ZZ(3), 2, ZZ)
[3, 0, -3, 0, 0]
"""
if not c or not f:
return []
else:
return [ cf * c for cf in f ] + [K.zero]*i
@cythonized("i,u,v")
[docs]def dmp_mul_term(f, c, i, u, K):
"""
Multiply ``f`` by ``c(x_2..x_u)*x_0**i`` in ``K[X]``.
Examples
========
>>> from sympy.polys.domains import ZZ
>>> from sympy.polys.densearith import dmp_mul_term
>>> f = ZZ.map([[1, 0], [1], []])
>>> c = ZZ.map([3, 0])
>>> dmp_mul_term(f, c, 2, 1, ZZ)
[[3, 0, 0], [3, 0], [], [], []]
"""
if not u:
return dup_mul_term(f, c, i, K)
v = u - 1
if dmp_zero_p(f, u):
return f
if dmp_zero_p(c, v):
return dmp_zero(u)
else:
return [ dmp_mul(cf, c, v, K) for cf in f ] + dmp_zeros(i, v, K)
def dup_add_ground(f, c, K):
"""
Add an element of the ground domain to ``f``.
Examples
========
>>> from sympy.polys.domains import ZZ
>>> from sympy.polys.densearith import dup_add_ground
>>> f = ZZ.map([1, 2, 3, 4])
>>> dup_add_ground(f, ZZ(4), ZZ)
[1, 2, 3, 8]
"""
return dup_add_term(f, c, 0, K)
[docs]def dmp_add_ground(f, c, u, K):
"""
Add an element of the ground domain to ``f``.
Examples
========
>>> from sympy.polys.domains import ZZ
>>> from sympy.polys.densearith import dmp_add_ground
>>> f = ZZ.map([[1], [2], [3], [4]])
>>> dmp_add_ground(f, ZZ(4), 1, ZZ)
[[1], [2], [3], [8]]
"""
return dmp_add_term(f, dmp_ground(c, u - 1), 0, u, K)
def dup_sub_ground(f, c, K):
"""
Subtract an element of the ground domain from ``f``.
Examples
========
>>> from sympy.polys.domains import ZZ
>>> from sympy.polys.densearith import dup_sub_ground
>>> f = ZZ.map([1, 2, 3, 4])
>>> dup_sub_ground(f, ZZ(4), ZZ)
[1, 2, 3, 0]
"""
return dup_sub_term(f, c, 0, K)
[docs]def dmp_sub_ground(f, c, u, K):
"""
Subtract an element of the ground domain from ``f``.
Examples
========
>>> from sympy.polys.domains import ZZ
>>> from sympy.polys.densearith import dmp_sub_ground
>>> f = ZZ.map([[1], [2], [3], [4]])
>>> dmp_sub_ground(f, ZZ(4), 1, ZZ)
[[1], [2], [3], []]
"""
return dmp_sub_term(f, dmp_ground(c, u - 1), 0, u, K)
def dup_mul_ground(f, c, K):
"""
Multiply ``f`` by a constant value in ``K[x]``.
Examples
========
>>> from sympy.polys.domains import ZZ
>>> from sympy.polys.densearith import dup_mul_ground
>>> f = ZZ.map([1, 2, -1])
>>> dup_mul_ground(f, ZZ(3), ZZ)
[3, 6, -3]
"""
if not c or not f:
return []
else:
return [ cf * c for cf in f ]
@cythonized("u,v")
[docs]def dmp_mul_ground(f, c, u, K):
"""
Multiply ``f`` by a constant value in ``K[X]``.
Examples
========
>>> from sympy.polys.domains import ZZ
>>> from sympy.polys.densearith import dmp_mul_ground
>>> f = ZZ.map([[2], [2, 0]])
>>> dmp_mul_ground(f, ZZ(3), 1, ZZ)
[[6], [6, 0]]
"""
if not u:
return dup_mul_ground(f, c, K)
v = u - 1
return [ dmp_mul_ground(cf, c, v, K) for cf in f ]
def dup_quo_ground(f, c, K):
"""
Quotient by a constant in ``K[x]``.
Examples
========
>>> from sympy.polys.domains import ZZ, QQ
>>> from sympy.polys.densearith import dup_quo_ground
>>> f = ZZ.map([3, 0, 2])
>>> g = QQ.map([3, 0, 2])
>>> dup_quo_ground(f, ZZ(2), ZZ)
[1, 0, 1]
>>> dup_quo_ground(g, QQ(2), QQ)
[3/2, 0/1, 1/1]
"""
if not c:
raise ZeroDivisionError('polynomial division')
if not f:
return f
if K.has_Field or not K.is_Exact:
return [ K.quo(cf, c) for cf in f ]
else:
return [ cf // c for cf in f ]
@cythonized("u,v")
[docs]def dmp_quo_ground(f, c, u, K):
"""
Quotient by a constant in ``K[X]``.
Examples
========
>>> from sympy.polys.domains import ZZ, QQ
>>> from sympy.polys.densearith import dmp_quo_ground
>>> f = ZZ.map([[2, 0], [3], []])
>>> g = QQ.map([[2, 0], [3], []])
>>> dmp_quo_ground(f, ZZ(2), 1, ZZ)
[[1, 0], [1], []]
>>> dmp_quo_ground(g, QQ(2), 1, QQ)
[[1/1, 0/1], [3/2], []]
"""
if not u:
return dup_quo_ground(f, c, K)
v = u - 1
return [ dmp_quo_ground(cf, c, v, K) for cf in f ]
def dup_exquo_ground(f, c, K):
"""
Exact quotient by a constant in ``K[x]``.
Examples
========
>>> from sympy.polys.domains import ZZ, QQ
>>> from sympy.polys.densearith import dup_exquo_ground
>>> f = QQ.map([1, 0, 2])
>>> dup_exquo_ground(f, QQ(2), QQ)
[1/2, 0/1, 1/1]
"""
if not c:
raise ZeroDivisionError('polynomial division')
if not f:
return f
return [ K.exquo(cf, c) for cf in f ]
@cythonized("u,v")
[docs]def dmp_exquo_ground(f, c, u, K):
"""
Exact quotient by a constant in ``K[X]``.
Examples
========
>>> from sympy.polys.domains import ZZ, QQ
>>> from sympy.polys.densearith import dmp_exquo_ground
>>> f = QQ.map([[1, 0], [2], []])
>>> dmp_exquo_ground(f, QQ(2), 1, QQ)
[[1/2, 0/1], [1/1], []]
"""
if not u:
return dup_exquo_ground(f, c, K)
v = u - 1
return [ dmp_exquo_ground(cf, c, v, K) for cf in f ]
@cythonized("n")
[docs]def dup_lshift(f, n, K):
"""
Efficiently multiply ``f`` by ``x**n`` in ``K[x]``.
Examples
========
>>> from sympy.polys.domains import ZZ
>>> from sympy.polys.densearith import dup_lshift
>>> f = ZZ.map([1, 0, 1])
>>> dup_lshift(f, 2, ZZ)
[1, 0, 1, 0, 0]
"""
if not f:
return f
else:
return f + [K.zero]*n
@cythonized("n")
[docs]def dup_rshift(f, n, K):
"""
Efficiently divide ``f`` by ``x**n`` in ``K[x]``.
Examples
========
>>> from sympy.polys.domains import ZZ
>>> from sympy.polys.densearith import dup_rshift
>>> f = ZZ.map([1, 0, 1, 0, 0])
>>> g = ZZ.map([1, 0, 1, 0, 2])
>>> dup_rshift(f, 2, ZZ)
[1, 0, 1]
>>> dup_rshift(g, 2, ZZ)
[1, 0, 1]
"""
return f[:-n]
def dup_abs(f, K):
"""
Make all coefficients positive in ``K[x]``.
Examples
========
>>> from sympy.polys.domains import ZZ
>>> from sympy.polys.densearith import dup_abs
>>> f = ZZ.map([1, 0, -1])
>>> dup_abs(f, ZZ)
[1, 0, 1]
"""
return [ K.abs(coeff) for coeff in f ]
@cythonized("u,v")
[docs]def dmp_abs(f, u, K):
"""
Make all coefficients positive in ``K[X]``.
Examples
========
>>> from sympy.polys.domains import ZZ
>>> from sympy.polys.densearith import dmp_abs
>>> f = ZZ.map([[1, 0], [-1], []])
>>> dmp_abs(f, 1, ZZ)
[[1, 0], [1], []]
"""
if not u:
return dup_abs(f, K)
v = u - 1
return [ dmp_abs(cf, v, K) for cf in f ]
def dup_neg(f, K):
"""
Negate a polynomial in ``K[x]``.
Examples
========
>>> from sympy.polys.domains import ZZ
>>> from sympy.polys.densearith import dup_neg
>>> f = ZZ.map([1, 0, -1])
>>> dup_neg(f, ZZ)
[-1, 0, 1]
"""
return [ -coeff for coeff in f ]
@cythonized("u,v")
[docs]def dmp_neg(f, u, K):
"""
Negate a polynomial in ``K[X]``.
Examples
========
>>> from sympy.polys.domains import ZZ
>>> from sympy.polys.densearith import dmp_neg
>>> f = ZZ.map([[1, 0], [-1], []])
>>> dmp_neg(f, 1, ZZ)
[[-1, 0], [1], []]
"""
if not u:
return dup_neg(f, K)
v = u - 1
return [ dmp_neg(cf, v, K) for cf in f ]
@cythonized("df,dg,k")
def dup_add(f, g, K):
"""
Add dense polynomials in ``K[x]``.
Examples
========
>>> from sympy.polys.domains import ZZ
>>> from sympy.polys.densearith import dup_add
>>> f = ZZ.map([1, 0, -1])
>>> g = ZZ.map([1, -2])
>>> dup_add(f, g, ZZ)
[1, 1, -3]
"""
if not f:
return g
if not g:
return f
df = dup_degree(f)
dg = dup_degree(g)
if df == dg:
return dup_strip([ a + b for a, b in zip(f, g) ])
else:
k = abs(df - dg)
if df > dg:
h, f = f[:k], f[k:]
else:
h, g = g[:k], g[k:]
return h + [ a + b for a, b in zip(f, g) ]
@cythonized("u,v,df,dg,k")
[docs]def dmp_add(f, g, u, K):
"""
Add dense polynomials in ``K[X]``.
Examples
========
>>> from sympy.polys.domains import ZZ
>>> from sympy.polys.densearith import dmp_add
>>> f = ZZ.map([[1], [], [1, 0]])
>>> g = ZZ.map([[1, 0], [1], []])
>>> dmp_add(f, g, 1, ZZ)
[[1, 1], [1], [1, 0]]
"""
if not u:
return dup_add(f, g, K)
df = dmp_degree(f, u)
if df < 0:
return g
dg = dmp_degree(g, u)
if dg < 0:
return f
v = u - 1
if df == dg:
return dmp_strip([ dmp_add(a, b, v, K) for a, b in zip(f, g) ], u)
else:
k = abs(df - dg)
if df > dg:
h, f = f[:k], f[k:]
else:
h, g = g[:k], g[k:]
return h + [ dmp_add(a, b, v, K) for a, b in zip(f, g) ]
@cythonized("df,dg,k")
def dup_sub(f, g, K):
"""
Subtract dense polynomials in ``K[x]``.
Examples
========
>>> from sympy.polys.domains import ZZ
>>> from sympy.polys.densearith import dup_sub
>>> f = ZZ.map([1, 0, -1])
>>> g = ZZ.map([1, -2])
>>> dup_sub(f, g, ZZ)
[1, -1, 1]
"""
if not f:
return dup_neg(g, K)
if not g:
return f
df = dup_degree(f)
dg = dup_degree(g)
if df == dg:
return dup_strip([ a - b for a, b in zip(f, g) ])
else:
k = abs(df - dg)
if df > dg:
h, f = f[:k], f[k:]
else:
h, g = dup_neg(g[:k], K), g[k:]
return h + [ a - b for a, b in zip(f, g) ]
@cythonized("u,v,df,dg,k")
[docs]def dmp_sub(f, g, u, K):
"""
Subtract dense polynomials in ``K[X]``.
Examples
========
>>> from sympy.polys.domains import ZZ
>>> from sympy.polys.densearith import dmp_sub
>>> f = ZZ.map([[1], [], [1, 0]])
>>> g = ZZ.map([[1, 0], [1], []])
>>> dmp_sub(f, g, 1, ZZ)
[[-1, 1], [-1], [1, 0]]
"""
if not u:
return dup_sub(f, g, K)
df = dmp_degree(f, u)
if df < 0:
return dmp_neg(g, u, K)
dg = dmp_degree(g, u)
if dg < 0:
return f
v = u - 1
if df == dg:
return dmp_strip([ dmp_sub(a, b, v, K) for a, b in zip(f, g) ], u)
else:
k = abs(df - dg)
if df > dg:
h, f = f[:k], f[k:]
else:
h, g = dmp_neg(g[:k], u, K), g[k:]
return h + [ dmp_sub(a, b, v, K) for a, b in zip(f, g) ]
def dup_add_mul(f, g, h, K):
"""
Returns ``f + g*h`` where ``f, g, h`` are in ``K[x]``.
Examples
========
>>> from sympy.polys.domains import ZZ
>>> from sympy.polys.densearith import dup_add_mul
>>> f = ZZ.map([1, 0, -1])
>>> g = ZZ.map([1, -2])
>>> h = ZZ.map([1, 2])
>>> dup_add_mul(f, g, h, ZZ)
[2, 0, -5]
"""
return dup_add(f, dup_mul(g, h, K), K)
@cythonized("u")
[docs]def dmp_add_mul(f, g, h, u, K):
"""
Returns ``f + g*h`` where ``f, g, h`` are in ``K[X]``.
Examples
========
>>> from sympy.polys.domains import ZZ
>>> from sympy.polys.densearith import dmp_add_mul
>>> f = ZZ.map([[1], [], [1, 0]])
>>> g = ZZ.map([[1], []])
>>> h = ZZ.map([[1], [2]])
>>> dmp_add_mul(f, g, h, 1, ZZ)
[[2], [2], [1, 0]]
"""
return dmp_add(f, dmp_mul(g, h, u, K), u, K)
def dup_sub_mul(f, g, h, K):
"""
Returns ``f - g*h`` where ``f, g, h`` are in ``K[x]``.
Examples
========
>>> from sympy.polys.domains import ZZ
>>> from sympy.polys.densearith import dup_sub_mul
>>> f = ZZ.map([1, 0, -1])
>>> g = ZZ.map([1, -2])
>>> h = ZZ.map([1, 2])
>>> dup_sub_mul(f, g, h, ZZ)
[3]
"""
return dup_sub(f, dup_mul(g, h, K), K)
@cythonized("u")
[docs]def dmp_sub_mul(f, g, h, u, K):
"""
Returns ``f - g*h`` where ``f, g, h`` are in ``K[X]``.
Examples
========
>>> from sympy.polys.domains import ZZ
>>> from sympy.polys.densearith import dmp_sub_mul
>>> f = ZZ.map([[1], [], [1, 0]])
>>> g = ZZ.map([[1], []])
>>> h = ZZ.map([[1], [2]])
>>> dmp_sub_mul(f, g, h, 1, ZZ)
[[-2], [1, 0]]
"""
return dmp_sub(f, dmp_mul(g, h, u, K), u, K)
@cythonized("df,dg,i,j")
def dup_mul(f, g, K):
"""
Multiply dense polynomials in ``K[x]``.
Examples
========
>>> from sympy.polys.domains import ZZ
>>> from sympy.polys.densearith import dup_mul
>>> f = ZZ.map([1, -2])
>>> g = ZZ.map([1, 2])
>>> dup_mul(f, g, ZZ)
[1, 0, -4]
"""
if f == g:
return dup_sqr(f, K)
if not (f and g):
return []
df = dup_degree(f)
dg = dup_degree(g)
h = []
for i in xrange(0, df + dg + 1):
coeff = K.zero
for j in xrange(max(0, i - dg), min(df, i) + 1):
coeff += f[j]*g[i - j]
h.append(coeff)
return dup_strip(h)
@cythonized("u,v,df,dg,i,j")
[docs]def dmp_mul(f, g, u, K):
"""
Multiply dense polynomials in ``K[X]``.
Examples
========
>>> from sympy.polys.domains import ZZ
>>> from sympy.polys.densearith import dmp_mul
>>> f = ZZ.map([[1, 0], [1]])
>>> g = ZZ.map([[1], []])
>>> dmp_mul(f, g, 1, ZZ)
[[1, 0], [1], []]
"""
if not u:
return dup_mul(f, g, K)
if f == g:
return dmp_sqr(f, u, K)
df = dmp_degree(f, u)
if df < 0:
return f
dg = dmp_degree(g, u)
if dg < 0:
return g
h, v = [], u - 1
for i in xrange(0, df + dg + 1):
coeff = dmp_zero(v)
for j in xrange(max(0, i - dg), min(df, i) + 1):
coeff = dmp_add(coeff, dmp_mul(f[j], g[i - j], v, K), v, K)
h.append(coeff)
return dmp_strip(h, u)
@cythonized("df,jmin,jmax,n,i,j")
def dup_sqr(f, K):
"""
Square dense polynomials in ``K[x]``.
Examples
========
>>> from sympy.polys.domains import ZZ
>>> from sympy.polys.densearith import dup_sqr
>>> f = ZZ.map([1, 0, 1])
>>> dup_sqr(f, ZZ)
[1, 0, 2, 0, 1]
"""
df, h = dup_degree(f), []
for i in xrange(0, 2*df + 1):
c = K.zero
jmin = max(0, i - df)
jmax = min(i, df)
n = jmax - jmin + 1
jmax = jmin + n // 2 - 1
for j in xrange(jmin, jmax + 1):
c += f[j]*f[i - j]
c += c
if n & 1:
elem = f[jmax + 1]
c += elem**2
h.append(c)
return dup_strip(h)
@cythonized("u,v,df,jmin,jmax,n,i,j")
[docs]def dmp_sqr(f, u, K):
"""
Square dense polynomials in ``K[X]``.
Examples
========
>>> from sympy.polys.domains import ZZ
>>> from sympy.polys.densearith import dmp_sqr
>>> f = ZZ.map([[1], [1, 0], [1, 0, 0]])
>>> dmp_sqr(f, 1, ZZ)
[[1], [2, 0], [3, 0, 0], [2, 0, 0, 0], [1, 0, 0, 0, 0]]
"""
if not u:
return dup_sqr(f, K)
df = dmp_degree(f, u)
if df < 0:
return f
h, v = [], u - 1
for i in xrange(0, 2*df + 1):
c = dmp_zero(v)
jmin = max(0, i - df)
jmax = min(i, df)
n = jmax - jmin + 1
jmax = jmin + n // 2 - 1
for j in xrange(jmin, jmax + 1):
c = dmp_add(c, dmp_mul(f[j], f[i - j], v, K), v, K)
c = dmp_mul_ground(c, K(2), v, K)
if n & 1:
elem = dmp_sqr(f[jmax + 1], v, K)
c = dmp_add(c, elem, v, K)
h.append(c)
return dmp_strip(h, u)
@cythonized("n,m")
def dup_pow(f, n, K):
"""
Raise ``f`` to the ``n``-th power in ``K[x]``.
Examples
========
>>> from sympy.polys.domains import ZZ
>>> from sympy.polys.densearith import dup_pow
>>> dup_pow([ZZ(1), -ZZ(2)], 3, ZZ)
[1, -6, 12, -8]
"""
if not n:
return [K.one]
if n < 0:
raise ValueError("can't raise polynomial to a negative power")
if n == 1 or not f or f == [K.one]:
return f
g = [K.one]
while True:
n, m = n//2, n
if m % 2:
g = dup_mul(g, f, K)
if not n:
break
f = dup_sqr(f, K)
return g
@cythonized("u,n,m")
[docs]def dmp_pow(f, n, u, K):
"""
Raise ``f`` to the ``n``-th power in ``K[X]``.
Examples
========
>>> from sympy.polys.domains import ZZ
>>> from sympy.polys.densearith import dmp_pow
>>> f = ZZ.map([[1, 0], [1]])
>>> dmp_pow(f, 3, 1, ZZ)
[[1, 0, 0, 0], [3, 0, 0], [3, 0], [1]]
"""
if not u:
return dup_pow(f, n, K)
if not n:
return dmp_one(u, K)
if n < 0:
raise ValueError("can't raise polynomial to a negative power")
if n == 1 or dmp_zero_p(f, u) or dmp_one_p(f, u, K):
return f
g = dmp_one(u, K)
while True:
n, m = n//2, n
if m & 1:
g = dmp_mul(g, f, u, K)
if not n:
break
f = dmp_sqr(f, u, K)
return g
@cythonized("df,dg,dr,N,j")
def dup_pdiv(f, g, K):
"""
Polynomial pseudo-division in ``K[x]``.
Examples
========
>>> from sympy.polys.domains import ZZ
>>> from sympy.polys.densearith import dup_pdiv
>>> f = ZZ.map([1, 0, 1])
>>> g = ZZ.map([2, -4])
>>> dup_pdiv(f, g, ZZ)
([2, 4], [20])
"""
df = dup_degree(f)
dg = dup_degree(g)
q, r = [], f
if not g:
raise ZeroDivisionError("polynomial division")
elif df < dg:
return q, r
N = df - dg + 1
lc_g = dup_LC(g, K)
while True:
dr = dup_degree(r)
if dr < dg:
break
lc_r = dup_LC(r, K)
j, N = dr - dg, N - 1
Q = dup_mul_ground(q, lc_g, K)
q = dup_add_term(Q, lc_r, j, K)
R = dup_mul_ground(r, lc_g, K)
G = dup_mul_term(g, lc_r, j, K)
r = dup_sub(R, G, K)
c = lc_g**N
q = dup_mul_ground(q, c, K)
r = dup_mul_ground(r, c, K)
return q, r
@cythonized("df,dg,dr,N,j")
def dup_prem(f, g, K):
"""
Polynomial pseudo-remainder in ``K[x]``.
Examples
========
>>> from sympy.polys.domains import ZZ
>>> from sympy.polys.densearith import dup_prem
>>> f = ZZ.map([1, 0, 1])
>>> g = ZZ.map([2, -4])
>>> dup_prem(f, g, ZZ)
[20]
"""
df = dup_degree(f)
dg = dup_degree(g)
r = f
if not g:
raise ZeroDivisionError("polynomial division")
elif df < dg:
return r
N = df - dg + 1
lc_g = dup_LC(g, K)
while True:
dr = dup_degree(r)
if dr < dg:
break
lc_r = dup_LC(r, K)
j, N = dr - dg, N - 1
R = dup_mul_ground(r, lc_g, K)
G = dup_mul_term(g, lc_r, j, K)
r = dup_sub(R, G, K)
return dup_mul_ground(r, lc_g**N, K)
def dup_pquo(f, g, K):
"""
Polynomial exact pseudo-quotient in ``K[X]``.
Examples
========
>>> from sympy.polys.domains import ZZ
>>> from sympy.polys.densearith import dup_pquo
>>> f = ZZ.map([1, 0, -1])
>>> g = ZZ.map([2, -2])
>>> dup_pquo(f, g, ZZ)
[2, 2]
>>> f = ZZ.map([1, 0, 1])
>>> g = ZZ.map([2, -4])
>>> dup_pquo(f, g, ZZ)
[2, 4]
"""
return dup_pdiv(f, g, K)[0]
def dup_pexquo(f, g, K):
"""
Polynomial pseudo-quotient in ``K[x]``.
Examples
========
>>> from sympy.polys.domains import ZZ
>>> from sympy.polys.densearith import dup_pexquo
>>> f = ZZ.map([1, 0, -1])
>>> g = ZZ.map([2, -2])
>>> dup_pexquo(f, g, ZZ)
[2, 2]
>>> f = ZZ.map([1, 0, 1])
>>> g = ZZ.map([2, -4])
>>> dup_pexquo(f, g, ZZ)
Traceback (most recent call last):
...
ExactQuotientFailed: [2, -4] does not divide [1, 0, 1]
"""
q, r = dup_pdiv(f, g, K)
if not r:
return q
else:
raise ExactQuotientFailed(f, g)
@cythonized("u,df,dg,dr,N,j")
[docs]def dmp_pdiv(f, g, u, K):
"""
Polynomial pseudo-division in ``K[X]``.
Examples
========
>>> from sympy.polys.domains import ZZ
>>> from sympy.polys.densearith import dmp_pdiv
>>> f = ZZ.map([[1], [1, 0], []])
>>> g = ZZ.map([[2], [2]])
>>> dmp_pdiv(f, g, 1, ZZ)
([[2], [2, -2]], [[-4, 4]])
"""
if not u:
return dup_pdiv(f, g, K)
df = dmp_degree(f, u)
dg = dmp_degree(g, u)
if dg < 0:
raise ZeroDivisionError("polynomial division")
q, r = dmp_zero(u), f
if df < dg:
return q, r
N = df - dg + 1
lc_g = dmp_LC(g, K)
while True:
dr = dmp_degree(r, u)
if dr < dg:
break
lc_r = dmp_LC(r, K)
j, N = dr - dg, N - 1
Q = dmp_mul_term(q, lc_g, 0, u, K)
q = dmp_add_term(Q, lc_r, j, u, K)
R = dmp_mul_term(r, lc_g, 0, u, K)
G = dmp_mul_term(g, lc_r, j, u, K)
r = dmp_sub(R, G, u, K)
c = dmp_pow(lc_g, N, u - 1, K)
q = dmp_mul_term(q, c, 0, u, K)
r = dmp_mul_term(r, c, 0, u, K)
return q, r
@cythonized("u,df,dg,dr,N,j")
[docs]def dmp_prem(f, g, u, K):
"""
Polynomial pseudo-remainder in ``K[X]``.
Examples
========
>>> from sympy.polys.domains import ZZ
>>> from sympy.polys.densearith import dmp_prem
>>> f = ZZ.map([[1], [1, 0], []])
>>> g = ZZ.map([[2], [2]])
>>> dmp_prem(f, g, 1, ZZ)
[[-4, 4]]
"""
if not u:
return dup_prem(f, g, K)
df = dmp_degree(f, u)
dg = dmp_degree(g, u)
if dg < 0:
raise ZeroDivisionError("polynomial division")
r = f
if df < dg:
return r
N = df - dg + 1
lc_g = dmp_LC(g, K)
while True:
dr = dmp_degree(r, u)
if dr < dg:
break
lc_r = dmp_LC(r, K)
j, N = dr - dg, N - 1
R = dmp_mul_term(r, lc_g, 0, u, K)
G = dmp_mul_term(g, lc_r, j, u, K)
r = dmp_sub(R, G, u, K)
c = dmp_pow(lc_g, N, u - 1, K)
return dmp_mul_term(r, c, 0, u, K)
[docs]def dmp_pquo(f, g, u, K):
"""
Polynomial exact pseudo-quotient in ``K[X]``.
Examples
========
>>> from sympy.polys.domains import ZZ
>>> from sympy.polys.densearith import dmp_pquo
>>> f = ZZ.map([[1], [1, 0], []])
>>> g = ZZ.map([[2], [2, 0]])
>>> h = ZZ.map([[2], [2]])
>>> dmp_pquo(f, g, 1, ZZ)
[[2], []]
>>> dmp_pquo(f, h, 1, ZZ)
[[2], [2, -2]]
"""
return dmp_pdiv(f, g, u, K)[0]
[docs]def dmp_pexquo(f, g, u, K):
"""
Polynomial pseudo-quotient in ``K[X]``.
Examples
========
>>> from sympy.polys.domains import ZZ
>>> from sympy.polys.densearith import dmp_pexquo
>>> f = ZZ.map([[1], [1, 0], []])
>>> g = ZZ.map([[2], [2, 0]])
>>> h = ZZ.map([[2], [2]])
>>> dmp_pexquo(f, g, 1, ZZ)
[[2], []]
>>> dmp_pexquo(f, h, 1, ZZ)
Traceback (most recent call last):
...
ExactQuotientFailed: [[2], [2]] does not divide [[1], [1, 0], []]
"""
q, r = dmp_pdiv(f, g, u, K)
if dmp_zero_p(r, u):
return q
else:
raise ExactQuotientFailed(f, g)
@cythonized("df,dg,dr,j")
def dup_rr_div(f, g, K):
"""
Univariate division with remainder over a ring.
Examples
========
>>> from sympy.polys.domains import ZZ
>>> from sympy.polys.densearith import dup_rr_div
>>> f = ZZ.map([1, 0, 1])
>>> g = ZZ.map([2, -4])
>>> dup_rr_div(f, g, ZZ)
([], [1, 0, 1])
"""
df = dup_degree(f)
dg = dup_degree(g)
q, r = [], f
if not g:
raise ZeroDivisionError("polynomial division")
elif df < dg:
return q, r
lc_g = dup_LC(g, K)
while True:
dr = dup_degree(r)
if dr < dg:
break
lc_r = dup_LC(r, K)
if lc_r % lc_g:
break
c = K.exquo(lc_r, lc_g)
j = dr - dg
q = dup_add_term(q, c, j, K)
h = dup_mul_term(g, c, j, K)
r = dup_sub(r, h, K)
return q, r
@cythonized("u,df,dg,dr,j")
[docs]def dmp_rr_div(f, g, u, K):
"""
Multivariate division with remainder over a ring.
Examples
========
>>> from sympy.polys.domains import ZZ
>>> from sympy.polys.densearith import dmp_rr_div
>>> f = ZZ.map([[1], [1, 0], []])
>>> g = ZZ.map([[2], [2]])
>>> dmp_rr_div(f, g, 1, ZZ)
([[]], [[1], [1, 0], []])
"""
if not u:
return dup_rr_div(f, g, K)
df = dmp_degree(f, u)
dg = dmp_degree(g, u)
if dg < 0:
raise ZeroDivisionError("polynomial division")
q, r = dmp_zero(u), f
if df < dg:
return q, r
lc_g, v = dmp_LC(g, K), u - 1
while True:
dr = dmp_degree(r, u)
if dr < dg:
break
lc_r = dmp_LC(r, K)
c, R = dmp_rr_div(lc_r, lc_g, v, K)
if not dmp_zero_p(R, v):
break
j = dr - dg
q = dmp_add_term(q, c, j, u, K)
h = dmp_mul_term(g, c, j, u, K)
r = dmp_sub(r, h, u, K)
return q, r
@cythonized("df,dg,dr,j")
def dup_ff_div(f, g, K):
"""
Polynomial division with remainder over a field.
Examples
========
>>> from sympy.polys.domains import QQ
>>> from sympy.polys.densearith import dup_ff_div
>>> f = QQ.map([1, 0, 1])
>>> g = QQ.map([2, -4])
>>> dup_ff_div(f, g, QQ)
([1/2, 1/1], [5/1])
"""
df = dup_degree(f)
dg = dup_degree(g)
q, r = [], f
if not g:
raise ZeroDivisionError("polynomial division")
elif df < dg:
return q, r
lc_g = dup_LC(g, K)
while True:
dr = dup_degree(r)
if dr < dg:
break
lc_r = dup_LC(r, K)
c = K.exquo(lc_r, lc_g)
j = dr - dg
q = dup_add_term(q, c, j, K)
h = dup_mul_term(g, c, j, K)
r = dup_sub(r, h, K)
if not K.is_Exact:
r = dup_normal(r, K)
return q, r
@cythonized("u,df,dg,dr,j")
[docs]def dmp_ff_div(f, g, u, K):
"""
Polynomial division with remainder over a field.
Examples
========
>>> from sympy.polys.domains import QQ
>>> from sympy.polys.densearith import dmp_ff_div
>>> f = QQ.map([[1], [1, 0], []])
>>> g = QQ.map([[2], [2]])
>>> dmp_ff_div(f, g, 1, QQ)
([[1/2], [1/2, -1/2]], [[-1/1, 1/1]])
"""
if not u:
return dup_ff_div(f, g, K)
df = dmp_degree(f, u)
dg = dmp_degree(g, u)
if dg < 0:
raise ZeroDivisionError("polynomial division")
q, r = dmp_zero(u), f
if df < dg:
return q, r
lc_g, v = dmp_LC(g, K), u - 1
while True:
dr = dmp_degree(r, u)
if dr < dg:
break
lc_r = dmp_LC(r, K)
c, R = dmp_ff_div(lc_r, lc_g, v, K)
if not dmp_zero_p(R, v):
break
j = dr - dg
q = dmp_add_term(q, c, j, u, K)
h = dmp_mul_term(g, c, j, u, K)
r = dmp_sub(r, h, u, K)
return q, r
def dup_div(f, g, K):
"""
Polynomial division with remainder in ``K[x]``.
Examples
========
>>> from sympy.polys.domains import ZZ, QQ
>>> from sympy.polys.densearith import dup_div
>>> f = ZZ.map([1, 0, 1])
>>> g = ZZ.map([2, -4])
>>> dup_div(f, g, ZZ)
([], [1, 0, 1])
>>> f = QQ.map([1, 0, 1])
>>> g = QQ.map([2, -4])
>>> dup_div(f, g, QQ)
([1/2, 1/1], [5/1])
"""
if K.has_Field or not K.is_Exact:
return dup_ff_div(f, g, K)
else:
return dup_rr_div(f, g, K)
def dup_rem(f, g, K):
"""
Returns polynomial remainder in ``K[x]``.
Examples
========
>>> from sympy.polys.domains import ZZ, QQ
>>> from sympy.polys.densearith import dup_rem
>>> f = ZZ.map([1, 0, 1])
>>> g = ZZ.map([2, -4])
>>> dup_rem(f, g, ZZ)
[1, 0, 1]
>>> f = QQ.map([1, 0, 1])
>>> g = QQ.map([2, -4])
>>> dup_rem(f, g, QQ)
[5/1]
"""
return dup_div(f, g, K)[1]
def dup_quo(f, g, K):
"""
Returns exact polynomial quotient in ``K[x]``.
Examples
========
>>> from sympy.polys.domains import ZZ, QQ
>>> from sympy.polys.densearith import dup_quo
>>> f = ZZ.map([1, 0, 1])
>>> g = ZZ.map([2, -4])
>>> dup_quo(f, g, ZZ)
[]
>>> f = QQ.map([1, 0, 1])
>>> g = QQ.map([2, -4])
>>> dup_quo(f, g, QQ)
[1/2, 1/1]
"""
return dup_div(f, g, K)[0]
def dup_exquo(f, g, K):
"""
Returns polynomial quotient in ``K[x]``.
Examples
========
>>> from sympy.polys.domains import ZZ
>>> from sympy.polys.densearith import dup_exquo
>>> f = ZZ.map([1, 0, -1])
>>> g = ZZ.map([1, -1])
>>> dup_exquo(f, g, ZZ)
[1, 1]
>>> f = ZZ.map([1, 0, 1])
>>> g = ZZ.map([2, -4])
>>> dup_exquo(f, g, ZZ)
Traceback (most recent call last):
...
ExactQuotientFailed: [2, -4] does not divide [1, 0, 1]
"""
q, r = dup_div(f, g, K)
if not r:
return q
else:
raise ExactQuotientFailed(f, g)
@cythonized("u")
[docs]def dmp_div(f, g, u, K):
"""
Polynomial division with remainder in ``K[X]``.
Examples
========
>>> from sympy.polys.domains import ZZ, QQ
>>> from sympy.polys.densearith import dmp_div
>>> f = ZZ.map([[1], [1, 0], []])
>>> g = ZZ.map([[2], [2]])
>>> dmp_div(f, g, 1, ZZ)
([[]], [[1], [1, 0], []])
>>> f = QQ.map([[1], [1, 0], []])
>>> g = QQ.map([[2], [2]])
>>> dmp_div(f, g, 1, QQ)
([[1/2], [1/2, -1/2]], [[-1/1, 1/1]])
"""
if K.has_Field or not K.is_Exact:
return dmp_ff_div(f, g, u, K)
else:
return dmp_rr_div(f, g, u, K)
@cythonized("u")
[docs]def dmp_rem(f, g, u, K):
"""
Returns polynomial remainder in ``K[X]``.
Examples
========
>>> from sympy.polys.domains import ZZ, QQ
>>> from sympy.polys.densearith import dmp_rem
>>> f = ZZ.map([[1], [1, 0], []])
>>> g = ZZ.map([[2], [2]])
>>> dmp_rem(f, g, 1, ZZ)
[[1], [1, 0], []]
>>> f = QQ.map([[1], [1, 0], []])
>>> g = QQ.map([[2], [2]])
>>> dmp_rem(f, g, 1, QQ)
[[-1/1, 1/1]]
"""
return dmp_div(f, g, u, K)[1]
@cythonized("u")
[docs]def dmp_quo(f, g, u, K):
"""
Returns exact polynomial quotient in ``K[X]``.
Examples
========
>>> from sympy.polys.domains import ZZ, QQ
>>> from sympy.polys.densearith import dmp_quo
>>> f = ZZ.map([[1], [1, 0], []])
>>> g = ZZ.map([[2], [2]])
>>> dmp_quo(f, g, 1, ZZ)
[[]]
>>> f = QQ.map([[1], [1, 0], []])
>>> g = QQ.map([[2], [2]])
>>> dmp_quo(f, g, 1, QQ)
[[1/2], [1/2, -1/2]]
"""
return dmp_div(f, g, u, K)[0]
@cythonized("u")
[docs]def dmp_exquo(f, g, u, K):
"""
Returns polynomial quotient in ``K[X]``.
Examples
========
>>> from sympy.polys.domains import ZZ
>>> from sympy.polys.densearith import dmp_exquo
>>> f = ZZ.map([[1], [1, 0], []])
>>> g = ZZ.map([[1], [1, 0]])
>>> h = ZZ.map([[2], [2]])
>>> dmp_exquo(f, g, 1, ZZ)
[[1], []]
>>> dmp_exquo(f, h, 1, ZZ)
Traceback (most recent call last):
...
ExactQuotientFailed: [[2], [2]] does not divide [[1], [1, 0], []]
"""
q, r = dmp_div(f, g, u, K)
if dmp_zero_p(r, u):
return q
else:
raise ExactQuotientFailed(f, g)
def dup_max_norm(f, K):
"""
Returns maximum norm of a polynomial in ``K[x]``.
Examples
========
>>> from sympy.polys.domains import ZZ
>>> from sympy.polys.densearith import dup_max_norm
>>> f = ZZ.map([-1, 2, -3])
>>> dup_max_norm(f, ZZ)
3
"""
if not f:
return K.zero
else:
return max(dup_abs(f, K))
@cythonized("u,v")
[docs]def dmp_max_norm(f, u, K):
"""
Returns maximum norm of a polynomial in ``K[X]``.
Examples
========
>>> from sympy.polys.domains import ZZ
>>> from sympy.polys.densearith import dmp_max_norm
>>> f = ZZ.map([[2, -1], [-3]])
>>> dmp_max_norm(f, 1, ZZ)
3
"""
if not u:
return dup_max_norm(f, K)
v = u - 1
return max([ dmp_max_norm(c, v, K) for c in f ])
def dup_l1_norm(f, K):
"""
Returns l1 norm of a polynomial in ``K[x]``.
Examples
========
>>> from sympy.polys.domains import ZZ
>>> from sympy.polys.densearith import dup_l1_norm
>>> f = ZZ.map([2, -3, 0, 1])
>>> dup_l1_norm(f, ZZ)
6
"""
if not f:
return K.zero
else:
return sum(dup_abs(f, K))
@cythonized("u,v")
[docs]def dmp_l1_norm(f, u, K):
"""
Returns l1 norm of a polynomial in ``K[X]``.
Examples
========
>>> from sympy.polys.domains import ZZ
>>> from sympy.polys.densearith import dmp_l1_norm
>>> f = ZZ.map([[2, -1], [-3]])
>>> dmp_l1_norm(f, 1, ZZ)
6
"""
if not u:
return dup_l1_norm(f, K)
v = u - 1
return sum([ dmp_l1_norm(c, v, K) for c in f ])
def dup_expand(polys, K):
"""
Multiply together several polynomials in ``K[x]``.
Examples
========
>>> from sympy.polys.domains import ZZ
>>> from sympy.polys.densearith import dup_expand
>>> f = ZZ.map([1, 0, -1])
>>> g = ZZ.map([1, 0])
>>> h = ZZ.map([2])
>>> dup_expand([f, g, h], ZZ)
[2, 0, -2, 0]
"""
if not polys:
return [K.one]
f = polys[0]
for g in polys[1:]:
f = dup_mul(f, g, K)
return f
@cythonized("u")
[docs]def dmp_expand(polys, u, K):
"""
Multiply together several polynomials in ``K[X]``.
Examples
========
>>> from sympy.polys.domains import ZZ
>>> from sympy.polys.densearith import dmp_expand
>>> f = ZZ.map([[1], [], [1, 0, 0]])
>>> g = ZZ.map([[1], [1]])
>>> dmp_expand([f, g], 1, ZZ)
[[1], [1], [1, 0, 0], [1, 0, 0]]
"""
if not polys:
return dmp_one(u, K)
f = polys[0]
for g in polys[1:]:
f = dmp_mul(f, g, u, K)
return f