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. > > 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 --~--~---------~--~----~------------~-------~--~----~ 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/ -~----------~----~----~----~------~----~------~--~---
