Coverage for sympy/core/exprtools.py : 41%

"""Tools for manipulating of large commutative expressions. """ 

from __future__ import print_function, division 

from sympy.core.add import Add 

from sympy.core.compatibility import iterable, is_sequence, SYMPY_INTS, range 

from sympy.core.mul import Mul, _keep_coeff 

from sympy.core.power import Pow 

from sympy.core.basic import Basic, preorder_traversal 

from sympy.core.expr import Expr 

from sympy.core.sympify import sympify 

from sympy.core.numbers import Rational, Integer, Number, I 

from sympy.core.singleton import S 

from sympy.core.symbol import Dummy 

from sympy.core.coreerrors import NonCommutativeExpression 

from sympy.core.containers import Tuple, Dict 

from sympy.utilities import default_sort_key 

from sympy.utilities.iterables import (common_prefix, common_suffix, 

variations, ordered) 

from collections import defaultdict 

_eps = Dummy(positive=True) 

def _isnumber(i): 

return isinstance(i, (SYMPY_INTS, float)) or i.is_Number 

def _monotonic_sign(self): 

"""Return the value closest to 0 that ``self`` may have if all symbols 

are signed and the result is uniformly the same sign for all values of symbols. 

If a symbol is only signed but not known to be an 

integer or the result is 0 then a symbol representative of the sign of self 

will be returned. Otherwise, None is returned if a) the sign could be positive 

or negative or b) self is not in one of the following forms: 

- L(x, y, ...) + A: a function linear in all symbols x, y, ... with an 

additive constant; if A is zero then the function can be a monomial whose 

sign is monotonic over the range of the variables, e.g. (x + 1)**3 if x is 

nonnegative. 

- A/L(x, y, ...) + B: the inverse of a function linear in all symbols x, y, ... 

that does not have a sign change from positive to negative for any set 

of values for the variables. 

- M(x, y, ...) + A: a monomial M whose factors are all signed and a constant, A. 

- A/M(x, y, ...) + B: the inverse of a monomial and constants A and B. 

- P(x): a univariate polynomial 

Examples 

======== 

>>> from sympy.core.exprtools import _monotonic_sign as F 

>>> from sympy import Dummy, S 

>>> nn = Dummy(integer=True, nonnegative=True) 

>>> p = Dummy(integer=True, positive=True) 

>>> p2 = Dummy(integer=True, positive=True) 

>>> F(nn + 1) 

1 

>>> F(p - 1) 

_nneg 

>>> F(nn*p + 1) 

1 

>>> F(p2*p + 1) 

2 

>>> F(nn - 1) # could be negative, zero or positive 

""" 

if not self.is_real: 

return 

if (-self).is_Symbol: 

rv = _monotonic_sign(-self) 

return rv if rv is None else -rv 

if not self.is_Add and self.as_numer_denom()[1].is_number: 

s = self 

if s.is_prime: 

if s.is_odd: 

return S(3) 

else: 

return S(2) 

elif s.is_positive: 

if s.is_even: 

return S(2) 

elif s.is_integer: 

return S.One 

else: 

return _eps 

elif s.is_negative: 

if s.is_even: 

return S(-2) 

elif s.is_integer: 

return S.NegativeOne 

else: 

return -_eps 

if s.is_zero or s.is_nonpositive or s.is_nonnegative: 

return S.Zero 

return None 

# univariate polynomial 

free = self.free_symbols 

if len(free) == 1: 

if self.is_polynomial(): 

from sympy.polys.polytools import real_roots 

from sympy.polys.polyroots import roots 

from sympy.polys.polyerrors import PolynomialError 

x = free.pop() 

x0 = _monotonic_sign(x) 

if x0 == _eps or x0 == -_eps: 

x0 = S.Zero 

if x0 is not None: 

d = self.diff(x) 

if d.is_number: 

roots = [] 

else: 

try: 

roots = real_roots(d) 

except (PolynomialError, NotImplementedError): 

roots = [r for r in roots(d, x) if r.is_real] 

y = self.subs(x, x0) 

if x.is_nonnegative and all(r <= x0 for r in roots): 

if y.is_nonnegative and d.is_positive: 

if y: 

return y if y.is_positive else Dummy('pos', positive=True) 

else: 

return Dummy('nneg', nonnegative=True) 

if y.is_nonpositive and d.is_negative: 

if y: 

return y if y.is_negative else Dummy('neg', negative=True) 

else: 

return Dummy('npos', nonpositive=True) 

elif x.is_nonpositive and all(r >= x0 for r in roots): 

if y.is_nonnegative and d.is_negative: 

