# Source code for sympy.polys.densetools

"""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_lshift,
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 xrange

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 xrange(1, m):
n *= i + j + 1

g.insert(0, K.exquo(c, K(n)))

return g

[docs]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 xrange(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)

[docs]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

"""
if m <= 0:
return f

n = dup_degree(f)

if n < m:
return []

deriv = []

if m == 1:
for coeff in f[:-m]:
deriv.append(K(n)*coeff)
n -= 1
else:
for coeff in f[:-m]:
k = n

for i in xrange(n - 1, n - m, -1):
k *= i

deriv.append(K(k)*coeff)
n -= 1

return dup_strip(deriv)

[docs]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

"""
if not u:
return dup_diff(f, m, K)
if m <= 0:
return f

n = dmp_degree(f, u)

if n < m:
return dmp_zero(u)

deriv, v = [], u - 1

if m == 1:
for coeff in f[:-m]:
deriv.append(dmp_mul_ground(coeff, K(n), v, K))
n -= 1
else:
for coeff in f[:-m]:
k = n

for i in xrange(n - 1, n - m, -1):
k *= i

deriv.append(dmp_mul_ground(coeff, K(k), v, K))
n -= 1

return dmp_strip(deriv, u)

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)

[docs]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

"""
if not a:
return dup_TC(f, K)

result = K.zero

for c in f:
result *= a
result += c

return result

[docs]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

"""
if not u:
return dup_eval(f, a, K)

if not a:
return dmp_TC(f, K)

result, v = dmp_LC(f, K), u - 1

for coeff in f[1:]:
result = dmp_mul_ground(result, a, v, K)
result = dmp_add(result, coeff, v, K)

return result

def _rec_eval_in(g, a, v, i, j, K):
"""Recursive helper for :func:dmp_eval_in."""
if i == j:
return dmp_eval(g, a, v, K)

v, i = v - 1, i + 1

return dmp_strip([ _rec_eval_in(c, a, v, i, j, K) for c in g ], v)

[docs]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

"""
if j < 0 or j > u:
raise IndexError("0 <= j <= %s expected, got %s" % (u, j))

return _rec_eval_in(f, a, u, 0, j, K)

def _rec_eval_tail(g, i, A, u, K):
"""Recursive helper for :func:dmp_eval_tail."""
if i == u:
return dup_eval(g, A[-1], K)
else:
h = [ _rec_eval_tail(c, i + 1, A, u, K) for c in g ]

if i < u - len(A) + 1:
return h
else:
return dup_eval(h, A[-u + i - 1], K)

[docs]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

"""
if not A:
return f

if dmp_zero_p(f, u):
return dmp_zero(u - len(A))

e = _rec_eval_tail(f, 0, A, u, K)

if u == len(A) - 1:
return e
else:
return dmp_strip(e, u - len(A))

def _rec_diff_eval(g, m, a, v, i, j, K):
"""Recursive helper for :func:dmp_diff_eval."""
if i == j:
return dmp_eval(dmp_diff(g, m, v, K), a, v, K)

v, i = v - 1, i + 1

return dmp_strip([ _rec_diff_eval(c, m, a, v, i, j, K) for c in g ], v)

[docs]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

"""
if j > u:
raise IndexError("-%s <= j < %s expected, got %s" % (u, u, j))
if not j:
return dmp_eval(dmp_diff(f, m, u, K), a, u, K)

return _rec_diff_eval(f, m, a, u, 0, j, 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

"""
if K.is_ZZ:
g = []

for c in f:
c = c % p

if c > p // 2:
g.append(c - p)
else:
g.append(c)
else:
g = [ c % p for c in f ]

return dup_strip(g)

[docs]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)

[docs]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

"""
if not u:
return dup_trunc(f, p, K)

v = u - 1

return dmp_strip([ dmp_ground_trunc(c, p, v, K) for c in f ], u)

[docs]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

"""
if not f:
return f

lc = dup_LC(f, K)

if K.is_one(lc):
return f
else:
return dup_exquo_ground(f, lc, K)

[docs]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 not u:
return dup_monic(f, K)

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)

[docs]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

"""
from sympy.polys.domains import QQ

if not f:
return K.zero

cont = K.zero

if K == QQ:
for c in f:
cont = K.gcd(cont, c)
else:
for c in f:
cont = K.gcd(cont, c)

if K.is_one(cont):
break

return cont

[docs]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

"""
from sympy.polys.domains import QQ

if not u:
return dup_content(f, K)

if dmp_zero_p(f, u):
return K.zero

cont, v = K.zero, u - 1

if K == QQ:
for c in f:
cont = K.gcd(cont, dmp_ground_content(c, v, K))
else:
for c in f:
cont = K.gcd(cont, dmp_ground_content(c, v, K))

if K.is_one(cont):
break

return cont

[docs]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)

"""
if not f:
return K.zero, f

cont = dup_content(f, K)

if K.is_one(cont):
return cont, f
else:
return cont, dup_quo_ground(f, cont, K)

[docs]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)

