<s> from __future__ import print_function , division <EOL> from collections import defaultdict <EOL> from sympy . core . function import expand_log , count_ops <EOL> from sympy . core import sympify , Basic , Dummy , S , Add , Mul , Pow , expand_mul , factor_terms <EOL> from sympy . core . compatibility import ordered , default_sort_key , reduce <EOL> from sympy . core . numbers import Integer , Rational <EOL> from sympy . core . mul import prod , _keep_coeff <EOL> from sympy . core . rules import Transform <EOL> from sympy . functions import exp_polar , exp , log , root , polarify , unpolarify <EOL> from sympy . polys import lcm , gcd <EOL> from sympy . ntheory . factor_ import multiplicity <EOL> def powsimp ( expr , deep = False , combine = '<STR_LIT:all>' , force = False , measure = count_ops ) : <EOL> """<STR_LIT>""" <EOL> from sympy . matrices . expressions . matexpr import MatrixSymbol <EOL> def recurse ( arg , ** kwargs ) : <EOL> _deep = kwargs . get ( '<STR_LIT>' , deep ) <EOL> _combine = kwargs . get ( '<STR_LIT>' , combine ) <EOL> _force = kwargs . get ( '<STR_LIT>' , force ) <EOL> _measure = kwargs . get ( '<STR_LIT>' , measure ) <EOL> return powsimp ( arg , _deep , _combine , _force , _measure ) <EOL> expr = sympify ( expr ) <EOL> if ( not isinstance ( expr , Basic ) or isinstance ( expr , MatrixSymbol ) or ( <EOL> expr . is_Atom or expr in ( exp_polar ( <NUM_LIT:0> ) , exp_polar ( <NUM_LIT:1> ) ) ) ) : <EOL> return expr <EOL> if deep or expr . is_Add or expr . is_Mul and _y not in expr . args : <EOL> expr = expr . func ( * [ recurse ( w ) for w in expr . args ] ) <EOL> if expr . is_Pow : <EOL> return recurse ( expr * _y , deep = False ) / _y <EOL> if not expr . is_Mul : <EOL> return expr <EOL> if combine in ( '<STR_LIT>' , '<STR_LIT:all>' ) : <EOL> c_powers = defaultdict ( list ) <EOL> nc_part = [ ] <EOL> newexpr = [ ] <EOL> coeff = S . One <EOL> for term in expr . args : <EOL> if term . is_Rational : <EOL> coeff *= term <EOL> continue <EOL> if term . is_Pow : <EOL> term = _denest_pow ( term ) <EOL> if term . is_commutative : <EOL> b , e = term . as_base_exp ( ) <EOL> if deep : <EOL> b , e = [ recurse ( i ) for i in [ b , e ] ] <EOL> if b . is_Pow or b . func is exp : <EOL> b , e = b ** e , S . One <EOL> c_powers [ b ] . append ( e ) <EOL> else : <EOL> if nc_part : <EOL> b1 , e1 = nc_part [ - <NUM_LIT:1> ] . as_base_exp ( ) <EOL> b2 , e2 = term . as_base_exp ( ) <EOL> if ( b1 == b2 and <EOL> e1 . is_commutative and e2 . is_commutative ) : <EOL> nc_part [ - <NUM_LIT:1> ] = Pow ( b1 , Add ( e1 , e2 ) ) <EOL> continue <EOL> nc_part . append ( term ) <EOL> for b , e in ordered ( iter ( c_powers . items ( ) ) ) : <EOL> if ( b and b . is_Number and not all ( ei . is_Number for ei in e ) and coeff is not S . One and <EOL> b not in ( S . One , S . NegativeOne ) ) : <EOL> m = multiplicity ( abs ( b ) , abs ( coeff ) ) <EOL> if m : <EOL> e . append ( m ) <EOL> coeff /= b ** m <EOL> c_powers [ b ] = Add ( * e ) <EOL> if coeff is not S . One : <EOL> if coeff in c_powers : <EOL> c_powers [ coeff ] += S . One <EOL> else : <EOL> c_powers [ coeff ] = S . One <EOL> c_powers = dict ( c_powers ) <EOL> be = list ( c_powers . items ( ) ) <EOL> skip = set ( ) <EOL> for b , e in be : <EOL> if b in skip : <EOL> continue <EOL> bpos = b . is_positive or b . is_polar <EOL> if bpos : <EOL> binv = <NUM_LIT:1> / b <EOL> if b != binv and binv in c_powers : <EOL> if b . as_numer_denom ( ) [ <NUM_LIT:0> ] is S . One : <EOL> c_powers . pop ( b ) <EOL> c_powers [ binv ] -= e <EOL> else : <EOL> skip . add ( binv ) <EOL> e = c_powers . pop ( binv ) <EOL> c_powers [ b ] -= e <EOL> be = list ( c_powers . items ( ) ) <EOL> _n = S . NegativeOne <EOL> for i , ( b , e ) in enumerate ( be ) : <EOL> if ( ( - b ) . is_Symbol or b . is_Add ) and - b in c_powers : <EOL> if ( b . is_positive in ( <NUM_LIT:0> , <NUM_LIT:1> ) or e . is_integer ) : <EOL> c_powers [ - b ] += c_powers . pop ( b ) <EOL> if _n in c_powers : <EOL> c_powers [ _n ] += e <EOL> else : <EOL> c_powers [ _n ] = e <EOL> c_powers = [ ( b , e ) for b , e in c_powers . items ( ) if e ] <EOL> def ratq ( x ) : <EOL> '''<STR_LIT>''' <EOL> return bkey ( x ) [ <NUM_LIT:0> ] [ <NUM_LIT:1> ] <EOL> def bkey ( b , e = None ) : <EOL> '''<STR_LIT>''' <EOL> if e is not None : <EOL> if e . is_Integer : <EOL> return ( b , S . One ) , e <EOL> elif e . is_Rational : <EOL> return ( b , Integer ( e . q ) ) , Integer ( e . p ) <EOL> else : <EOL> c , m = e . as_coeff_Mul ( rational = True ) <EOL> if c is not S . One : <EOL> if m . is_integer : <EOL> return ( b , Integer ( c . q ) ) , m * Integer ( c . p ) <EOL> return ( b ** m , Integer ( c . q ) ) , Integer ( c . p ) <EOL> else : <EOL> return ( b ** e , S . One ) , S . One <EOL> else : <EOL> return bkey ( * b . as_base_exp ( ) ) <EOL> def update ( b ) : <EOL> '''<STR_LIT>''' <EOL> newe , r = divmod ( common_b [ b ] , b [ <NUM_LIT:1> ] ) <EOL> if not r : <EOL> common_b . pop ( b ) <EOL> if newe : <EOL> for m in Mul . make_args ( b [ <NUM_LIT:0> ] ** newe ) : <EOL> b , e = bkey ( m ) <EOL> if b not in common_b : <EOL> common_b [ b ] = <NUM_LIT:0> <EOL> common_b [ b ] += e <EOL> if b [ <NUM_LIT:1> ] != <NUM_LIT:1> : <EOL> bases . append ( b ) <EOL> common_b = { } <EOL> done = [ ] <EOL> bases = [ ] <EOL> for b , e in c_powers : <EOL> b , e = bkey ( b , e ) <EOL> if b in common_b . keys ( ) : <EOL> common_b [ b ] = common_b [ b ] + e <EOL> else : <EOL> common_b [ b ] = e <EOL> if b [ <NUM_LIT:1> ] != <NUM_LIT:1> and b [ <NUM_LIT:0> ] . is_Mul : <EOL> bases . append ( b ) <EOL> c_powers = [ ( b , e ) for b , e in common_b . items ( ) if e ] <EOL> bases . sort ( key = default_sort_key ) <EOL> bases . sort ( key = measure , reverse = True ) <EOL> for base in bases : <EOL> if base not in common_b : <EOL> continue <EOL> b , exponent = base <EOL> last = False <EOL> qlcm = <NUM_LIT:1> <EOL> while True : <EOL> bstart = b <EOL> qstart = qlcm <EOL> bb = [ ] <EOL> ee = [ ] <EOL> for bi in Mul . make_args ( b ) : <EOL> bib , bie = bkey ( bi ) <EOL> if bib not in common_b or common_b [ bib ] < bie : <EOL> ee = bb = [ ] <EOL> break <EOL> ee . append ( [ bie , common_b [ bib ] ] ) <EOL> bb . append ( bib ) <EOL> if ee : <EOL> min1 = ee [ <NUM_LIT:0> ] [ <NUM_LIT:1> ] / ee [ <NUM_LIT:0> ] [ <NUM_LIT:0> ] <EOL> for i in range ( len ( ee ) ) : <EOL> rat = ee [ i ] [ <NUM_LIT:1> ] / ee [ i ] [ <NUM_LIT:0> ] <EOL> if rat < <NUM_LIT:1> : <EOL> break <EOL> min1 = min ( min1 , rat ) <EOL> else : <EOL> for i in range ( len ( bb ) ) : <EOL> common_b [ bb [ i ] ] -= min1 * ee [ i ] [ <NUM_LIT:0> ] <EOL> update ( bb [ i ] ) <EOL> common_b [ base ] += min1 * qstart * exponent <EOL> if ( last <EOL> or len ( common_b ) == <NUM_LIT:1> <EOL> or all ( k [ <NUM_LIT:1> ] == <NUM_LIT:1> for k in common_b ) <EOL> ) : <EOL> break <EOL> qlcm = lcm ( [ ratq ( bi ) for bi in Mul . make_args ( bstart ) ] ) <EOL> if qlcm == <NUM_LIT:1> : <EOL> break <EOL> b = bstart ** qlcm <EOL> qlcm *= qstart <EOL> if all ( ratq ( bi ) == <NUM_LIT:1> for bi in Mul . make_args ( b ) ) : <EOL> last = True <EOL> b , q = base <EOL> done . append ( ( b , common_b . pop ( base ) * Rational ( <NUM_LIT:1> , q ) ) ) <EOL> c_powers = done <EOL> for ( b , q ) , e in common_b . items ( ) : <EOL> if ( b . is_Pow or b . func is exp ) and q is not S . One and not b . exp . is_Rational : <EOL> b , be = b . as_base_exp ( ) <EOL> b = b ** ( be / q ) <EOL> else : <EOL> b = root ( b , q ) <EOL> c_powers . append ( ( b , e ) ) <EOL> check = len ( c_powers ) <EOL> c_powers = dict ( c_powers ) <EOL> assert len ( c_powers ) == check <EOL> newexpr = expr . func ( * ( newexpr + [ Pow ( b , e ) for b , e in c_powers . items ( ) ] ) ) <EOL> if combine == '<STR_LIT>' : <EOL> return expr . func ( newexpr , expr . func ( * nc_part ) ) <EOL> else : <EOL> return recurse ( expr . func ( * nc_part ) , combine = '<STR_LIT>' ) * recurse ( newexpr , combine = '<STR_LIT>' ) <EOL> elif combine == '<STR_LIT>' : <EOL> c_powers = [ ] <EOL> nc_part = [ ] <EOL> for term in expr . args : <EOL> if term . is_commutative : <EOL> c_powers . append ( list ( term . as_base_exp ( ) ) ) <EOL> else : <EOL> if nc_part : <EOL> b1 , e1 = nc_part [ - <NUM_LIT:1> ] . as_base_exp ( ) <EOL> b2 , e2 = term . as_base_exp ( ) <EOL> if ( e1 == e2 and e2 . is_commutative ) : <EOL> nc_part [ - <NUM_LIT:1> ] = Pow ( b1 * b2 , e1 ) <EOL> continue <EOL> nc_part . append ( term ) <EOL> for i in range ( len ( c_powers ) ) : <EOL> b , e = c_powers [ i ] <EOL> if not ( all ( x . is_nonnegative for x in b . as_numer_denom ( ) ) or e . is_integer or force or b . is_polar ) : <EOL> continue <EOL> exp_c , exp_t = e . as_coeff_Mul ( rational = True ) <EOL> if exp_c is not S . One and exp_t is not S . One : <EOL> c_powers [ i ] = [ Pow ( b , exp_c ) , exp_t ] <EOL> c_exp = defaultdict ( list ) <EOL> for b , e in c_powers : <EOL> if deep : <EOL> e = recurse ( e ) <EOL> c_exp [ e ] . append ( b ) <EOL> del c_powers <EOL> c_powers = defaultdict ( list ) <EOL> for e in c_exp : <EOL> bases = c_exp [ e ] <EOL> if len ( bases ) == <NUM_LIT:1> : <EOL> new_base = bases [ <NUM_LIT:0> ] <EOL> elif e . is_integer or force : <EOL> new_base = expr . func ( * bases ) <EOL> else : <EOL> unk = [ ] <EOL> nonneg = [ ] <EOL> neg = [ ] <EOL> for bi in bases : <EOL> if bi . is_negative : <EOL> neg . append ( bi ) <EOL> elif bi . is_nonnegative : <EOL> nonneg . append ( bi ) <EOL> elif bi . is_polar : <EOL> nonneg . append ( <EOL> bi ) <EOL> else : <EOL> unk . append ( bi ) <EOL> if len ( unk ) == <NUM_LIT:1> and not neg or len ( neg ) == <NUM_LIT:1> and not unk : <EOL> nonneg . extend ( unk + neg ) <EOL> unk = neg = [ ] <EOL> elif neg : <EOL> israt = False <EOL> if e . is_Rational : <EOL> israt = True <EOL> else : <EOL> p , d = e . as_numer_denom ( ) <EOL> if p . is_integer and d . is_integer : <EOL> israt = True <EOL> if israt : <EOL> neg = [ - w for w in neg ] <EOL> unk . extend ( [ S . NegativeOne ] * len ( neg ) ) <EOL> else : <EOL> unk . extend ( neg ) <EOL> neg = [ ] <EOL> del israt <EOL> for b in unk : <EOL> c_powers [ b ] . append ( e ) <EOL> new_base = expr . func ( * ( nonneg + neg ) ) <EOL> def _terms ( e ) : <EOL> if e . is_Add : <EOL> return sum ( [ _terms ( ai ) for ai in e . args ] ) <EOL> if e . is_Mul : <EOL> return prod ( [ _terms ( mi ) for mi in e . args ] ) <EOL> return <NUM_LIT:1> <EOL> xnew_base = expand_mul ( new_base , deep = False ) <EOL> if len ( Add . make_args ( xnew_base ) ) < _terms ( new_base ) : <EOL> new_base = factor_terms ( xnew_base ) <EOL> c_powers [ new_base ] . append ( e ) <EOL> c_part = [ Pow ( b , ei ) for b , e in c_powers . items ( ) for ei in e ] <EOL> return expr . func ( * ( c_part + nc_part ) ) <EOL> else : <EOL> raise ValueError ( "<STR_LIT>" ) <EOL> def powdenest ( eq , force = False , polar = False ) : <EOL> r"""<STR_LIT>""" <EOL> from sympy . simplify . simplify import posify <EOL> if force : <EOL> eq , rep = posify ( eq ) <EOL> return powdenest ( eq , force = False ) . xreplace ( rep ) <EOL> if polar : <EOL> eq , rep = polarify ( eq ) <EOL> return unpolarify ( powdenest ( unpolarify ( eq , exponents_only = True ) ) , rep ) <EOL> new = powsimp ( sympify ( eq ) ) <EOL> return new . xreplace ( Transform ( <EOL> _denest_pow , filter = lambda m : m . is_Pow or m . func is exp ) ) <EOL> _y = Dummy ( '<STR_LIT:y>' ) <EOL> def _denest_pow ( eq ) : <EOL> """<STR_LIT>""" <EOL> from sympy . simplify . simplify import logcombine <EOL> b , e = eq . as_base_exp ( ) <EOL> if b . is_Pow or isinstance ( b . func , exp ) and e != <NUM_LIT:1> : <EOL> new = b . _eval_power ( e ) <EOL> if new is not None : <EOL> eq = new <EOL> b , e = new . as_base_exp ( ) <EOL> if b is S . Exp1 and e . is_Mul : <EOL> logs = [ ] <EOL> other = [ ] <EOL> for ei in e . args : <EOL> if any ( ai . func is log for ai in Add . make_args ( ei ) ) : <EOL> logs . append ( ei ) <EOL> else : <EOL> other . append ( ei ) <EOL> logs = logcombine ( Mul ( * logs ) ) <EOL> return Pow ( exp ( logs ) , Mul ( * other ) ) <EOL> _ , be = b . as_base_exp ( ) <EOL> if be is S . One and not ( b . is_Mul or <EOL> b . is_Rational and b . q != <NUM_LIT:1> or <EOL> b . is_positive ) : <EOL> return eq <EOL> polars , nonpolars = [ ] , [ ] <EOL> for bb in Mul . make_args ( b ) : <EOL> if bb . is_polar : <EOL> polars . append ( bb . as_base_exp ( ) ) <EOL> else : <EOL> nonpolars . append ( bb ) <EOL> if len ( polars ) == <NUM_LIT:1> and not polars [ <NUM_LIT:0> ] [ <NUM_LIT:0> ] . is_Mul : <EOL> return Pow ( polars [ <NUM_LIT:0> ] [ <NUM_LIT:0> ] , polars [ <NUM_LIT:0> ] [ <NUM_LIT:1> ] * e ) * powdenest ( Mul ( * nonpolars ) ** e ) <EOL> elif polars : <EOL> return Mul ( * [ powdenest ( bb ** ( ee * e ) ) for ( bb , ee ) in polars ] ) * powdenest ( Mul ( * nonpolars ) ** e ) <EOL> if b . is_Integer : <EOL> logb = expand_log ( log ( b ) ) <EOL> if logb . is_Mul : <EOL> c , logb = logb . args <EOL> e *= c <EOL> base = logb . args [ <NUM_LIT:0> ] <EOL> return Pow ( base , e ) <EOL> if not b . is_Mul or any ( s . is_Atom for s in Mul . make_args ( b ) ) : <EOL> return eq <EOL> def nc_gcd ( aa , bb ) : <EOL> a , b = [ i . as_coeff_Mul ( ) for i in [ aa , bb ] ] <EOL> c = gcd ( a [ <NUM_LIT:0> ] , b [ <NUM_LIT:0> ] ) . as_numer_denom ( ) [ <NUM_LIT:0> ] <EOL> g = Mul ( * ( a [ <NUM_LIT:1> ] . args_cnc ( cset = True ) [ <NUM_LIT:0> ] & b [ <NUM_LIT:1> ] . args_cnc ( cset = True ) [ <NUM_LIT:0> ] ) ) <EOL> return _keep_coeff ( c , g ) <EOL> glogb = expand_log ( log ( b ) ) <EOL> if glogb . is_Add : <EOL> args = glogb . args <EOL> g = reduce ( nc_gcd , args ) <EOL> if g != <NUM_LIT:1> : <EOL> cg , rg = g . as_coeff_Mul ( ) <EOL> glogb = _keep_coeff ( cg , rg * Add ( * [ a / g for a in args ] ) ) <EOL> if glogb . func is log or not glogb . is_Mul : <EOL> if glogb . args [ <NUM_LIT:0> ] . is_Pow or glogb . args [ <NUM_LIT:0> ] . func is exp : <EOL> glogb = _denest_pow ( glogb . args [ <NUM_LIT:0> ] ) <EOL> if ( abs ( glogb . exp ) < <NUM_LIT:1> ) == True : <EOL> return Pow ( glogb . base , glogb . exp * e ) <EOL> return eq <EOL> add = [ ] <EOL> other = [ ] <EOL> for a in glogb . args : <EOL> if a . is_Add : <EOL> add . append ( a ) <EOL> else : <EOL> other . append ( a ) <EOL> return Pow ( exp ( logcombine ( Mul ( * add ) ) ) , e * Mul ( * other ) ) </s>