if y: 

return Dummy('pos', positive=True) 

else: 

return Dummy('nneg', nonnegative=True) 

if y.is_nonpositive and d.is_positive: 

if y: 

return Dummy('neg', negative=True) 

else: 

return Dummy('npos', nonpositive=True) 

else: 

n, d = self.as_numer_denom() 

den = None 

if n.is_number: 

den = _monotonic_sign(d) 

elif not d.is_number: 

if _monotonic_sign(n) is not None: 

den = _monotonic_sign(d) 

if den is not None and (den.is_positive or den.is_negative): 

v = n*den 

if v.is_positive: 

return Dummy('pos', positive=True) 

elif v.is_nonnegative: 

return Dummy('nneg', nonnegative=True) 

elif v.is_negative: 

return Dummy('neg', negative=True) 

elif v.is_nonpositive: 

return Dummy('npos', nonpositive=True) 

return None 

# multivariate 

c, a = self.as_coeff_Add() 

v = None 

if not a.is_polynomial(): 

# F/A or A/F where A is a number and F is a signed, rational monomial 

n, d = a.as_numer_denom() 

if not (n.is_number or d.is_number): 

return 

if ( 

a.is_Mul or a.is_Pow) and \ 

a.is_rational and \ 

all(p.exp.is_Integer for p in a.atoms(Pow) if p.is_Pow) and \ 

(a.is_positive or a.is_negative): 

v = S(1) 

for ai in Mul.make_args(a): 

if ai.is_number: 

v *= ai 

continue 

reps = {} 

for x in ai.free_symbols: 

reps[x] = _monotonic_sign(x) 

if reps[x] is None: 

return 

v *= ai.subs(reps) 

elif c: 

# signed linear expression 

if not any(p for p in a.atoms(Pow) if not p.is_number) and (a.is_nonpositive or a.is_nonnegative): 

free = list(a.free_symbols) 

p = {} 

for i in free: 

v = _monotonic_sign(i) 

if v is None: 

return 

p[i] = v or (_eps if i.is_nonnegative else -_eps) 

v = a.xreplace(p) 

if v is not None: 

rv = v + c 

if v.is_nonnegative and rv.is_positive: 

return rv.subs(_eps, 0) 

if v.is_nonpositive and rv.is_negative: 

return rv.subs(_eps, 0) 

def decompose_power(expr): 

""" 

Decompose power into symbolic base and integer exponent. 

This is strictly only valid if the exponent from which 

the integer is extracted is itself an integer or the 

base is positive. These conditions are assumed and not 

checked here. 

Examples 

======== 

>>> from sympy.core.exprtools import decompose_power 

>>> from sympy.abc import x, y 

>>> decompose_power(x) 

(x, 1) 

>>> decompose_power(x**2) 

(x, 2) 

>>> decompose_power(x**(2*y)) 

(x**y, 2) 

>>> decompose_power(x**(2*y/3)) 

(x**(y/3), 2) 

""" 

base, exp = expr.as_base_exp() 

if exp.is_Number: 

if exp.is_Rational: 

if not exp.is_Integer: 

base = Pow(base, Rational(1, exp.q)) 

exp = exp.p 

else: 

base, exp = expr, 1 

else: 

exp, tail = exp.as_coeff_Mul(rational=True) 

if exp is S.NegativeOne: 

base, exp = Pow(base, tail), -1 

elif exp is not S.One: 

tail = _keep_coeff(Rational(1, exp.q), tail) 

base, exp = Pow(base, tail), exp.p 

else: 

base, exp = expr, 1 

return base, exp 

def decompose_power_rat(expr): 

""" 

Decompose power into symbolic base and rational exponent. 

""" 

base, exp = expr.as_base_exp() 

if exp.is_Number: 

if not exp.is_Rational: 

base, exp = expr, 1 

else: 

exp, tail = exp.as_coeff_Mul(rational=True) 

if exp is S.NegativeOne: 

base, exp = Pow(base, tail), -1 

elif exp is not S.One: 

tail = _keep_coeff(Rational(1, exp.q), tail) 

base, exp = Pow(base, tail), exp.p 

else: 

base, exp = expr, 1 

return base, exp 

class Factors(object): 

"""Efficient representation of ``f_1*f_2*...*f_n``.""" 

__slots__ = ['factors', 'gens'] 

def __init__(self, factors=None): # Factors 