"""
if not u:
return dup_primitive(f, K)

if dmp_zero_p(f, u):
return K.zero, f

cont = dmp_ground_content(f, u, K)

if K.is_one(cont):
return cont, f
else:
return cont, dmp_quo_ground(f, cont, u, K)

[docs]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)

"""
fc = dup_content(f, K)
gc = dup_content(g, K)

gcd = K.gcd(fc, gc)

if not K.is_one(gcd):
f = dup_quo_ground(f, gcd, K)
g = dup_quo_ground(g, gcd, K)

return gcd, f, g

[docs]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)

"""
fc = dmp_ground_content(f, u, K)
gc = dmp_ground_content(g, u, K)

gcd = K.gcd(fc, gc)

if not K.is_one(gcd):
f = dmp_quo_ground(f, gcd, u, K)
g = dmp_quo_ground(g, gcd, u, K)

return gcd, f, g

[docs]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)

"""
if not K.is_ZZ and not K.is_QQ:
raise DomainError("computing real and imaginary parts is not supported over %s" % K)

f1 = dmp_zero(1)
f2 = dmp_zero(1)

if not f:
return f1, f2

g = [[[K.one, K.zero]], [[K.one], []]]
h = dmp_ground(f[0], 2)

for c in f[1:]:
h = dmp_mul(h, g, 2, K)
h = dmp_add_term(h, dmp_ground(c, 1), 0, 2, K)

H = dup_to_raw_dict(h)

for k, h in H.items():
m = k % 4

if not m:
f1 = dmp_add(f1, h, 1, K)
elif m == 1:
f2 = dmp_add(f2, h, 1, K)
elif m == 2:
f1 = dmp_sub(f1, h, 1, K)
else:
f2 = dmp_sub(f2, h, 1, K)

return f1, f2

[docs]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

"""
f, n, a = list(f), len(f) - 1, -K.one

for i in xrange(n - 1, -1, -1):
f[i], a = a*f[i], -a

return f

[docs]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

"""
f, n, b = list(f), len(f) - 1, a

for i in xrange(n - 1, -1, -1):
f[i], b = b*f[i], b*a

return f

[docs]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

"""
f, n = list(f), len(f) - 1

for i in xrange(n, 0, -1):
for j in xrange(0, i):
f[j + 1] += a*f[j]

return f

[docs]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

"""
if not f:
return []

n = len(f) - 1
h, Q = [f[0]], [[K.one]]

for i in xrange(0, n):
Q.append(dup_mul(Q[-1], q, K))

for c, q in zip(f[1:], Q[1:]):
h = dup_mul(h, p, K)
q = dup_mul_ground(q, c, K)

return h

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

[docs]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."""
n = len(f) - 1
lc = dup_LC(f, K)

f = dup_to_raw_dict(f)
g = { s: K.one }

r = n // s

for i in xrange(1, s):
coeff = K.zero

for j in xrange(0, i):
if not n + j - i in f:
continue

if not s - j in g:
continue

fc, gc = f[n + j - i], g[s - j]
coeff += (i - r*j)*fc*gc

g[s - i] = K.quo(coeff, i*r*lc)

return dup_from_raw_dict(g, K)

def _dup_left_decompose(f, h, K):
"""Helper function for :func:_dup_decompose."""
g, i = {}, 0

while f:
q, r = dup_div(f, h, K)

if dup_degree(r) > 0:
return None
else:
g[i] = dup_LC(r, K)
f, i = q, i + 1

return dup_from_raw_dict(g, K)

def _dup_decompose(f, K):
"""Helper function for :func:dup_decompose."""
df = len(f) - 1

for s in xrange(2, df):
if df % s != 0:
continue

h = _dup_right_decompose(f, s, K)

if h is not None:
g = _dup_left_decompose(f, h, K)

if g is not None:
return g, h

return None

[docs]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]_

"""
F = []

while True:
result = _dup_decompose(f, K)

if result is not None:
f, h = result
F = [h] + F
else:
break

return [f] + F

[docs]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)

[docs]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

"""
prev, k = K.zero, 0

for coeff in f:
if K.is_negative(coeff*prev):
k += 1

if coeff:
prev = coeff

return k

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)

"""
if K1 is None:
if K0.has_assoc_Ring:
K1 = K0.get_ring()
else:
K1 = K0

common = K1.one

for c in f:
common = K1.lcm(common, K0.denom(c))

if not K1.is_one(common):
f = dup_mul_ground(f, common, K0)

if not convert:
return common, f
else:
return common, dup_convert(f, K0, K1)

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

[docs]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 not u:
return dup_clear_denoms(f, K0, K1, convert=convert)

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 xrange(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

[docs]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)