Coverage for sympy/core/mul.py : 62%

from __future__ import print_function, division 

from collections import defaultdict 

from functools import cmp_to_key 

import operator 

from .sympify import sympify 

from .basic import Basic 

from .singleton import S 

from .operations import AssocOp 

from .cache import cacheit 

from .logic import fuzzy_not, _fuzzy_group 

from .compatibility import reduce, range 

from .expr import Expr 

# internal marker to indicate: 

# "there are still non-commutative objects -- don't forget to process them" 

class NC_Marker: 

is_Order = False 

is_Mul = False 

is_Number = False 

is_Poly = False 

is_commutative = False 

# Key for sorting commutative args in canonical order 

_args_sortkey = cmp_to_key(Basic.compare) 

def _mulsort(args): 

# in-place sorting of args 

args.sort(key=_args_sortkey) 

def _unevaluated_Mul(*args): 

"""Return a well-formed unevaluated Mul: Numbers are collected and 

put in slot 0, any arguments that are Muls will be flattened, and args 

are sorted. Use this when args have changed but you still want to return 

an unevaluated Mul. 

Examples 

======== 

>>> from sympy.core.mul import _unevaluated_Mul as uMul 

>>> from sympy import S, sqrt, Mul 

>>> from sympy.abc import x 

>>> a = uMul(*[S(3.0), x, S(2)]) 

>>> a.args[0] 

6.00000000000000 

>>> a.args[1] 

x 

Two unevaluated Muls with the same arguments will 

always compare as equal during testing: 

>>> m = uMul(sqrt(2), sqrt(3)) 

>>> m == uMul(sqrt(3), sqrt(2)) 

True 

>>> u = Mul(sqrt(3), sqrt(2), evaluate=False) 

>>> m == uMul(u) 

True 

>>> m == Mul(*m.args) 

False 

""" 

args = list(args) 

newargs = [] 

ncargs = [] 

co = S.One 

while args: 

a = args.pop() 

if a.is_Mul: 

c, nc = a.args_cnc() 

args.extend(c) 

if nc: 

ncargs.append(Mul._from_args(nc)) 

elif a.is_Number: 

co *= a 

else: 

newargs.append(a) 

_mulsort(newargs) 

if co is not S.One: 

newargs.insert(0, co) 

if ncargs: 

newargs.append(Mul._from_args(ncargs)) 

return Mul._from_args(newargs) 

class Mul(Expr, AssocOp): 

__slots__ = [] 

is_Mul = True 

@classmethod 

def flatten(cls, seq): 

"""Return commutative, noncommutative and order arguments by 

combining related terms. 

Notes 

===== 

* In an expression like ``a*b*c``, python process this through sympy 

as ``Mul(Mul(a, b), c)``. This can have undesirable consequences. 

- Sometimes terms are not combined as one would like: 

{c.f. https://github.com/sympy/sympy/issues/4596} 

>>> from sympy import Mul, sqrt 

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

>>> 2*(x + 1) # this is the 2-arg Mul behavior 

2*x + 2 

>>> y*(x + 1)*2 

2*y*(x + 1) 

>>> 2*(x + 1)*y # 2-arg result will be obtained first 

y*(2*x + 2) 

>>> Mul(2, x + 1, y) # all 3 args simultaneously processed 

2*y*(x + 1) 

>>> 2*((x + 1)*y) # parentheses can control this behavior 

2*y*(x + 1) 

Powers with compound bases may not find a single base to 

combine with unless all arguments are processed at once. 

Post-processing may be necessary in such cases. 

{c.f. https://github.com/sympy/sympy/issues/5728} 

>>> a = sqrt(x*sqrt(y)) 

>>> a**3 

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

>>> Mul(a,a,a) 

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

>>> a*a*a 

x*sqrt(y)*sqrt(x*sqrt(y)) 

>>> _.subs(a.base, z).subs(z, a.base) 

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

- If more than two terms are being multiplied then all the 

previous terms will be re-processed for each new argument. 

So if each of ``a``, ``b`` and ``c`` were :class:`Mul` 

expression, then ``a*b*c`` (or building up the product 

with ``*=``) will process all the arguments of ``a`` and 

``b`` twice: once when ``a*b`` is computed and again when 

``c`` is multiplied. 

Using ``Mul(a, b, c)`` will process all arguments once. 

* The results of Mul are cached according to arguments, so flatten 

will only be called once for ``Mul(a, b, c)``. If you can 

structure a calculation so the arguments are most likely to be 

repeats then this can save time in computing the answer. For 

example, say you had a Mul, M, that you wished to divide by ``d[i]`` 

and multiply by ``n[i]`` and you suspect there are many repeats 

in ``n``. It would be better to compute ``M*n[i]/d[i]`` rather 

than ``M/d[i]*n[i]`` since every time n[i] is a repeat, the 

product, ``M*n[i]`` will be returned without flattening -- the 

cached value will be returned. If you divide by the ``d[i]`` 

first (and those are more unique than the ``n[i]``) then that will 

create a new Mul, ``M/d[i]`` the args of which will be traversed 

again when it is multiplied by ``n[i]``. 

{c.f. https://github.com/sympy/sympy/issues/5706} 

This consideration is moot if the cache is turned off. 

NB 

-- 

The validity of the above notes depends on the implementation 

details of Mul and flatten which may change at any time. Therefore, 

you should only consider them when your code is highly performance 

sensitive. 

Removal of 1 from the sequence is already handled by AssocOp.__new__. 

""" 