"""Initialize Factors from dict or expr. 

Examples 

======== 

>>> from sympy.core.exprtools import Factors 

>>> from sympy.abc import x 

>>> from sympy import I 

>>> e = 2*x**3 

>>> Factors(e) 

Factors({2: 1, x: 3}) 

>>> Factors(e.as_powers_dict()) 

Factors({2: 1, x: 3}) 

>>> f = _ 

>>> f.factors # underlying dictionary 

{2: 1, x: 3} 

>>> f.gens # base of each factor 

frozenset([2, x]) 

>>> Factors(0) 

Factors({0: 1}) 

>>> Factors(I) 

Factors({I: 1}) 

Notes 

===== 

Although a dictionary can be passed, only minimal checking is 

performed: powers of -1 and I are made canonical. 

""" 

if isinstance(factors, (SYMPY_INTS, float)): 

factors = S(factors) 

if isinstance(factors, Factors): 

factors = factors.factors.copy() 

elif factors is None or factors is S.One: 

factors = {} 

elif factors is S.Zero or factors == 0: 

factors = {S.Zero: S.One} 

elif isinstance(factors, Number): 

n = factors 

factors = {} 

if n < 0: 

factors[S.NegativeOne] = S.One 

n = -n 

if n is not S.One: 

if n.is_Float or n.is_Integer or n is S.Infinity: 

factors[n] = S.One 

elif n.is_Rational: 

# since we're processing Numbers, the denominator is 

# stored with a negative exponent; all other factors 

# are left . 

if n.p != 1: 

factors[Integer(n.p)] = S.One 

factors[Integer(n.q)] = S.NegativeOne 

else: 

raise ValueError('Expected Float|Rational|Integer, not %s' % n) 

elif isinstance(factors, Basic) and not factors.args: 

factors = {factors: S.One} 

elif isinstance(factors, Expr): 

c, nc = factors.args_cnc() 

i = c.count(I) 

for _ in range(i): 

c.remove(I) 

factors = dict(Mul._from_args(c).as_powers_dict()) 

if i: 

factors[I] = S.One*i 

if nc: 

factors[Mul(*nc, evaluate=False)] = S.One 

else: 

factors = factors.copy() # /!\ should be dict-like 

# tidy up -/+1 and I exponents if Rational 

handle = [] 

for k in factors: 

if k is I or k in (-1, 1): 

handle.append(k) 

if handle: 

i1 = S.One 

for k in handle: 

if not _isnumber(factors[k]): 

continue 

i1 *= k**factors.pop(k) 

if i1 is not S.One: 

for a in i1.args if i1.is_Mul else [i1]: # at worst, -1.0*I*(-1)**e 

if a is S.NegativeOne: 

factors[a] = S.One 

elif a is I: 

factors[I] = S.One 

elif a.is_Pow: 

if S.NegativeOne not in factors: 

factors[S.NegativeOne] = S.Zero 

factors[S.NegativeOne] += a.exp 

elif a == 1: 

factors[a] = S.One 

elif a == -1: 

factors[-a] = S.One 

factors[S.NegativeOne] = S.One 

else: 

raise ValueError('unexpected factor in i1: %s' % a) 

self.factors = factors 

try: 

self.gens = frozenset(factors.keys()) 

except AttributeError: 

raise TypeError('expecting Expr or dictionary') 

def __hash__(self): # Factors 

keys = tuple(ordered(self.factors.keys())) 

values = [self.factors[k] for k in keys] 

return hash((keys, values)) 

def __repr__(self): # Factors 

return "Factors({%s})" % ', '.join( 

['%s: %s' % (k, v) for k, v in ordered(self.factors.items())]) 

@property 

def is_zero(self): # Factors 

""" 

>>> from sympy.core.exprtools import Factors 

>>> Factors(0).is_zero 

True 

""" 

f = self.factors 

return len(f) == 1 and S.Zero in f 

@property 

def is_one(self): # Factors 

""" 

>>> from sympy.core.exprtools import Factors 

>>> Factors(1).is_one 

True 

""" 

return not self.factors 

def as_expr(self): # Factors 

"""Return the underlying expression. 

Examples 

======== 

>>> from sympy.core.exprtools import Factors 

>>> from sympy.abc import x, y 

>>> Factors((x*y**2).as_powers_dict()).as_expr() 

x*y**2 

""" 

args = [] 

for factor, exp in self.factors.items(): 

if exp != 1: 

b, e = factor.as_base_exp() 

if isinstance(exp, int): 

e = _keep_coeff(Integer(exp), e) 

elif isinstance(exp, Rational): 

e = _keep_coeff(exp, e) 

else: 

e *= exp 

args.append(b**e) 

else: 

args.append(factor) 

return Mul(*args) 

def mul(self, other): # Factors 

