On Thursday 20 December 2007 10:56, Bill Hart wrote: > Does SAGE use the GP interpreter or the Pari library to do this > computation? If it is using the Pari library, and the data conversion > isn't quadratic time, then I don't think this should be a problem.
The library and I think the conversion is done correctly. It's a bit of convoluted path in the sage code to get in this specific case though so there might be other silly issues. > The other thing is, you are factoring a single random polynomial, > which may be irreducible. Factoring generic polynomials may be much > faster, since one only needs to know it is irreducible and then one > need not do any factoring. I will prepare a graph comparing the time > to factor generic polynomials, though I don't in general think that is > such a great benchmark, unless one specifically wants to tune for that > situation (which could be a nice idea if one had a certain flag that > could be set to indicate that one expected the polynomials being > factored to be vaguely generic). My observation is that random polynomials are almost always irreducible. This fact seems in startling contrast to the case for integers! For instance: sage: R.<x>=ZZ[] sage: R.random_element(6,-2^23,2^23).factor() # virtually always 1 factor I've actually been doing tests of 3 different cases (not all of which made it to the mailing list). 1) product of a bunch of small factors 2) product of 2 medium factors 3) random (irreducible by comments above) NTL seems to gain a bit relative to pari when there are non-trivial factors, but it doesn't seem too significant. It's main influence in my cutoff points has been to let NTL factor small polys out to degree 30 rather than degree 10. But both are so competitive for degree 10-20 that it's not that big of a deal. -- Joel --~--~---------~--~----~------------~-------~--~----~ To post to this group, send email to sage-devel@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/sage-devel URLs: http://sage.scipy.org/sage/ and http://modular.math.washington.edu/sage/ -~----------~----~----~----~------~----~------~--~---