from sympy.calculus.util import AccumBounds 

rv = None 

if len(seq) == 2: 

a, b = seq 

if b.is_Rational: 

a, b = b, a 

assert not a is S.One 

if not a.is_zero and a.is_Rational: 

r, b = b.as_coeff_Mul() 

if b.is_Add: 

if r is not S.One: # 2-arg hack 

# leave the Mul as a Mul 

rv = [cls(a*r, b, evaluate=False)], [], None 

elif b.is_commutative: 

if a is S.One: 

rv = [b], [], None 

else: 

r, b = b.as_coeff_Add() 

bargs = [_keep_coeff(a, bi) for bi in Add.make_args(b)] 

_addsort(bargs) 

ar = a*r 

if ar: 

bargs.insert(0, ar) 

bargs = [Add._from_args(bargs)] 

rv = bargs, [], None 

if rv: 

return rv 

# apply associativity, separate commutative part of seq 

c_part = [] # out: commutative factors 

nc_part = [] # out: non-commutative factors 

nc_seq = [] 

coeff = S.One # standalone term 

# e.g. 3 * ... 

c_powers = [] # (base,exp) n 

# e.g. (x,n) for x 

num_exp = [] # (num-base, exp) y 

# e.g. (3, y) for ... * 3 * ... 

neg1e = S.Zero # exponent on -1 extracted from Number-based Pow and I 

pnum_rat = {} # (num-base, Rat-exp) 1/2 

# e.g. (3, 1/2) for ... * 3 * ... 

order_symbols = None 

# --- PART 1 --- 

# 

# "collect powers and coeff": 

# 

# o coeff 

# o c_powers 

# o num_exp 

# o neg1e 

# o pnum_rat 

# 

# NOTE: this is optimized for all-objects-are-commutative case 

for o in seq: 

# O(x) 

if o.is_Order: 

o, order_symbols = o.as_expr_variables(order_symbols) 

# Mul([...]) 

if o.is_Mul: 

if o.is_commutative: 

seq.extend(o.args) # XXX zerocopy? 

else: 

# NCMul can have commutative parts as well 

for q in o.args: 

if q.is_commutative: 

seq.append(q) 

else: 

nc_seq.append(q) 

# append non-commutative marker, so we don't forget to 

# process scheduled non-commutative objects 

seq.append(NC_Marker) 

continue 

# 3 

elif o.is_Number: 

if o is S.NaN or coeff is S.ComplexInfinity and o is S.Zero: 

# we know for sure the result will be nan 

return [S.NaN], [], None 

elif coeff.is_Number: # it could be zoo 

coeff *= o 

if coeff is S.NaN: 

# we know for sure the result will be nan 

return [S.NaN], [], None 

continue 

elif isinstance(o, AccumBounds): 

coeff = o.__mul__(coeff) 

continue 

elif o is S.ComplexInfinity: 

if not coeff: 

# 0 * zoo = NaN 

return [S.NaN], [], None 

if coeff is S.ComplexInfinity: 

# zoo * zoo = zoo 

return [S.ComplexInfinity], [], None 

coeff = S.ComplexInfinity 

continue 

elif o is S.ImaginaryUnit: 

neg1e += S.Half 

continue 

elif o.is_commutative: 

# e 

# o = b 

b, e = o.as_base_exp() 

# y 

# 3 

if o.is_Pow: 

if b.is_Number: 

# get all the factors with numeric base so they can be 

# combined below, but don't combine negatives unless 

# the exponent is an integer 

if e.is_Rational: 

if e.is_Integer: 

coeff *= Pow(b, e) # it is an unevaluated power 