"""Return Factors of ``self * other``. 

Examples 

======== 

>>> from sympy.core.exprtools import Factors 

>>> from sympy.abc import x, y, z 

>>> a = Factors((x*y**2).as_powers_dict()) 

>>> b = Factors((x*y/z).as_powers_dict()) 

>>> a.mul(b) 

Factors({x: 2, y: 3, z: -1}) 

>>> a*b 

Factors({x: 2, y: 3, z: -1}) 

""" 

if not isinstance(other, Factors): 

other = Factors(other) 

if any(f.is_zero for f in (self, other)): 

return Factors(S.Zero) 

factors = dict(self.factors) 

for factor, exp in other.factors.items(): 

if factor in factors: 

exp = factors[factor] + exp 

if not exp: 

del factors[factor] 

continue 

factors[factor] = exp 

return Factors(factors) 

def normal(self, other): 

"""Return ``self`` and ``other`` with ``gcd`` removed from each. 

The only differences between this and method ``div`` is that this 

is 1) optimized for the case when there are few factors in common and 

2) this does not raise an error if ``other`` is zero. 

See Also 

======== 

div 

""" 

if not isinstance(other, Factors): 

other = Factors(other) 

if other.is_zero: 

return (Factors(), Factors(S.Zero)) 

if self.is_zero: 

return (Factors(S.Zero), Factors()) 

self_factors = dict(self.factors) 

other_factors = dict(other.factors) 

for factor, self_exp in self.factors.items(): 

try: 

other_exp = other.factors[factor] 

except KeyError: 

continue 

exp = self_exp - other_exp 

if not exp: 

del self_factors[factor] 

del other_factors[factor] 

elif _isnumber(exp): 

if exp > 0: 

self_factors[factor] = exp 

del other_factors[factor] 

else: 

del self_factors[factor] 

other_factors[factor] = -exp 

else: 

r = self_exp.extract_additively(other_exp) 

if r is not None: 

if r: 

self_factors[factor] = r 

del other_factors[factor] 

else: # should be handled already 

del self_factors[factor] 

del other_factors[factor] 

else: 

sc, sa = self_exp.as_coeff_Add() 

if sc: 

oc, oa = other_exp.as_coeff_Add() 

diff = sc - oc 

if diff > 0: 

self_factors[factor] -= oc 

other_exp = oa 

elif diff < 0: 

self_factors[factor] -= sc 

other_factors[factor] -= sc 

other_exp = oa - diff 

else: 

self_factors[factor] = sa 

other_exp = oa 

if other_exp: 

other_factors[factor] = other_exp 

else: 

del other_factors[factor] 

return Factors(self_factors), Factors(other_factors) 

def div(self, other): # Factors 

"""Return ``self`` and ``other`` with ``gcd`` removed from each. 

This is optimized for the case when there are many factors in common. 

Examples 

======== 

>>> from sympy.core.exprtools import Factors 

>>> from sympy.abc import x, y, z 

>>> from sympy import S 

>>> a = Factors((x*y**2).as_powers_dict()) 

>>> a.div(a) 

(Factors({}), Factors({})) 

>>> a.div(x*z) 

(Factors({y: 2}), Factors({z: 1})) 

The ``/`` operator only gives ``quo``: 

>>> a/x 

Factors({y: 2}) 

Factors treats its factors as though they are all in the numerator, so 

if you violate this assumption the results will be correct but will 

not strictly correspond to the numerator and denominator of the ratio: 

>>> a.div(x/z) 

(Factors({y: 2}), Factors({z: -1})) 

Factors is also naive about bases: it does not attempt any denesting 

of Rational-base terms, for example the following does not become 

2**(2*x)/2. 

>>> Factors(2**(2*x + 2)).div(S(8)) 

(Factors({2: 2*x + 2}), Factors({8: 1})) 

factor_terms can clean up such Rational-bases powers: 

>>> from sympy.core.exprtools import factor_terms 

>>> n, d = Factors(2**(2*x + 2)).div(S(8)) 

>>> n.as_expr()/d.as_expr() 

2**(2*x + 2)/8 

>>> factor_terms(_) 

2**(2*x)/2 

""" 

quo, rem = dict(self.factors), {} 

if not isinstance(other, Factors): 

other = Factors(other) 

if other.is_zero: 

raise ZeroDivisionError 

if self.is_zero: 

return (Factors(S.Zero), Factors()) 

for factor, exp in other.factors.items(): 

if factor in quo: 

d = quo[factor] - exp 

if _isnumber(d): 

if d <= 0: 

del quo[factor] 

if d >= 0: 

if d: 

