Hi, On 11 August 2011 16:53, Aaron Meurer <[email protected]> wrote:
> On Thu, Aug 11, 2011 at 8:47 AM, Mateusz Paprocki <[email protected]> > wrote: > > Hi, > > > > On 11 August 2011 16:41, Aaron Meurer <[email protected]> wrote: > >> > >> On Thu, Aug 11, 2011 at 8:31 AM, Mateusz Paprocki <[email protected]> > >> wrote: > >> > Hi, > >> > > >> > On 11 August 2011 16:24, Aaron Meurer <[email protected]> wrote: > >> >> > >> >> Indeed, I ran through it with a debugger, and one of the coefficients > >> >> was a rational number whose numerator had 3410 digits and denominator > >> >> had 3409 digits. And that was just a random number I looked at half > >> >> way through the execution; it could get much larger than that even. > >> >> So actually, the test does not "hang", it just takes a really long > >> >> time. > >> >> > >> >> By the way, the lex test finishes in a reasonable amount of time. > >> >> It's only the grlex test that is slow. And it's only the buchberger > >> >> version (f5b is very fast in any case). > >> >> > >> >> I never realized that Python longs are (apparently) asymptotically > >> >> slower than gmpy mpz. > >> > > >> > Look at this > >> > > >> > graph: > http://mattpap.github.com/masters-thesis/html/images/ground-factor-large.png > . > >> > This shows factorization times of (1234*x + 123*y + 12*x + 1)**n. This > >> > was > >> > done for integers, but in case of rationals (which are used in > >> > groebner()) > >> > the difference is even bigger. > >> > >> Ah, so it may not really be asymptotic. Perhaps gmpy just has a much > >> slower growth rate. It's really hard to judge the degree of a > >> polynomial from a graph. > > > > Well, it is asymptotic. GMP implements optimal or almost optimal > algorithms > > (currently known), whereas Python implements classical arithmetic. In the > > rational case it is even worse, because gcd() is implemented in pure > Python > > (that's why PythonRationalType doesn't improve the situation that much > over > > Fraction). > > > > Would something like http://en.wikipedia.org/wiki/Binary_gcd improve > things? Or does that algorithm not work so well for long integers? > Read the section about "Efficiency". It doesn't seem to be a big improvement. Also I'm not sure if I didn't already try it in SymPy (without great success). Note that function calls are very expensive in Python, so often it happens that a weaker algorithm is fast because it's simple, contrary to some other superior (in the theory) algorithm that requires a lot of logic in pure Python. > > Aaron Meurer > > >> > >> Aaron Meurer > >> > >> > > >> >> > >> >> Aaron Meurer > >> >> > >> >> On Thu, Aug 11, 2011 at 7:53 AM, Mateusz Paprocki <[email protected] > > > >> >> wrote: > >> >> > Hi, > >> >> > > >> >> > On 11 August 2011 15:49, Aaron Meurer <[email protected]> wrote: > >> >> >> > >> >> >> Skipping the test is a good workaround, but this should be > >> >> >> investigated. Python ground types should not be that much slower > >> >> >> than > >> >> >> gmpy. I suspect there is a bug in PythonIntegerType or > >> >> >> PythonRationalType. > >> >> > > >> >> > Coefficients in this test can have 60 digits and more, so it's > quite > >> >> > understandable why this test hangs under Python ground types. > >> >> > Skipping > >> >> > is > >> >> > fine for now, but really this should be a conditional tests, i.e. > do > >> >> > it > >> >> > if > >> >> > gmpy is available and otherwise skip. > >> >> > > >> >> >> > >> >> >> Aaron Meurer > >> >> >> > >> >> >> On Thu, Aug 11, 2011 at 7:40 AM, Tomo Lazovich > >> >> >> <[email protected]> > >> >> >> wrote: > >> >> >> > For the record, I am also seeing this hanging in OS X (no gmpy > >> >> >> > either). > >> >> >> > > >> >> >> > On Thu, Aug 11, 2011 at 7:37 AM, Jeremias Yehdegho > >> >> >> > <[email protected]> > >> >> >> > wrote: > >> >> >> >> > >> >> >> >> On 08/11/2011 01:55 PM, smichr wrote: > >> >> >> >> > groebnertools appears to hang starting with commit > >> >> >> >> > >> >> >> >> Thank you, fix: https://github.com/sympy/sympy/pull/539 > >> >> >> >> > >> >> >> >> I think the problem was test_czichowski, which takes too long > >> >> >> >> without > >> >> >> >> gmpy (at least on my computer, now that I tried it without > gmpy). > >> >> >> >> Sorry. > >> >> >> >> > >> >> >> >> Kind Regards, > >> >> >> >> Jeremias > >> >> >> >> > >> >> >> >> -- > >> >> >> >> 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. > >> >> >> > > >> >> >> > >> >> >> -- > >> >> >> 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. > >> >> > > >> >> > >> >> -- > >> >> 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. > >> > > >> > >> -- > >> 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. > > > > -- > 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.
