Coverage for sympy/simplify/fu.py : 49%

""" 

Implementation of the trigsimp algorithm by Fu et al. 

The idea behind the ``fu`` algorithm is to use a sequence of rules, applied 

in what is heuristically known to be a smart order, to select a simpler 

expression that is equivalent to the input. 

There are transform rules in which a single rule is applied to the 

expression tree. The following are just mnemonic in nature; see the 

docstrings for examples. 

TR0 - simplify expression 

TR1 - sec-csc to cos-sin 

TR2 - tan-cot to sin-cos ratio 

TR2i - sin-cos ratio to tan 

TR3 - angle canonicalization 

TR4 - functions at special angles 

TR5 - powers of sin to powers of cos 

TR6 - powers of cos to powers of sin 

TR7 - reduce cos power (increase angle) 

TR8 - expand products of sin-cos to sums 

TR9 - contract sums of sin-cos to products 

TR10 - separate sin-cos arguments 

TR10i - collect sin-cos arguments 

TR11 - reduce double angles 

TR12 - separate tan arguments 

TR12i - collect tan arguments 

TR13 - expand product of tan-cot 

TRmorrie - prod(cos(x*2**i), (i, 0, k - 1)) -> sin(2**k*x)/(2**k*sin(x)) 

TR14 - factored powers of sin or cos to cos or sin power 

TR15 - negative powers of sin to cot power 

TR16 - negative powers of cos to tan power 

TR22 - tan-cot powers to negative powers of sec-csc functions 

TR111 - negative sin-cos-tan powers to csc-sec-cot 

There are 4 combination transforms (CTR1 - CTR4) in which a sequence of 

transformations are applied and the simplest expression is selected from 

a few options. 

Finally, there are the 2 rule lists (RL1 and RL2), which apply a 

sequence of transformations and combined transformations, and the ``fu`` 

algorithm itself, which applies rules and rule lists and selects the 

best expressions. There is also a function ``L`` which counts the number 

of trigonometric functions that appear in the expression. 

Other than TR0, re-writing of expressions is not done by the transformations. 

e.g. TR10i finds pairs of terms in a sum that are in the form like 

``cos(x)*cos(y) + sin(x)*sin(y)``. Such expression are targeted in a bottom-up 

traversal of the expression, but no manipulation to make them appear is 

attempted. For example, 

Set-up for examples below: 

>>> from sympy.simplify.fu import fu, L, TR9, TR10i, TR11 

>>> from sympy import factor, sin, cos, powsimp 

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

>>> from time import time 

>>> eq = cos(x + y)/cos(x) 

>>> TR10i(eq.expand(trig=True)) 

-sin(x)*sin(y)/cos(x) + cos(y) 

If the expression is put in "normal" form (with a common denominator) then 

the transformation is successful: 

>>> TR10i(_.normal()) 

cos(x + y)/cos(x) 

TR11's behavior is similar. It rewrites double angles as smaller angles but 

doesn't do any simplification of the result. 

>>> TR11(sin(2)**a*cos(1)**(-a), 1) 

(2*sin(1)*cos(1))**a*cos(1)**(-a) 

>>> powsimp(_) 

(2*sin(1))**a 

The temptation is to try make these TR rules "smarter" but that should really 

be done at a higher level; the TR rules should try maintain the "do one thing 

well" principle. There is one exception, however. In TR10i and TR9 terms are 

recognized even when they are each multiplied by a common factor: 

>>> fu(a*cos(x)*cos(y) + a*sin(x)*sin(y)) 

a*cos(x - y) 

Factoring with ``factor_terms`` is used but it it "JIT"-like, being delayed 

until it is deemed necessary. Furthermore, if the factoring does not 

help with the simplification, it is not retained, so 

``a*cos(x)*cos(y) + a*sin(x)*sin(z)`` does not become the factored 

(but unsimplified in the trigonometric sense) expression: 

>>> fu(a*cos(x)*cos(y) + a*sin(x)*sin(z)) 

a*sin(x)*sin(z) + a*cos(x)*cos(y) 

In some cases factoring might be a good idea, but the user is left 

to make that decision. For example: 

>>> expr=((15*sin(2*x) + 19*sin(x + y) + 17*sin(x + z) + 19*cos(x - z) + 

... 25)*(20*sin(2*x) + 15*sin(x + y) + sin(y + z) + 14*cos(x - z) + 

... 14*cos(y - z))*(9*sin(2*y) + 12*sin(y + z) + 10*cos(x - y) + 2*cos(y - 

... z) + 18)).expand(trig=True).expand() 

In the expanded state, there are nearly 1000 trig functions: 

>>> L(expr) 

932 

If the expression where factored first, this would take time but the 

resulting expression would be transformed very quickly: 

>>> def clock(f, n=2): 

... t=time(); f(); return round(time()-t, n) 

... 

>>> clock(lambda: factor(expr)) # doctest: +SKIP 

0.86 

>>> clock(lambda: TR10i(expr), 3) # doctest: +SKIP 

0.016 

If the unexpanded expression is used, the transformation takes longer but 

not as long as it took to factor it and then transform it: 

>>> clock(lambda: TR10i(expr), 2) # doctest: +SKIP 

0.28 

So neither expansion nor factoring is used in ``TR10i``: if the 

expression is already factored (or partially factored) then expansion 

with ``trig=True`` would destroy what is already known and take 

longer; if the expression is expanded, factoring may take longer than 

simply applying the transformation itself. 

Although the algorithms should be canonical, always giving the same 

result, they may not yield the best result. This, in general, is 

the nature of simplification where searching all possible transformation 

paths is very expensive. Here is a simple example. There are 6 terms 

in the following sum: 

>>> expr = (sin(x)**2*cos(y)*cos(z) + sin(x)*sin(y)*cos(x)*cos(z) + 

... sin(x)*sin(z)*cos(x)*cos(y) + sin(y)*sin(z)*cos(x)**2 + sin(y)*sin(z) + 

... cos(y)*cos(z)) 

>>> args = expr.args 

Serendipitously, fu gives the best result: 

>>> fu(expr) 

3*cos(y - z)/2 - cos(2*x + y + z)/2 

But if different terms were combined, a less-optimal result might be 

obtained, requiring some additional work to get better simplification, 

but still less than optimal. The following shows an alternative form 

of ``expr`` that resists optimal simplification once a given step 

is taken since it leads to a dead end: 

>>> TR9(-cos(x)**2*cos(y + z) + 3*cos(y - z)/2 + 

... cos(y + z)/2 + cos(-2*x + y + z)/4 - cos(2*x + y + z)/4) 

sin(2*x)*sin(y + z)/2 - cos(x)**2*cos(y + z) + 3*cos(y - z)/2 + cos(y + z)/2 

Here is a smaller expression that exhibits the same behavior: 

>>> a = sin(x)*sin(z)*cos(x)*cos(y) + sin(x)*sin(y)*cos(x)*cos(z) 

>>> TR10i(a) 

sin(x)*sin(y + z)*cos(x) 

>>> newa = _ 

>>> TR10i(expr - a) # this combines two more of the remaining terms 

sin(x)**2*cos(y)*cos(z) + sin(y)*sin(z)*cos(x)**2 + cos(y - z) 

>>> TR10i(_ + newa) == _ + newa # but now there is no more simplification 

True 

Without getting lucky or trying all possible pairings of arguments, the 

final result may be less than optimal and impossible to find without 

better heuristics or brute force trial of all possibilities. 

Notes 

===== 

This work was started by Dimitar Vlahovski at the Technological School 

"Electronic systems" (30.11.2011). 

References 

========== 

Fu, Hongguang, Xiuqin Zhong, and Zhenbing Zeng. "Automated and readable 

simplification of trigonometric expressions." Mathematical and computer 

modelling 44.11 (2006): 1169-1177. 

http://rfdz.ph-noe.ac.at/fileadmin/Mathematik_Uploads/ACDCA/DESTIME2006/DES_contribs/Fu/simplification.pdf 

http://www.sosmath.com/trig/Trig5/trig5/pdf/pdf.html gives a formula sheet. 

""" 

