Hi John, Despite having looked into the problem of computing gcd's efficiently, I don't know which algorithms are in practice faster for checking squarefreeness. In fact, to date, I am unable to tell you which algorithm is even asymptotically fastest for computing polynomial gcd. For integer gcd it is the half-gcd algorithm, though other algorithms are probably more practical to implement. I've only just now realised this may not be the case for polynomial gcds!
With regards to your problem, another way of checking that a polynomial is squarefree is to check res(f,f')!=0. The resultant can be computed a number of ways, as can a gcd. In practice, for both problems, modular methods seem to be preferred, however the asymptotically/practically fastest methods may or may not be modular. In the case of the resultant, one can use the sub-resultant algorithm, and some computer algebra systems in fact use this for shorter length polynomials, reserving the modular method for longer polynomials. Both methods control the coefficient size of intermediate coefficients. The thing is, in terms of efficient implementation, the resultant and gcd algorithms offered by NTL are probably the best available (I haven't timed these, but I'm going on what I know in general about the implementations out there) and apparently SAGE already uses the modular implementation in NTL for this problem. Likely that is the best you can do for now. If your polynomials are not long, you could try using the resultant computation in Pari which probably uses the subresultant algorithm. However nothing in Pari is optimised for long polynomials. I'd be fairly sure Magma is even better than NTL or Pari for short and long polynomials (since I read that somewhere). But the FLINT project will soon (weeks not years) be working on beating this. Our fast polynomial division algorithms should enable us to beat both Magma and NTL, often by a very significant factor, for this problem. It's likely to be quite a while before we have the modular methods implemented, but certainly we'll have the subresultant and a continued fraction implementation before too long. A slight saving can also be made by not actually computing the full resultant/gcd if it is not zero/one, but existing packages don't seem to implement this. If your algorithm can somehow stand a wrong answer to the gcd problem say every 1 in 2^80 gcd's then NTL implements a probabilistic algorithm which should be faster. I don't know your algorithm, so I can't comment on whether you can guarantee a correct result if the gcd computation happens to return the incorrect answer. Bill. --~--~---------~--~----~------------~-------~--~----~ 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/ -~----------~----~----~----~------~----~------~--~---
