On Oct 21, 2010, at 2:43 PM, Mateusz Paprocki wrote: > Hi, > > On Thu, Oct 21, 2010 at 02:26:18PM -0600, Aaron S. Meurer wrote: >> Whenever I worked on this a long time ago, I discovered that there is no one >> ordering that will work for all expressions (see the docstring of expand()). >> At that point in time, I was already digressing from my GSoC project for >> some time to work on it, so I decided to just make it the way it is now. >> >> I agree that it needs to be smarter. Maybe, if we move out the polynomial >> type expansion into having Poly to do the work, then the other hints (log, >> exp_base/power, trig, complex) will not conflict so much. >> > >> On the other hand, in some cases, it really could be considered ambiguous >> what "expand" means. For example, if you have log((x + 1)*(x - 1)), is the >> expanded form log(x + 1) + log(x - 1) or log(x**2 - 1). expand() right now >> will return either, depending on what order the hints are processed in. >> Perhaps really the best thing to do is to always try to use the specific >> expand functions (expand_log, expand_mul, etc.) in the code, based on what >> the expansion need is (Chris's hint manager should help with this). I think >> that the majority of the time, the polynomial type expansion is all that the >> algorithm really wants, because it wants to make sure that the expression is >> an Add if it can be. >> > > There is a good reason why e.g. Mathematica's Expand[] does only > polynomial expansion (over various domains) and there are other > functions for performing other types of expansion. When I first > added those `hints' to expand() I meant: > > expand(expr, something=True) -> something_expand(expr) > > but it went completely different direction to become something > I dislike in mathematical systems. I would like our expand() > does poly()'s job and nothing more and there should be other > *_expand() functions for particular tasks (they may use other > expansion functions, but the order of application of rewrite > functions must be deterministic and well defined).
Having worked with this long enough, I am inclined to agree. expand() is trying to be smart like simplify(), but purports to be more a decision type algorithm, like ratsimp(). > >> But again, for the polynomial type expansions, the ONLY correct fix for >> speed is to use Poly, because it can expand things like (x + 1)*(x + 2)**10 >> all at once (if I am not mistaken), and using much more efficient data >> structures. >> > > poly() applies a very simple rule: given h = f op g, to compute h, f and > g must be polynomials, thus if g = G**n then G**n is first transformed to > a polynomial form and then f op g is computed (both sides of 'op' must be > polynomials to proceed). > > In certain cases, expand() may be faster than poly(), e.g. (x + 1)**1000 > because expand() implements a specialized algorithm for this case (small > base and big exponent). poly() is tuned for bases of 'average' size. It > will be convenient to make polynomial exponentiation algorithms aware of > this specialized method. I see. Is there also a generalized algorithm for computing the coefficients for p1**n1*p2**n2*…*pm**nm? That would be the most efficient. Aaron Meurer > >> Aaron Meurer >> >> On Oct 21, 2010, at 11:52 AM, Øyvind Jensen wrote: >> >>> to., 21.10.2010 kl. 10.29 -0600, skrev Aaron S. Meurer: >>>> Well, that's not surprising. 99% of the time, when sympy hangs (but still >>>> finishes) it is hanging in expand(). This is a place where a slight >>>> machine difference can make a difference, too, because of the way expand >>>> works. Basically, it places all the expansion hints in a dictionary, and >>>> then executes them in whatever order it pops them out in a for loop (see >>>> sympy/core/expr.py, line 895). So if you have a slightly different order >>>> for expansion, it can easily make a difference. For example, consider >>>> >>>> (x + 1)*(x + 2)**10. >>>> >>>> If you first expand (x + 2)**10 using the expand_multinomial hint you get >>>> x + 1 times 11 terms. You then expand the (x + 1) around it using the >>>> expand_mul hint. >>>> >>>> But if you instead first expand using the expand_mul hint, you will get >>>> x*(x + 2)**10 + (x + 2)**10, and then when you apply the >>>> expand_multinomial hint, you have to expand the (x + 2)**10 part TWICE. >>>> (You will actually then have to run the expand_mul hint again to get the >>>> completely expanded expression). You can see how this can result in >>>> different execution times depending on the hint order. >>>> >>> >>> Shouldn't this be implemented in a more predictable way? Is it possible >>> to order the hints in an educated way based on the expression? If that >>> is difficult, wouldn't it be better to iterate through the hints in an >>> arbitrary, but consistent order? >>> >>> Øyvind >>> >>> -- >>> You received this message because you are subscribed to the Google Groups >>> "sympy" group. >>> To post to this group, send email to [email protected]. >>> To unsubscribe from this group, send email to >>> [email protected]. >>> For more options, visit this group at >>> http://groups.google.com/group/sympy?hl=en. >>> >> >> -- >> You received this message because you are subscribed to the Google Groups >> "sympy" group. >> To post to this group, send email to [email protected]. >> To unsubscribe from this group, send email to >> [email protected]. >> For more options, visit this group at >> http://groups.google.com/group/sympy?hl=en. >> > > -- > Mateusz > -- You received this message because you are subscribed to the Google Groups "sympy" group. To post to this group, send email to [email protected]. To unsubscribe from this group, send email to [email protected]. For more options, visit this group at http://groups.google.com/group/sympy?hl=en.
