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). > 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. > 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
signature.asc
Description: This is a digitally signed message part
