sympy/core/mul.py

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