from __future__ import print_function, division 

from collections import defaultdict 

from sympy.simplify.simplify import bottom_up 

from sympy.core.sympify import sympify 

from sympy.functions.elementary.trigonometric import ( 

cos, sin, tan, cot, sec, csc, sqrt, TrigonometricFunction) 

from sympy.functions.elementary.hyperbolic import ( 

cosh, sinh, tanh, coth, HyperbolicFunction) 

from sympy.core.compatibility import ordered, range 

from sympy.core.expr import Expr 

from sympy.core.mul import Mul 

from sympy.core.power import Pow 

from sympy.core.function import expand_mul 

from sympy.core.add import Add 

from sympy.core.symbol import Dummy 

from sympy.core.exprtools import Factors, gcd_terms, factor_terms 

from sympy.core.basic import S 

from sympy.core.numbers import pi, I 

from sympy.strategies.tree import greedy 

from sympy.strategies.core import identity, debug 

from sympy.polys.polytools import factor 

from sympy.ntheory.factor_ import perfect_power 

from sympy import SYMPY_DEBUG 

# ================== Fu-like tools =========================== 

def TR0(rv): 

"""Simplification of rational polynomials, trying to simplify 

the expression, e.g. combine things like 3*x + 2*x, etc.... 

""" 

# although it would be nice to use cancel, it doesn't work 

