Hi, On Thu, Oct 21, 2010 at 02:52:35PM -0600, Aaron S. Meurer wrote: > > 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.
I'm not aware of any specialized algorithm for computing this. > > 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. > -- Mateusz
signature.asc
Description: This is a digitally signed message part