continue 

elif e.is_negative: # also a sign of an unevaluated power 

seq.append(Pow(b, e)) 

continue 

elif b.is_negative: 

neg1e += e 

b = -b 

if b is not S.One: 

pnum_rat.setdefault(b, []).append(e) 

continue 

elif b.is_positive or e.is_integer: 

num_exp.append((b, e)) 

continue 

elif b is S.ImaginaryUnit and e.is_Rational: 

neg1e += e/2 

continue 

c_powers.append((b, e)) 

# NON-COMMUTATIVE 

# TODO: Make non-commutative exponents not combine automatically 

else: 

if o is not NC_Marker: 

nc_seq.append(o) 

# process nc_seq (if any) 

while nc_seq: 

o = nc_seq.pop(0) 

if not nc_part: 

nc_part.append(o) 

continue 

# b c b+c 

# try to combine last terms: a * a -> a 

o1 = nc_part.pop() 

b1, e1 = o1.as_base_exp() 

b2, e2 = o.as_base_exp() 

new_exp = e1 + e2 

# Only allow powers to combine if the new exponent is 

# not an Add. This allow things like a**2*b**3 == a**5 

# if a.is_commutative == False, but prohibits 

# a**x*a**y and x**a*x**b from combining (x,y commute). 

if b1 == b2 and (not new_exp.is_Add): 

o12 = b1 ** new_exp 

# now o12 could be a commutative object 

if o12.is_commutative: 

seq.append(o12) 

continue 

else: 

nc_seq.insert(0, o12) 

else: 

nc_part.append(o1) 

nc_part.append(o) 

# We do want a combined exponent if it would not be an Add, such as 

# y 2y 3y 

# x * x -> x 

# We determine if two exponents have the same term by using 

# as_coeff_Mul. 

# 

# Unfortunately, this isn't smart enough to consider combining into 

# exponents that might already be adds, so things like: 

# z - y y 

# x * x will be left alone. This is because checking every possible 

# combination can slow things down. 

# gather exponents of common bases... 

def _gather(c_powers): 

common_b = {} # b:e 

for b, e in c_powers: 

co = e.as_coeff_Mul() 

common_b.setdefault(b, {}).setdefault( 

co[1], []).append(co[0]) 

for b, d in common_b.items(): 

for di, li in d.items(): 

d[di] = Add(*li) 

new_c_powers = [] 

for b, e in common_b.items(): 

new_c_powers.extend([(b, c*t) for t, c in e.items()]) 

return new_c_powers 

# in c_powers 

c_powers = _gather(c_powers) 

# and in num_exp 

num_exp = _gather(num_exp) 

# --- PART 2 --- 

# 

# o process collected powers (x**0 -> 1; x**1 -> x; otherwise Pow) 

# o combine collected powers (2**x * 3**x -> 6**x) 

# with numeric base 

# ................................ 

# now we have: 

# - coeff: 

# - c_powers: (b, e) 

# - num_exp: (2, e) 

# - pnum_rat: {(1/3, [1/3, 2/3, 1/4])} 

# 0 1 

# x -> 1 x -> x 

# this should only need to run twice; if it fails because 

# it needs to be run more times, perhaps this should be 

# changed to a "while True" loop -- the only reason it 

# isn't such now is to allow a less-than-perfect result to 

# be obtained rather than raising an error or entering an 

# infinite loop 

for i in range(2): 

new_c_powers = [] 

changed = False 

for b, e in c_powers: 

if e.is_zero: 

continue 

if e is S.One: 

if b.is_Number: 

coeff *= b 

continue 

p = b 

if e is not S.One: 

p = Pow(b, e) 

# check to make sure that the base doesn't change 

# after exponentiation; to allow for unevaluated 

# Pow, we only do so if b is not already a Pow 

if p.is_Pow and not b.is_Pow: 

bi = b 

b, e = p.as_base_exp() 

if b != bi: 

changed = True 

c_part.append(p) 

new_c_powers.append((b, e)) 

# there might have been a change, but unless the base 

# matches some other base, there is nothing to do 

if changed and len(set( 

b for b, e in new_c_powers)) != len(new_c_powers): 

# start over again 

c_part = [] 

c_powers = _gather(new_c_powers) 

else: 

break 

# x x x 

# 2 * 3 -> 6 

inv_exp_dict = {} # exp:Mul(num-bases) x x 

# e.g. x:6 for ... * 2 * 3 * ... 

for b, e in num_exp: 

inv_exp_dict.setdefault(e, []).append(b) 

for e, b in inv_exp_dict.items(): 