# with noncommutatives 

return rv.normal().factor().expand() 

def TR1(rv): 

"""Replace sec, csc with 1/cos, 1/sin 

Examples 

======== 

>>> from sympy.simplify.fu import TR1, sec, csc 

>>> from sympy.abc import x 

>>> TR1(2*csc(x) + sec(x)) 

1/cos(x) + 2/sin(x) 

""" 

def f(rv): 

if rv.func is sec: 

a = rv.args[0] 

return S.One/cos(a) 

elif rv.func is csc: 

a = rv.args[0] 

return S.One/sin(a) 

return rv 

return bottom_up(rv, f) 

def TR2(rv): 

"""Replace tan and cot with sin/cos and cos/sin 

Examples 

======== 

>>> from sympy.simplify.fu import TR2 

>>> from sympy.abc import x 

>>> from sympy import tan, cot, sin, cos 

>>> TR2(tan(x)) 

sin(x)/cos(x) 

>>> TR2(cot(x)) 

cos(x)/sin(x) 

>>> TR2(tan(tan(x) - sin(x)/cos(x))) 

0 

""" 

def f(rv): 

if rv.func is tan: 

a = rv.args[0] 

return sin(a)/cos(a) 

elif rv.func is cot: 

a = rv.args[0] 

return cos(a)/sin(a) 

return rv 

return bottom_up(rv, f) 

def TR2i(rv, half=False): 

"""Converts ratios involving sin and cos as follows:: 

sin(x)/cos(x) -> tan(x) 

sin(x)/(cos(x) + 1) -> tan(x/2) if half=True 

Examples 

======== 

>>> from sympy.simplify.fu import TR2i 

>>> from sympy.abc import x, a 

>>> from sympy import sin, cos 

>>> TR2i(sin(x)/cos(x)) 

tan(x) 

Powers of the numerator and denominator are also recognized 

>>> TR2i(sin(x)**2/(cos(x) + 1)**2, half=True) 

tan(x/2)**2 

The transformation does not take place unless assumptions allow 

(i.e. the base must be positive or the exponent must be an integer 

for both numerator and denominator) 

>>> TR2i(sin(x)**a/(cos(x) + 1)**a) 

(cos(x) + 1)**(-a)*sin(x)**a 

""" 