quo[factor] = d 

continue 

exp = -d 

else: 

r = quo[factor].extract_additively(exp) 

if r is not None: 

if r: 

quo[factor] = r 

else: # should be handled already 

del quo[factor] 

else: 

other_exp = exp 

sc, sa = quo[factor].as_coeff_Add() 

if sc: 

oc, oa = other_exp.as_coeff_Add() 

diff = sc - oc 

if diff > 0: 

quo[factor] -= oc 

other_exp = oa 

elif diff < 0: 

quo[factor] -= sc 

other_exp = oa - diff 

else: 

quo[factor] = sa 

other_exp = oa 

if other_exp: 

rem[factor] = other_exp 

else: 

assert factor not in rem 

continue 

rem[factor] = exp 

return Factors(quo), Factors(rem) 

def quo(self, other): # Factors 

"""Return numerator Factor of ``self / other``. 

Examples 

======== 

>>> from sympy.core.exprtools import Factors 

>>> from sympy.abc import x, y, z 

>>> a = Factors((x*y**2).as_powers_dict()) 

>>> b = Factors((x*y/z).as_powers_dict()) 

>>> a.quo(b) # same as a/b 

Factors({y: 1}) 

""" 

return self.div(other)[0] 

def rem(self, other): # Factors 

"""Return denominator Factors of ``self / other``. 

Examples 

======== 

>>> from sympy.core.exprtools import Factors 

>>> from sympy.abc import x, y, z 

>>> a = Factors((x*y**2).as_powers_dict()) 

>>> b = Factors((x*y/z).as_powers_dict()) 

>>> a.rem(b) 

Factors({z: -1}) 

>>> a.rem(a) 

Factors({}) 

""" 

return self.div(other)[1] 

def pow(self, other): # Factors 

"""Return self raised to a non-negative integer power. 

Examples 

======== 

>>> from sympy.core.exprtools import Factors 

>>> from sympy.abc import x, y 

>>> a = Factors((x*y**2).as_powers_dict()) 

>>> a**2 

Factors({x: 2, y: 4}) 

""" 

if isinstance(other, Factors): 

other = other.as_expr() 

if other.is_Integer: 

other = int(other) 

if isinstance(other, SYMPY_INTS) and other >= 0: 

factors = {} 

if other: 

for factor, exp in self.factors.items(): 

factors[factor] = exp*other 

return Factors(factors) 

else: 

raise ValueError("expected non-negative integer, got %s" % other) 

def gcd(self, other): # Factors 

"""Return Factors of ``gcd(self, other)``. The keys are 

the intersection of factors with the minimum exponent for 

each factor. 

Examples 

======== 

>>> from sympy.core.exprtools import Factors 

>>> from sympy.abc import x, y, z 

>>> a = Factors((x*y**2).as_powers_dict()) 

>>> b = Factors((x*y/z).as_powers_dict()) 

>>> a.gcd(b) 

Factors({x: 1, y: 1}) 

""" 

if not isinstance(other, Factors): 

other = Factors(other) 

if other.is_zero: 

return Factors(self.factors) 

factors = {} 

for factor, exp in self.factors.items(): 

factor, exp = sympify(factor), sympify(exp) 

if factor in other.factors: 

lt = (exp - other.factors[factor]).is_negative 

if lt == True: 

factors[factor] = exp 

elif lt == False: 

factors[factor] = other.factors[factor] 

return Factors(factors) 

def lcm(self, other): # Factors 

"""Return Factors of ``lcm(self, other)`` which are 

the union of factors with the maximum exponent for 

each factor. 

Examples 

======== 

>>> from sympy.core.exprtools import Factors 

>>> from sympy.abc import x, y, z 

>>> a = Factors((x*y**2).as_powers_dict()) 

>>> b = Factors((x*y/z).as_powers_dict()) 

>>> a.lcm(b) 

Factors({x: 1, y: 2, z: -1}) 

""" 

if not isinstance(other, Factors): 

other = Factors(other) 

if any(f.is_zero for f in (self, other)): 

return Factors(S.Zero) 

factors = dict(self.factors) 

for factor, exp in other.factors.items(): 

if factor in factors: 

exp = max(exp, factors[factor]) 

factors[factor] = exp 

return Factors(factors) 

def __mul__(self, other): # Factors 

return self.mul(other) 

def __divmod__(self, other): # Factors 

return self.div(other) 

def __div__(self, other): # Factors 

return self.quo(other) 

__truediv__ = __div__ 

def __mod__(self, other): # Factors 

return self.rem(other) 

def __pow__(self, other): # Factors