inv_exp_dict[e] = cls(*b) 

c_part.extend([Pow(b, e) for e, b in inv_exp_dict.items() if e]) 

# b, e -> e' = sum(e), b 

# {(1/5, [1/3]), (1/2, [1/12, 1/4]} -> {(1/3, [1/5, 1/2])} 

comb_e = {} 

for b, e in pnum_rat.items(): 

comb_e.setdefault(Add(*e), []).append(b) 

del pnum_rat 

# process them, reducing exponents to values less than 1 

# and updating coeff if necessary else adding them to 

# num_rat for further processing 

num_rat = [] 

for e, b in comb_e.items(): 

b = cls(*b) 

if e.q == 1: 

coeff *= Pow(b, e) 

continue 

if e.p > e.q: 

e_i, ep = divmod(e.p, e.q) 

coeff *= Pow(b, e_i) 

e = Rational(ep, e.q) 

num_rat.append((b, e)) 

del comb_e 

# extract gcd of bases in num_rat 

# 2**(1/3)*6**(1/4) -> 2**(1/3+1/4)*3**(1/4) 

pnew = defaultdict(list) 

i = 0 # steps through num_rat which may grow 

while i < len(num_rat): 

bi, ei = num_rat[i] 

grow = [] 

for j in range(i + 1, len(num_rat)): 

bj, ej = num_rat[j] 

g = bi.gcd(bj) 

if g is not S.One: 

# 4**r1*6**r2 -> 2**(r1+r2) * 2**r1 * 3**r2 

# this might have a gcd with something else 

e = ei + ej 

if e.q == 1: 

coeff *= Pow(g, e) 

else: 

if e.p > e.q: 

e_i, ep = divmod(e.p, e.q) # change e in place 

coeff *= Pow(g, e_i) 

e = Rational(ep, e.q) 

grow.append((g, e)) 

# update the jth item 

num_rat[j] = (bj/g, ej) 

# update bi that we are checking with 

bi = bi/g 

if bi is S.One: 

break 

if bi is not S.One: 

obj = Pow(bi, ei) 

if obj.is_Number: 

coeff *= obj 

else: 

# changes like sqrt(12) -> 2*sqrt(3) 

for obj in Mul.make_args(obj): 

if obj.is_Number: 

coeff *= obj 

else: 

assert obj.is_Pow 

bi, ei = obj.args 

pnew[ei].append(bi) 

num_rat.extend(grow) 

i += 1 

# combine bases of the new powers 

for e, b in pnew.items(): 

pnew[e] = cls(*b) 

# handle -1 and I 

if neg1e: 

# treat I as (-1)**(1/2) and compute -1's total exponent 

p, q = neg1e.as_numer_denom() 

# if the integer part is odd, extract -1 

n, p = divmod(p, q) 

if n % 2: 

coeff = -coeff 

# if it's a multiple of 1/2 extract I 

if q == 2: 

c_part.append(S.ImaginaryUnit) 

elif p: 

# see if there is any positive base this power of 

# -1 can join 

neg1e = Rational(p, q) 

for e, b in pnew.items(): 

if e == neg1e and b.is_positive: 

pnew[e] = -b 

break 

else: 

# keep it separate; we've already evaluated it as 

# much as possible so evaluate=False 

c_part.append(Pow(S.NegativeOne, neg1e, evaluate=False)) 

# add all the pnew powers 

c_part.extend([Pow(b, e) for e, b in pnew.items()]) 

# oo, -oo 

if (coeff is S.Infinity) or (coeff is S.NegativeInfinity): 

def _handle_for_oo(c_part, coeff_sign): 

new_c_part = [] 

for t in c_part: 

if t.is_positive: 

continue 

if t.is_negative: 

coeff_sign *= -1 

continue 

new_c_part.append(t) 

return new_c_part, coeff_sign 

c_part, coeff_sign = _handle_for_oo(c_part, 1) 

nc_part, coeff_sign = _handle_for_oo(nc_part, coeff_sign) 

coeff *= coeff_sign 

# zoo 

if coeff is S.ComplexInfinity: 

# zoo might be 

# infinite_real + bounded_im 

# bounded_real + infinite_im 

# infinite_real + infinite_im 

# and non-zero real or imaginary will not change that status. 

c_part = [c for c in c_part if not (fuzzy_not(c.is_zero) and 

c.is_real is not None)] 

nc_part = [c for c in nc_part if not (fuzzy_not(c.is_zero) and 

c.is_real is not None)] 

# 0 

elif coeff is S.Zero: 