def f(rv): 

if not rv.is_Mul: 

return rv 

n, d = rv.as_numer_denom() 

if n.is_Atom or d.is_Atom: 

return rv 

def ok(k, e): 

# initial filtering of factors 

return ( 

(e.is_integer or k.is_positive) and ( 

k.func in (sin, cos) or (half and 

k.is_Add and 

len(k.args) >= 2 and 

any(any(ai.func is cos or ai.is_Pow and ai.base is cos 

for ai in Mul.make_args(a)) for a in k.args)))) 

n = n.as_powers_dict() 

ndone = [(k, n.pop(k)) for k in list(n.keys()) if not ok(k, n[k])] 

if not n: 

return rv 

d = d.as_powers_dict() 

ddone = [(k, d.pop(k)) for k in list(d.keys()) if not ok(k, d[k])] 

if not d: 

return rv 

# factoring if necessary 

def factorize(d, ddone): 

newk = [] 

for k in d: 

if k.is_Add and len(k.args) > 1: 

knew = factor(k) if half else factor_terms(k) 

if knew != k: 

newk.append((k, knew)) 

if newk: 

for i, (k, knew) in enumerate(newk): 

del d[k] 

newk[i] = knew 

newk = Mul(*newk).as_powers_dict() 

for k in newk: 

v = d[k] + newk[k] 

if ok(k, v): 

d[k] = v 

else: 

ddone.append((k, v)) 

del newk 

factorize(n, ndone) 

factorize(d, ddone) 

# joining 

t = [] 

for k in n: 

if k.func is sin: 

a = cos(k.args[0], evaluate=False) 

if a in d and d[a] == n[k]: 

t.append(tan(k.args[0])**n[k]) 

n[k] = d[a] = None 

elif half: 

a1 = 1 + a 

if a1 in d and d[a1] == n[k]: 

t.append((tan(k.args[0]/2))**n[k]) 

n[k] = d[a1] = None 

elif k.func is cos: 

a = sin(k.args[0], evaluate=False) 

if a in d and d[a] == n[k]: 

t.append(tan(k.args[0])**-n[k]) 

n[k] = d[a] = None 

elif half and k.is_Add and k.args[0] is S.One and \ 

k.args[1].func is cos: 

a = sin(k.args[1].args[0], evaluate=False) 

if a in d and d[a] == n[k] and (d[a].is_integer or \ 

a.is_positive): 

t.append(tan(a.args[0]/2)**-n[k]) 

n[k] = d[a] = None 

if t: 

rv = Mul(*(t + [b**e for b, e in n.items() if e]))/\ 

Mul(*[b**e for b, e in d.items() if e]) 

rv *= Mul(*[b**e for b, e in ndone])/Mul(*[b**e for b, e in ddone]) 

return rv 

return bottom_up(rv, f) 

def TR3(rv): 

"""Induced formula: example sin(-a) = -sin(a) 

Examples 

======== 

>>> from sympy.simplify.fu import TR3 

>>> from sympy.abc import x, y 

>>> from sympy import pi 

>>> from sympy import cos 

>>> TR3(cos(y - x*(y - x))) 

cos(x*(x - y) + y) 

>>> cos(pi/2 + x) 

-sin(x) 

>>> cos(30*pi/2 + x) 

-cos(x) 

""" 

from sympy.simplify.simplify import signsimp 

# Negative argument (already automatic for funcs like sin(-x) -> -sin(x) 

# but more complicated expressions can use it, too). Also, trig angles 

# between pi/4 and pi/2 are not reduced to an angle between 0 and pi/4. 

# The following are automatically handled: 

# Argument of type: pi/2 +/- angle 

# Argument of type: pi +/- angle 

# Argument of type : 2k*pi +/- angle 

def f(rv): 

if not isinstance(rv, TrigonometricFunction): 

