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? 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.