# we know for sure the result will be 0 except the multiplicand 

# is infinity 

if any(c.is_finite == False for c in c_part): 

return [S.NaN], [], order_symbols 

return [coeff], [], order_symbols 

# check for straggling Numbers that were produced 

_new = [] 

for i in c_part: 

if i.is_Number: 

coeff *= i 

else: 

_new.append(i) 

c_part = _new 

# order commutative part canonically 

_mulsort(c_part) 

# current code expects coeff to be always in slot-0 

if coeff is not S.One: 

c_part.insert(0, coeff) 

# we are done 

if (not nc_part and len(c_part) == 2 and c_part[0].is_Number and 

c_part[1].is_Add): 

# 2*(1+a) -> 2 + 2 * a 

coeff = c_part[0] 

c_part = [Add(*[coeff*f for f in c_part[1].args])] 

return c_part, nc_part, order_symbols 

def _eval_power(b, e): 

# don't break up NC terms: (A*B)**3 != A**3*B**3, it is A*B*A*B*A*B 

cargs, nc = b.args_cnc(split_1=False) 

if e.is_Integer: 

return Mul(*[Pow(b, e, evaluate=False) for b in cargs]) * \ 

Pow(Mul._from_args(nc), e, evaluate=False) 

p = Pow(b, e, evaluate=False) 

if e.is_Rational or e.is_Float: 

return p._eval_expand_power_base() 

return p 

@classmethod 

def class_key(cls): 

return 3, 0, cls.__name__ 

def _eval_evalf(self, prec): 

c, m = self.as_coeff_Mul() 

if c is S.NegativeOne: 

if m.is_Mul: 

rv = -AssocOp._eval_evalf(m, prec) 

else: 

mnew = m._eval_evalf(prec) 

if mnew is not None: 

m = mnew 

rv = -m 

else: 

rv = AssocOp._eval_evalf(self, prec) 

if rv.is_number: 

return rv.expand() 

return rv 

@cacheit 

def as_two_terms(self): 

"""Return head and tail of self. 

This is the most efficient way to get the head and tail of an 

expression. 

- if you want only the head, use self.args[0]; 

- if you want to process the arguments of the tail then use 

self.as_coef_mul() which gives the head and a tuple containing 

the arguments of the tail when treated as a Mul. 

- if you want the coefficient when self is treated as an Add 

then use self.as_coeff_add()[0] 

>>> from sympy.abc import x, y 

>>> (3*x*y).as_two_terms() 

(3, x*y) 

""" 

args = self.args 

if len(args) == 1: 

return S.One, self 

elif len(args) == 2: 

return args 

else: 

return args[0], self._new_rawargs(*args[1:]) 

@cacheit 

def as_coefficients_dict(self): 

"""Return a dictionary mapping terms to their coefficient. 

Since the dictionary is a defaultdict, inquiries about terms which 

were not present will return a coefficient of 0. The dictionary 

is considered to have a single term. 

Examples 

======== 

>>> from sympy.abc import a, x 

>>> (3*a*x).as_coefficients_dict() 

{a*x: 3} 

>>> _[a] 

0 

""" 

d = defaultdict(int) 

args = self.args 

if len(args) == 1 or not args[0].is_Number: 

d[self] = S.One 

else: 

d[self._new_rawargs(*args[1:])] = args[0] 

return d 

@cacheit 

def as_coeff_mul(self, *deps, **kwargs): 

rational = kwargs.pop('rational', True) 

if deps: 

l1 = [] 

l2 = [] 

for f in self.args: 

if f.has(*deps): 

l2.append(f) 

else: 

l1.append(f) 

return self._new_rawargs(*l1), tuple(l2) 

args = self.args 

if args[0].is_Number: 

if not rational or args[0].is_Rational: 

return args[0], args[1:] 

elif args[0].is_negative: 

return S.NegativeOne, (-args[0],) + args[1:] 

return S.One, args 

def as_coeff_Mul(self, rational=False): 

"""Efficiently extract the coefficient of a product. """ 

coeff, args = self.args[0], self.args[1:] 

if coeff.is_Number: 

if not rational or coeff.is_Rational: 

if len(args) == 1: 

return coeff, args[0] 

else: 

return coeff, self._new_rawargs(*args) 

elif coeff.is_negative: 

return S.NegativeOne, self._new_rawargs(*((-coeff,) + args)) 

return S.One, self 

def as_real_imag(self, deep=True, **hints): 

from sympy import Abs, expand_mul, im, re 

other = [] 

coeffr = [] 

coeffi = [] 

addterms = S.One