return rv 

rv = rv.func(signsimp(rv.args[0])) 

if (rv.args[0] - S.Pi/4).is_positive is (S.Pi/2 - rv.args[0]).is_positive is True: 

fmap = {cos: sin, sin: cos, tan: cot, cot: tan, sec: csc, csc: sec} 

rv = fmap[rv.func](S.Pi/2 - rv.args[0]) 

return rv 

return bottom_up(rv, f) 

def TR4(rv): 

"""Identify values of special angles. 

a= 0 pi/6 pi/4 pi/3 pi/2 

---------------------------------------------------- 

cos(a) 0 1/2 sqrt(2)/2 sqrt(3)/2 1 

sin(a) 1 sqrt(3)/2 sqrt(2)/2 1/2 0 

tan(a) 0 sqt(3)/3 1 sqrt(3) -- 

Examples 

======== 

>>> from sympy.simplify.fu import TR4 

>>> from sympy import pi 

>>> from sympy import cos, sin, tan, cot 

>>> for s in (0, pi/6, pi/4, pi/3, pi/2): 

... print('%s %s %s %s' % (cos(s), sin(s), tan(s), cot(s))) 

... 

1 0 0 zoo 

sqrt(3)/2 1/2 sqrt(3)/3 sqrt(3) 

sqrt(2)/2 sqrt(2)/2 1 1 

1/2 sqrt(3)/2 sqrt(3) sqrt(3)/3 

0 1 zoo 0 

""" 

# special values at 0, pi/6, pi/4, pi/3, pi/2 already handled 

return rv 

def _TR56(rv, f, g, h, max, pow): 

"""Helper for TR5 and TR6 to replace f**2 with h(g**2) 

Options 

======= 

max : controls size of exponent that can appear on f 

e.g. if max=4 then f**4 will be changed to h(g**2)**2. 

pow : controls whether the exponent must be a perfect power of 2 

e.g. if pow=True (and max >= 6) then f**6 will not be changed 

but f**8 will be changed to h(g**2)**4 

>>> from sympy.simplify.fu import _TR56 as T 

>>> from sympy.abc import x 

>>> from sympy import sin, cos 

>>> h = lambda x: 1 - x 

>>> T(sin(x)**3, sin, cos, h, 4, False) 

sin(x)**3 

>>> T(sin(x)**6, sin, cos, h, 6, False) 

(-cos(x)**2 + 1)**3 

>>> T(sin(x)**6, sin, cos, h, 6, True) 

sin(x)**6 

>>> T(sin(x)**8, sin, cos, h, 10, True) 

(-cos(x)**2 + 1)**4 

""" 

def _f(rv): 

# I'm not sure if this transformation should target all even powers 

# or only those expressible as powers of 2. Also, should it only 

# make the changes in powers that appear in sums -- making an isolated 

# change is not going to allow a simplification as far as I can tell. 

if not (rv.is_Pow and rv.base.func == f): 

return rv 

if (rv.exp < 0) == True: 

return rv 

if (rv.exp > max) == True: 

return rv 

if rv.exp == 2: 

return h(g(rv.base.args[0])**2) 

else: 

if rv.exp == 4: 

e = 2 

elif not pow: 

if rv.exp % 2: 

return rv 

e = rv.exp//2 

else: 

p = perfect_power(rv.exp) 

if not p: 

return rv 

e = rv.exp//2 

return h(g(rv.base.args[0])**2)**e 

return bottom_up(rv, _f) 

def TR5(rv, max=4, pow=False): 

"""Replacement of sin**2 with 1 - cos(x)**2. 

See _TR56 docstring for advanced use of ``max`` and ``pow``. 

Examples 

======== 

>>> from sympy.simplify.fu import TR5 

>>> from sympy.abc import x 

>>> from sympy import sin 

>>> TR5(sin(x)**2) 

-cos(x)**2 + 1 

>>> TR5(sin(x)**-2) # unchanged 

sin(x)**(-2) 

>>> TR5(sin(x)**4) 

(-cos(x)**2 + 1)**2 

""" 

