On Dec 15, 2007 12:35 PM, Joel B. Mohler <[EMAIL PROTECTED]> wrote: > > On Sat, Dec 15, 2007 at 11:12:12AM -0800, William Stein wrote: > > On Dec 15, 2007 7:19 AM, Joel B. Mohler <[EMAIL PROTECTED]> wrote: > > > Hmm, this is interesting. Singular may be frightening for factoring with > > > some > > > big bad examples, but it seems we've got some work to do for the small > > > cases. > > > sage: R.<y,z>=QQ[] # singular > > > sage: r=y^37-1 > > > sage: timeit r.factor() > > > 1000 loops, best of 3: 1.04 ms per loop > > > sage: S.<x>=ZZ[] # NTL, but the factoring code converts to pari. > > > sage: s=x^37-1 > > > sage: timeit s.factor() > > > 100 loops, best of 3: 5.2 ms per loop > > > The moral might be: conversions are costly (but we already knew that). > > > > Note that NTL does implement factoring in ZZ[] and moreover it does > > so asymptotically *very* quickly. It's only for small degree where I > > once noticed pari being faster and made that the default -- and maybe > > that had to do with bad turning when building NTL! So you might > > want to consider wrapping ZZ[] factoring via NTL, which I'm sure you > > can easily do since you led the charge for rewraping all of NTL! > > Yeah, I thought about doing that and started looking at ZZX factor stuff. Is > there an arbitrary factoring function? All I could find is factoring for > special cases (square-free, etc) and I was too lazy to try and figure out > what I > was supposed to do. I'll be looking into this further.
Factoring in ZZ[x] in more extreme cases is perhaps the *main* problem that NTL was designed for. See http://www.shoup.net/ntl/doc/tour-time.html for a bunch of timings. Also, the section of the ntl tutorial on polynomials starts with a factoring example: http://www.shoup.net/ntl/doc/tour-ex3.html > > > So far, my mpoly over ZZ factoring code reduces to a univariate and > > > factors > > > that. Profiling indicates that the univariate factoring is a significant > > > hunk of my time -- I guess that means my all-python book-keeping is > > > respectable. Oh, and my kroneckers trick algorithm for my special case > > > absolutely clobbers singular, but I don't think that is really a great > > > shock. > > > > Nice! How does it compare to Maple and Magma and Reduce? > > Note too good yet. And, actually singular beats me for simpler polynomials -- > it's just my bizarre polynomials that singular can't handle that I beat > singular > with. > > I'm sure a cython-ing would help it out since there's a non-trivial amount of > book-keeping with the exponents. However, I can't believe that this simple > trick is the best we can do with mpoly factoring. I think it may turn out to > be > a nice thing to have around for special cases though. > > > -- > Joel > > > > -- William Stein Associate Professor of Mathematics University of Washington http://wstein.org --~--~---------~--~----~------------~-------~--~----~ 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/ -~----------~----~----~----~------~----~------~--~---
