sympy/core/mul.py

   1
   2 from basic import Basic, S, C, sympify
   3 from operations import AssocOp
   4 from cache import cacheit
   5
   6 from logic import fuzzy_not
   7
   8 from symbol import Symbol, Wild
   9 # from function import FunctionClass, WildFunction /cyclic/
  10 # from numbers import Number, Integer, Real /cyclic/
  11 # from add   import Add /cyclic/
  12 # from power import Pow /cyclic/
  13
  14 import sympy.mpmath as mpmath
  15
  16 class Mul(AssocOp):
  17
  18     __slots__ = []
  19
  20     is_Mul = True
  21
  22     @classmethod
  23     def flatten(cls, seq):
  24         # apply associativity, separate commutative part of seq
  25         c_part = []
  26         nc_part = []
  27
  28         c_seq = []
  29         nc_seq = seq
  30
  31         coeff = S.One       # standalone term
  32                             # e.g. 3 * ...
  33
  34         c_powers = {}       # base -> exp                      z
  35                             # e.g. (x+y) -> z  for  ... * (x+y)  * ...
  36
  37         exp_dict = {}       # num-base -> exp           y
  38                             # e.g.  3 -> y  for  ... * 3  * ...
  39
  40         inv_exp_dict = {}   # exp -> Mul(num-bases)     x    x
  41                             # e.g.  x -> 6  for  ... * 2  * 3  * ...
  42
  43         order_symbols = None
  44
  45
  46         while c_seq or nc_seq:
  47
  48             # COMMUTATIVE
  49             if c_seq:
  50                 # first process commutative objects
  51                 o = c_seq.pop(0)
  52
  53                 # O(x)
  54                 if o.is_Order:
  55                     o, order_symbols = o.as_expr_symbols(order_symbols)
  56
  57                 # Mul([...])
  58                 if o.is_Mul:
  59                     # associativity
  60                     c_seq = list(o.args[:]) + c_seq
  61                     continue
  62
  63                 # 3
  64                 if o.is_Number:
  65                     coeff *= o
  66                     continue
  67
  68                 #  y
  69                 # x
  70                 if o.is_Pow:
  71                     base, exponent = o.as_base_exp()
  72
  73                     #  y
  74                     # 3
  75                     if base.is_Number:
  76
  77                         # let's collect factors with numeric base
  78                         if base in exp_dict:
  79                             exp_dict[base] += exponent
  80                         else:
  81                             exp_dict[base] = exponent
  82                         continue
  83
  84                 # exp(x)
  85                 if o.func is C.exp:
  86                     # exp(x) / exp(y) -> exp(x-y)
  87                     b = S.Exp1
  88                     e = o.args[0]
  89
  90                 # everything else
  91                 else:
  92                     b, e = o.as_base_exp()
  93
  94                 # now we have
  95                 # o = b**e
  96
  97                 #         n          n          n
  98                 # (-3 + y)   ->  (-1)  * (3 - y)
  99                 if b.is_Add and e.is_Number:
 100                     #found factor (x+y)**number; split off initial coefficient
 101                     c, t = b.as_coeff_terms()
 102                     #last time I checked, Add.as_coeff_terms returns One or NegativeOne
 103                     #but this might change
 104                     if c.is_negative and not e.is_integer:
 105                         # extracting root from negative number: ignore sign
 106                         if c is not S.NegativeOne:
 107                             # make c positive (probably never occurs)
 108                             coeff *= (-c) ** e
 109                             assert len(t)==1,`t`
 110                             b = -t[0]
 111                         #else: ignoring sign from NegativeOne: nothing to do!
 112                     elif c is not S.One:
 113                         coeff *= c ** e
 114                         assert len(t)==1,`t`
 115                         b = t[0]
 116                     #else: c is One, so pass
 117
 118                 # let's collect factors with the same base, so e.g.
 119                 #  y    z     y+z
 120                 # x  * x  -> x
 121                 if b in c_powers:
 122                     c_powers[b] += e
 123                 else:
 124                     c_powers[b] = e
 125
 126
 127             # NON-COMMUTATIVE
 128             else:
 129                 o = nc_seq.pop(0)
 130                 if isinstance(o, WildFunction):
 131                     pass
 132                 elif o.is_Order:
 133                     o, order_symbols = o.as_expr_symbols(order_symbols)
 134
 135                 # -> commutative
 136                 if o.is_commutative:
 137                     # separate commutative symbols
 138                     c_seq.append(o)
 139                     continue
 140
 141                 # Mul([...])
 142                 if o.__class__ is cls:
 143                     # associativity
 144                     nc_seq = list(o.args) + nc_seq
 145                     continue
 146                 if not nc_part:
 147                     nc_part.append(o)
 148                     continue
 149
 150                 #                             b    c       b+c
 151                 # try to combine last terms: a  * a   ->  a
 152                 o1 = nc_part.pop()
 153                 b1,e1 = o1.as_base_exp()
 154                 b2,e2 = o.as_base_exp()
 155                 if b1==b2:
 156                     nc_seq.insert(0, b1 ** (e1 + e2))
 157                 else:
 158                     nc_part.append(o1)
 159                     nc_part.append(o)
 160
 161
 162         # ................................
 163         # now we have:
 164         # - coeff:
 165         # - c_powers:   b -> e
 166         # - exp_dict:   3 -> e
 167
 168         # XXX
 169         for b, e in c_powers.items():
 170             if e is S.Zero:
 171                 continue
 172
 173             if e is S.One:
 174                 if b.is_Number:
 175                     coeff *= b
 176                 else:
 177                     c_part.append(b)
 178             elif e.is_Integer and b.is_Number:
 179                 coeff *= b ** e
 180             else:
 181                 c_part.append(Pow(b, e))
 182
 183         #  x    x     x
 184         # 2  * 3  -> 6
 185         for b,e in exp_dict.items():
 186             if e in inv_exp_dict:
 187                 inv_exp_dict[e] *= b
 188             else:
 189                 inv_exp_dict[e] = b
 190
 191         for e,b in inv_exp_dict.items():
 192             if e is S.Zero:
 193                 continue
 194
 195             if e is S.One:
 196                 if b.is_Number:
 197                     coeff *= b
 198                 else:
 199                     c_part.append(b)
 200             elif e.is_Integer and b.is_Number:
 201                 coeff *= b ** e
 202             else:
 203                 obj = b**e
 204                 if obj.is_Number:
 205                     coeff *= obj
 206                 else:
 207                     c_part.append(obj)
 208
 209
 210         # deal with
 211         # (oo|nan|zero) * ...
 212         if (coeff is S.Infinity) or (coeff is S.NegativeInfinity):
 213             new_c_part = []
 214             for t in c_part:
 215                 if t.is_positive:
 216                     continue
 217                 if t.is_negative:
 218                     coeff = -coeff
 219                     continue
 220                 new_c_part.append(t)
 221             c_part = new_c_part
 222             new_nc_part = []
 223             for t in nc_part:
 224                 if t.is_positive:
 225                     continue
 226                 if t.is_negative:
 227                     coeff = -coeff
 228                     continue
 229                 new_nc_part.append(t)
 230             nc_part = new_nc_part
 231             c_part.insert(0, coeff)
 232         elif (coeff is S.Zero) or (coeff is S.NaN):
 233             c_part, nc_part = [coeff], []
 234         elif coeff.is_Real:
 235             if coeff == Real(0):
 236                 c_part, nc_part = [coeff], []
 237             elif coeff != Real(1):
 238                 c_part.insert(0, coeff)
 239         elif coeff is not S.One:
 240             c_part.insert(0, coeff)
 241
 242         # order commutative part canonically
 243         c_part.sort(Basic.compare)
 244
 245         # we are done
 246         if len(c_part)==2 and c_part[0].is_Number and c_part[1].is_Add:
 247             # 2*(1+a) -> 2 + 2 * a
 248             coeff = c_part[0]
 249             c_part = [Add(*[coeff*f for f in c_part[1].args])]
 250
 251         return c_part, nc_part, order_symbols
 252
 253
 254     def _eval_power(b, e):
 255         if e.is_Number:
 256             if b.is_commutative:
 257                 if e.is_Integer:
 258                     # (a*b)**2 -> a**2 * b**2
 259                     return Mul(*[s**e for s in b.args])
 260
 261                 if e.is_rational:
 262                     coeff, rest = b.as_coeff_terms()
 263                     if coeff == -1:
 264                         return None
 265                     elif coeff < 0:
 266                         return (-coeff)**e * Mul(*((S.NegativeOne,) +rest))**e
 267                     else:
 268                         return coeff**e * Mul(*[s**e for s in rest])
 269
 270
 271                 coeff, rest = b.as_coeff_terms()
 272                 if coeff is not S.One:
 273                     # (2*a)**3 -> 2**3 * a**3
 274                     return coeff**e * Mul(*[s**e for s in rest])
 275             elif e.is_Integer:
 276                 coeff, rest = b.as_coeff_terms()
 277                 l = [s**e for s in rest]
 278                 if e.is_negative:
 279                     l.reverse()
 280                 return coeff**e * Mul(*l)
 281
 282         c,t = b.as_coeff_terms()
 283         if e.is_even and c.is_Number and c < 0:
 284             return (-c * Mul(*t)) ** e
 285
 286         #if e.atoms(Wild):
 287         #    return Mul(*[t**e for t in b])
 288
 289     def _eval_evalf(self, prec):
 290         return AssocOp._eval_evalf(self, prec).expand()
 291
 292     @cacheit
 293     def as_two_terms(self):
 294         if len(self.args) == 1:
 295             return S.One, self
 296         return self.args[0], Mul(*self.args[1:])
 297
 298     @cacheit
 299     def as_coeff_terms(self, x=None):
 300         if x is not None:
 301             l1 = []
 302             l2 = []
 303             for f in self.args:
 304                 if f.has(x):
 305                     l2.append(f)
 306                 else:
 307                     l1.append(f)
 308             return Mul(*l1), tuple(l2)
 309         coeff = self.args[0]
 310         if coeff.is_Number:
 311             return coeff, self.args[1:]
 312         return S.One, self.args
 313
 314     @staticmethod
 315     def _expandsums(sums):
 316         L = len(sums)
 317         if len(sums) == 1:
 318             return sums[0]
 319         terms = []
 320         left = Mul._expandsums(sums[:L//2])
 321         right = Mul._expandsums(sums[L//2:])
 322         if isinstance(right, Basic):
 323             right = right.args
 324         if isinstance(left, Basic):
 325             left = left.args
 326
 327         if len(left) == 1 and len(right) == 1:
 328             # no expansion needed, bail out now to avoid infinite recursion
 329             return [Mul(left[0], right[0])]
 330
 331         terms = []
 332         for a in left:
 333             for b in right:
 334                 terms.append(Mul(a,b).expand())
 335             added = Add(*terms)
 336             if added.is_Add:
 337                 terms = list(added.args)
 338             else:
 339                 terms = [added]
 340         return terms
 341
 342     def _eval_expand_basic(self):
 343         plain, sums, rewrite = [], [], False
 344
 345         for factor in self.args:
 346             terms = factor._eval_expand_basic()
 347
 348             if terms is not None:
 349                 factor = terms
 350
 351             if factor.is_Add:
 352                 sums.append(factor)
 353                 rewrite = True
 354             else:
 355                 if factor.is_commutative:
 356                     plain.append(factor)
 357                 else:
 358                     sums.append([factor])
 359
 360                 if terms is not None:
 361                     rewrite = True
 362
 363         if not rewrite:
 364             return None
 365         else:
 366             if sums:
 367                 terms = Mul._expandsums(sums)
 368
 369                 if isinstance(terms, Basic):
 370                     terms = terms.args
 371
 372                 plain = Mul(*plain)
 373
 374                 return Add(*(Mul(plain, term) for term in terms), **self.assumptions0)
 375             else:
 376                 return Mul(*plain, **self.assumptions0)
 377
 378     def _eval_derivative(self, s):
 379         terms = list(self.args)
 380         factors = []
 381         for i in xrange(len(terms)):
 382             t = terms[i].diff(s)
 383             if t is S.Zero:
 384                 continue
 385             factors.append(Mul(*(terms[:i]+[t]+terms[i+1:])))
 386         return Add(*factors)
 387
 388     def _matches_simple(pattern, expr, repl_dict):
 389         # handle (w*3).matches('x*5') -> {w: x*5/3}
 390         coeff, terms = pattern.as_coeff_terms()
 391         if len(terms)==1:
 392             return terms[0].matches(expr / coeff, repl_dict)
 393         return
 394
 395     def matches(pattern, expr, repl_dict={}, evaluate=False):
 396         expr = sympify(expr)
 397         if pattern.is_commutative and expr.is_commutative:
 398             return AssocOp._matches_commutative(pattern, expr, repl_dict, evaluate)
 399         # todo for commutative parts, until then use the default matches method for non-commutative products
 400         return Basic.matches(pattern, expr, repl_dict, evaluate)
 401
 402     @staticmethod
 403     def _combine_inverse(lhs, rhs):
 404         if lhs == rhs:
 405             return S.One
 406         return lhs / rhs
 407
 408     def as_powers_dict(self):
 409         return dict([ term.as_base_exp() for term in self ])
 410
 411     def as_numer_denom(self):
 412         numers, denoms = [],[]
 413         for t in self.args:
 414             n,d = t.as_numer_denom()
 415             numers.append(n)
 416             denoms.append(d)
 417         return Mul(*numers), Mul(*denoms)
 418
 419     @cacheit
 420     def count_ops(self, symbolic=True):
 421         if symbolic:
 422             return Add(*[t.count_ops(symbolic) for t in self[:]]) + Symbol('MUL') * (len(self[:])-1)
 423         return Add(*[t.count_ops(symbolic) for t in self.args[:]]) + (len(self.args)-1)
 424
 425     def _eval_is_polynomial(self, syms):
 426         for term in self.args:
 427             if not term._eval_is_polynomial(syms):
 428                 return False
 429         return True
 430
 431     _eval_is_bounded = lambda self: self._eval_template_is_attr('is_bounded')
 432     _eval_is_commutative = lambda self: self._eval_template_is_attr('is_commutative')
 433     _eval_is_integer = lambda self: self._eval_template_is_attr('is_integer')
 434     _eval_is_comparable = lambda self: self._eval_template_is_attr('is_comparable')
 435
 436
 437     # I*I -> R,  I*I*I -> -I
 438
 439     def _eval_is_real(self):
 440         im_count = 0
 441         re_not   = False
 442
 443         for t in self.args:
 444             if t.is_imaginary:
 445                 im_count += 1
 446                 continue
 447
 448             t_real = t.is_real
 449             if t_real:
 450                 continue
 451
 452             elif fuzzy_not(t_real):
 453                 re_not = True
 454
 455             else:
 456                 return None
 457
 458         if re_not:
 459             return False
 460
 461         return (im_count % 2 == 0)
 462
 463
 464     def _eval_is_imaginary(self):
 465         im_count = 0
 466
 467         for t in self.args:
 468             if t.is_imaginary:
 469                 im_count += 1
 470
 471             elif t.is_real:
 472                 continue
 473
 474             # real=F|U
 475             else:
 476                 return None
 477
 478         return (im_count % 2 == 1)
 479
 480
 481
 482     def _eval_is_irrational(self):
 483         for t in self.args:
 484             a = t.is_irrational
 485             if a: return True
 486             if a is None: return
 487         return False
 488
 489     def _eval_is_positive(self):
 490         terms = [t for t in self.args if not t.is_positive]
 491         if not terms:
 492             return True
 493         c = terms[0]
 494         if len(terms)==1:
 495             if c.is_nonpositive:
 496                 return False
 497             return
 498         r = Mul(*terms[1:])
 499         if c.is_negative and r.is_negative:
 500             return True
 501         if r.is_negative and c.is_negative:
 502             return True
 503         # check for nonpositivity, <=0
 504         if c.is_negative and r.is_nonnegative:
 505             return False
 506         if r.is_negative and c.is_nonnegative:
 507             return False
 508         if c.is_nonnegative and r.is_nonpositive:
 509             return False
 510         if r.is_nonnegative and c.is_nonpositive:
 511             return False
 512
 513
 514     def _eval_is_negative(self):
 515         terms = [t for t in self.args if not t.is_positive]
 516         if not terms:
 517             # all terms are either positive -- 2*Symbol('n', positive=T)
 518             #               or     unknown  -- 2*Symbol('x')
 519             if self.is_positive:
 520                 return False
 521             else:
 522                 return None
 523         c = terms[0]
 524         if len(terms)==1:
 525             return c.is_negative
 526         r = Mul(*terms[1:])
 527         # check for nonnegativity, >=0
 528         if c.is_negative and r.is_nonpositive:
 529             return False
 530         if r.is_negative and c.is_nonpositive:
 531             return False
 532         if c.is_nonpositive and r.is_nonpositive:
 533             return False
 534         if c.is_nonnegative and r.is_nonnegative:
 535             return False
 536
 537     def _eval_is_odd(self):
 538         is_integer = self.is_integer
 539
 540         if is_integer:
 541             r = True
 542             for t in self.args:
 543                 if t.is_even:
 544                     return False
 545                 if t.is_odd is None:
 546                     r = None
 547             return r
 548
 549         # !integer -> !odd
 550         elif is_integer == False:
 551             return False
 552
 553
 554     def _eval_is_even(self):
 555         is_integer = self.is_integer
 556
 557         if is_integer:
 558             return fuzzy_not(self._eval_is_odd())
 559
 560         elif is_integer == False:
 561             return False
 562
 563     def _eval_subs(self, old, new):
 564         if self==old:
 565             return new
 566         if isinstance(old, FunctionClass):
 567             return self.__class__(*[s.subs(old, new) for s in self.args ])
 568         coeff1,terms1 = self.as_coeff_terms()
 569         coeff2,terms2 = old.as_coeff_terms()
 570         if terms1==terms2: # (2*a).subs(3*a,y) -> 2/3*y
 571             return new * coeff1/coeff2
 572         l1,l2 = len(terms1),len(terms2)
 573         if l2 == 0:
 574             # if old is just a number, go through the self.args one by one
 575             return Mul(*[x.subs(old, new) for x in self.args])
 576         elif l2<l1:
 577             # old is some something more complex, like:
 578             # (a*b*c*d).subs(b*c,x) -> a*x*d
 579             # then we need to search where in self.args the "old" is, and then
 580             # correctly substitute both terms and coefficients.
 581             for i in xrange(l1-l2+1):
 582                 if terms2==terms1[i:i+l2]:
 583                     m1 = Mul(*terms1[:i]).subs(old,new)
 584                     m2 = Mul(*terms1[i+l2:]).subs(old,new)
 585                     return Mul(*([coeff1/coeff2,m1,new,m2]))
 586         return self.__class__(*[s.subs(old, new) for s in self.args])
 587
 588     def _eval_oseries(self, order):
 589         x = order.symbols[0]
 590         l = []
 591         r = []
 592         lt = []
 593         #separate terms containing "x" (r) and the rest (l)
 594         for t in self.args:
 595             if not t.has(x):
 596                 l.append(t)
 597                 continue
 598             r.append(t)
 599         #if r is empty or just one term, it's easy:
 600         if not r:
 601             if order.contains(1,x): return S.Zero
 602             return Mul(*l)
 603         if len(r)==1:
 604             return Mul(*(l + [r[0].oseries(order)]))
 605         #otherwise, we need to calculate how many orders we need to calculate
 606         #in each term. Currently this is done using as_leading_term, but this
 607         #is fragile and slow, because this involves limits. Let's find some
 608         #more clever approach.
 609         lt = [t.as_leading_term(x) for t in r]
 610         for i in xrange(len(r)):
 611             m = Mul(*(lt[:i]+lt[i+1:]))
 612             #calculate how many orders we want
 613             o = order/m
 614             #expand each term and multiply things together
 615             l.append(r[i].oseries(o))
 616         #shouldn't we rather expand everything? This seems to me to leave
 617         #things as (x+x**2+...)*(x-x**2+...) etc.:
 618         return Mul(*l)
 619
 620     def nseries(self, x, x0, n):
 621         terms = [t.nseries(x, x0, n) for t in self.args]
 622         return Mul(*terms).expand()
 623
 624
 625     def _eval_as_leading_term(self, x):
 626         return Mul(*[t.as_leading_term(x) for t in self.args])
 627
 628     def _eval_conjugate(self):
 629         return Mul(*[t.conjugate() for t in self.args])
 630
 631     def _sage_(self):
 632         s = 1
 633         for x in self.args:
 634             s *= x._sage_()
 635         return s
 636
 637
 638 # /cyclic/
 639 import basic as _
 640 _.Mul       = Mul
 641 del _
 642
 643 import add as _
 644 _.Mul       = Mul
 645 del _
 646
 647 import power as _
 648 _.Mul       = Mul
 649 del _
 650
 651 import numbers as _
 652 _.Mul       = Mul
 653 del _
 654
 655 import operations as _
 656 _.Mul       = Mul
 657 del _