return _TR56(rv, sin, cos, lambda x: 1 - x, max=max, pow=pow) 

def TR6(rv, max=4, pow=False): 

"""Replacement of cos**2 with 1 - sin(x)**2. 

See _TR56 docstring for advanced use of ``max`` and ``pow``. 

Examples 

======== 

>>> from sympy.simplify.fu import TR6 

>>> from sympy.abc import x 

>>> from sympy import cos 

>>> TR6(cos(x)**2) 

-sin(x)**2 + 1 

>>> TR6(cos(x)**-2) #unchanged 

cos(x)**(-2) 

>>> TR6(cos(x)**4) 

(-sin(x)**2 + 1)**2 

""" 

return _TR56(rv, cos, sin, lambda x: 1 - x, max=max, pow=pow) 

def TR7(rv): 

"""Lowering the degree of cos(x)**2 

Examples 

======== 

>>> from sympy.simplify.fu import TR7 

>>> from sympy.abc import x 

>>> from sympy import cos 

>>> TR7(cos(x)**2) 

cos(2*x)/2 + 1/2 

>>> TR7(cos(x)**2 + 1) 

cos(2*x)/2 + 3/2 

""" 

def f(rv): 

if not (rv.is_Pow and rv.base.func == cos and rv.exp == 2): 

return rv 

return (1 + cos(2*rv.base.args[0]))/2 

return bottom_up(rv, f) 

def TR8(rv, first=True): 

"""Converting products of ``cos`` and/or ``sin`` to a sum or 

difference of ``cos`` and or ``sin`` terms. 

Examples 

======== 

>>> from sympy.simplify.fu import TR8, TR7 

>>> from sympy import cos, sin 

>>> TR8(cos(2)*cos(3)) 

cos(5)/2 + cos(1)/2 

>>> TR8(cos(2)*sin(3)) 

sin(5)/2 + sin(1)/2 

>>> TR8(sin(2)*sin(3)) 

-cos(5)/2 + cos(1)/2 

""" 

def f(rv): 

if not ( 

rv.is_Mul or 

rv.is_Pow and 

rv.base.func in (cos, sin) and 

(rv.exp.is_integer or rv.base.is_positive)): 

return rv 

if first: 

n, d = [expand_mul(i) for i in rv.as_numer_denom()] 

newn = TR8(n, first=False) 

newd = TR8(d, first=False) 

if newn != n or newd != d: 

rv = gcd_terms(newn/newd) 

if rv.is_Mul and rv.args[0].is_Rational and \ 

len(rv.args) == 2 and rv.args[1].is_Add: 

rv = Mul(*rv.as_coeff_Mul()) 

return rv 

args = {cos: [], sin: [], None: []} 

for a in ordered(Mul.make_args(rv)): 

if a.func in (cos, sin): 

args[a.func].append(a.args[0]) 

elif (a.is_Pow and a.exp.is_Integer and a.exp > 0 and \ 

a.base.func in (cos, sin)): 

# XXX this is ok but pathological expression could be handled 

# more efficiently as in TRmorrie 

args[a.base.func].extend([a.base.args[0]]*a.exp) 

else: 

args[None].append(a) 

c = args[cos] 

s = args[sin] 

if not (c and s or len(c) > 1 or len(s) > 1): 

return rv 

args = args[None] 

n = min(len(c), len(s)) 

for i in range(n): 

a1 = s.pop() 

a2 = c.pop() 

args.append((sin(a1 + a2) + sin(a1 - a2))/2) 

while len(c) > 1: 

a1 = c.pop() 

a2 = c.pop() 

args.append((cos(a1 + a2) + cos(a1 - a2))/2) 

if c: 

args.append(cos(c.pop())) 

while len(s) > 1: 

a1 = s.pop()