1=========================================== 2Hongguang Fu's Trigonometric Simplification 3=========================================== 4 5.. currentmodule:: sympy.simplify.fu 6 7Implementation of the trigsimp algorithm by Fu et al. 8 9The idea behind the Fu algorithm is to use a sequence of rules 10that students learn during their pre-calculus courses. 11The rules are applied heuristically and it uses a greedy algorithm to 12apply multiple rules simultaneously and choose the result with the least 13leaf counts. 14 15There are transform rules in which a single rule is applied to the 16expression tree. The following are just mnemonic in nature; see the 17docstrings for examples. 18 19- :func:`TR0` - simplify expression 20- :func:`TR1` - sec-csc to cos-sin 21- :func:`TR2` - tan-cot to sin-cos ratio 22- :func:`TR2i` - sin-cos ratio to tan 23- :func:`TR3` - angle canonicalization 24- :func:`TR4` - functions at special angles 25- :func:`TR5` - powers of sin to powers of cos 26- :func:`TR6` - powers of cos to powers of sin 27- :func:`TR7` - reduce cos power (increase angle) 28- :func:`TR8` - expand products of sin-cos to sums 29- :func:`TR9` - contract sums of sin-cos to products 30- :func:`TR10` - separate sin-cos arguments 31- :func:`TR10i` - collect sin-cos arguments 32- :func:`TR11` - reduce double angles 33- :func:`TR12` - separate tan arguments 34- :func:`TR12i` - collect tan arguments 35- :func:`TR13` - expand product of tan-cot 36- :func:`TRmorrie` - prod(cos(x*2**i), (i, 0, k - 1)) -> sin(2**k*x)/(2**k*sin(x)) 37- :func:`TR14` - factored powers of sin or cos to cos or sin power 38- :func:`TR15` - negative powers of sin to cot power 39- :func:`TR16` - negative powers of cos to tan power 40- :func:`TR22` - tan-cot powers to negative powers of sec-csc functions 41- :func:`TR111` - negative sin-cos-tan powers to csc-sec-cot 42 43There are 4 combination transforms (CTR1 - CTR4) in which a sequence of 44transformations are applied and the simplest expression is selected from 45a few options. 46 47Finally, there are the 2 rule lists (RL1 and RL2), which apply a 48sequence of transformations and combined transformations, and the ``fu`` 49algorithm itself, which applies rules and rule lists and selects the 50best expressions. There is also a function ``L`` which counts the number 51of trigonometric functions that appear in the expression. 52 53Other than TR0, re-writing of expressions is not done by the transformations. 54e.g. TR10i finds pairs of terms in a sum that are in the form like 55``cos(x)*cos(y) + sin(x)*sin(y)``. Such expression are targeted in a bottom-up 56traversal of the expression, but no manipulation to make them appear is 57attempted. For example, 58 59Set-up for examples below: 60 61 >>> from sympy.simplify.fu import fu, L, TR9, TR10i, TR11 62 >>> from sympy import factor, sin, cos, powsimp 63 >>> from sympy.abc import x, y, z, a 64 >>> from time import time 65 66 >>> eq = cos(x + y)/cos(x) 67 >>> TR10i(eq.expand(trig=True)) 68 -sin(x)*sin(y)/cos(x) + cos(y) 69 70If the expression is put in "normal" form (with a common denominator) then 71the transformation is successful: 72 73 >>> TR10i(_.normal()) 74 cos(x + y)/cos(x) 75 76TR11's behavior is similar. It rewrites double angles as smaller angles but 77doesn't do any simplification of the result. 78 79 >>> TR11(sin(2)**a*cos(1)**(-a), 1) 80 (2*sin(1)*cos(1))**a/cos(1)**a 81 >>> powsimp(_) 82 (2*sin(1))**a 83 84The temptation is to try make these TR rules "smarter" but that should really 85be done at a higher level; the TR rules should try maintain the "do one thing 86well" principle. There is one exception, however. In TR10i and TR9 terms are 87recognized even when they are each multiplied by a common factor: 88 89 >>> fu(a*cos(x)*cos(y) + a*sin(x)*sin(y)) 90 a*cos(x - y) 91 92Factoring with ``factor_terms`` is used but it is "JIT"-like, being delayed 93until it is deemed necessary. Furthermore, if the factoring does not 94help with the simplification, it is not retained, so 95``a*cos(x)*cos(y) + a*sin(x)*sin(z)`` does not become a factored 96(but unsimplified in the trigonometric sense) expression: 97 98 >>> fu(a*cos(x)*cos(y) + a*sin(x)*sin(z)) 99 a*sin(x)*sin(z) + a*cos(x)*cos(y) 100 101In some cases factoring might be a good idea, but the user is left 102to make that decision. For example: 103 104 >>> expr=((15*sin(2*x) + 19*sin(x + y) + 17*sin(x + z) + 19*cos(x - z) + 105 ... 25)*(20*sin(2*x) + 15*sin(x + y) + sin(y + z) + 14*cos(x - z) + 106 ... 14*cos(y - z))*(9*sin(2*y) + 12*sin(y + z) + 10*cos(x - y) + 2*cos(y - 107 ... z) + 18)).expand(trig=True).expand() 108 109In the expanded state, there are nearly 1000 trig functions: 110 111 >>> L(expr) 112 932 113 114If the expression where factored first, this would take time but the 115resulting expression would be transformed very quickly: 116 117 >>> def clock(f, n=2): 118 ... t=time(); f(); return round(time()-t, n) 119 ... 120 >>> clock(lambda: factor(expr)) # doctest: +SKIP 121 0.86 122 >>> clock(lambda: TR10i(expr), 3) # doctest: +SKIP 123 0.016 124 125If the unexpanded expression is used, the transformation takes longer but 126not as long as it took to factor it and then transform it: 127 128 >>> clock(lambda: TR10i(expr), 2) # doctest: +SKIP 129 0.28 130 131So neither expansion nor factoring is used in ``TR10i``: if the 132expression is already factored (or partially factored) then expansion 133with ``trig=True`` would destroy what is already known and take 134longer; if the expression is expanded, factoring may take longer than 135simply applying the transformation itself. 136 137Although the algorithms should be canonical, always giving the same 138result, they may not yield the best result. This, in general, is 139the nature of simplification where searching all possible transformation 140paths is very expensive. Here is a simple example. There are 6 terms 141in the following sum: 142 143 >>> expr = (sin(x)**2*cos(y)*cos(z) + sin(x)*sin(y)*cos(x)*cos(z) + 144 ... sin(x)*sin(z)*cos(x)*cos(y) + sin(y)*sin(z)*cos(x)**2 + sin(y)*sin(z) + 145 ... cos(y)*cos(z)) 146 >>> args = expr.args 147 148Serendipitously, fu gives the best result: 149 150 >>> fu(expr) 151 3*cos(y - z)/2 - cos(2*x + y + z)/2 152 153But if different terms were combined, a less-optimal result might be 154obtained, requiring some additional work to get better simplification, 155but still less than optimal. The following shows an alternative form 156of ``expr`` that resists optimal simplification once a given step 157is taken since it leads to a dead end: 158 159 >>> TR9(-cos(x)**2*cos(y + z) + 3*cos(y - z)/2 + 160 ... cos(y + z)/2 + cos(-2*x + y + z)/4 - cos(2*x + y + z)/4) 161 sin(2*x)*sin(y + z)/2 - cos(x)**2*cos(y + z) + 3*cos(y - z)/2 + cos(y + z)/2 162 163Here is a smaller expression that exhibits the same behavior: 164 165 >>> a = sin(x)*sin(z)*cos(x)*cos(y) + sin(x)*sin(y)*cos(x)*cos(z) 166 >>> TR10i(a) 167 sin(x)*sin(y + z)*cos(x) 168 >>> newa = _ 169 >>> TR10i(expr - a) # this combines two more of the remaining terms 170 sin(x)**2*cos(y)*cos(z) + sin(y)*sin(z)*cos(x)**2 + cos(y - z) 171 >>> TR10i(_ + newa) == _ + newa # but now there is no more simplification 172 True 173 174Without getting lucky or trying all possible pairings of arguments, the 175final result may be less than optimal and impossible to find without 176better heuristics or brute force trial of all possibilities. 177 178Rules 179===== 180 181.. autofunction:: TR0 182 183.. autofunction:: TR1 184 185.. autofunction:: TR2 186 187.. autofunction:: TR2i 188 189.. autofunction:: TR3 190 191.. autofunction:: TR4 192 193.. autofunction:: TR5 194 195.. autofunction:: TR6 196 197.. autofunction:: TR7 198 199.. autofunction:: TR8 200 201.. autofunction:: TR9 202 203.. autofunction:: TR10 204 205.. autofunction:: TR10i 206 207.. autofunction:: TR11 208 209.. autofunction:: TR12 210 211.. autofunction:: TR12i 212 213.. autofunction:: TR13 214 215.. autofunction:: TRmorrie 216 217.. autofunction:: TR14 218 219.. autofunction:: TR15 220 221.. autofunction:: TR16 222 223.. autofunction:: TR111 224 225.. autofunction:: TR22 226 227.. autofunction:: TRpower 228 229.. autofunction:: fu 230 231Notes 232===== 233 234This work was started by Dimitar Vlahovski at the Technological School 235"Electronic systems" (30.11.2011). 236 237Beyond TR13, other rules are not from the original paper, but extended 238in SymPy. 239 240References 241========== 242 243.. [1] Fu, Hongguang, Xiuqin Zhong, and Zhenbing Zeng. 244 "Automated and readable simplification of trigonometric expressions." 245 Mathematical and computer modelling 44.11 (2006): 1169-1177. 246 http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.657.2478&rep=rep1&type=pdf 247 248.. [2] A formula sheet for trigonometric functions. 249 http://www.sosmath.com/trig/Trig5/trig5/pdf/pdf.html 250