On Monday 18 August 2008 11:44:11 am Bill Hart wrote: > Assuming FLINT is in fact being used for the GCD in Z[x], the > implementation is only "fast" up to degree about 250. It depends on > your definition of fast though. :-) In a later release of FLINT, GCD > will be asymptotically faster, and certainly by degree 1000 will be > many times faster than it currently is.
By "fast", I meant faster than my naive implementation of the sqrt. The ZZ gcd certainly seems fast enough for any problem I'm likely to have in the next 6 months :). The sage I'm using (3.0.6) is using the flint fmpz_poly_gcd. > If I'm not mistaken, the linear algebra method is nearly cubic > complexity. The GCD method should be subquadratic (though only just). > The method using power series has the same complexity as Karatsuba > multiplication of polynomials, in terms of ring operations (see papers > of Paul Zimmermann), and the constant can be made very low by use of > the recursive middle product algorithm. My algorithm is most definitely quadratic (as I had already thought from the simple nested for-loops). Doubling the degree produces a nearly perfect quadrupling of run-time. Note that it isn't a linear system of the coefficients and the solution is so obvious that it's easy to find one unknown at a time. I'm not sure what you are calling the "power series method" -- I wonder if it may be what I'm doing. > Note that if one requires the square root of an exact square of > polynomials, if one uses the power series method, one only needs to > work to a precision about half the length of the original polynomial > since that is how large the square root will be. I think so anyway, > unless I'm missing something silly here (altogether likely). That makes sense. If you know that you have a perfect square you only need to think about half the coefficients of the square input. Of course, if you want to raise an error when something is not a perfect square, you'll need to test all the coefficients by comparing with the square of your tentative square root. -- Joel --~--~---------~--~----~------------~-------~--~----~ 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/sage-devel URLs: http://www.sagemath.org -~----------~----~----~----~------~----~------~--~---
