|
From: Bill H. <goo...@go...> - 2008-11-06 13:23:32
|
I plotted a new graph of FLINT fmpz_poly_gcd vs Magma. I'm using an older version of Magma, 2-13.5, and for lengths 2-16 Magma goes into an infinite loop for polynomials over a certain bit size. Hence there is a cutout in the graph to avoid this problem area. http://sage.math.washington.edu/home/wbhart/flint-trunk/graphing/gcd8.png The point of this graph is to see what happens a bit further out. On the right hand side, one can clearly see that Magma is not asymptotically faster, but simply a constant faster for small bit sizes. This is purely a caching effect to do with the way FLINT and Magma store polynomials. In fmpz_poly FLINT currently stores polynomials using a minimum of 2 limbs per coefficient (one sign/size limb and one data limb). Magma uses half a limb. In zmod_poly, FLINT currently uses a minimum of 1 limb per coefficient and does not pack multiple coefficients into a limb as Magma does. Probably it is the second issue that is really costing us here as about 4.5 of 5.5 seconds for a very large poly gcd is taken up by the hgcd algorithm in Z/pZ[x]. So we need to pack some limbs. I'm now going to concentrate on the big red region to the left. I think that is due to Magma's implementation of the heuristic gcd. If practical I will implement this algorithm. The red at the top of the first column is due to a bug in eMPIRe which prevents us from taking advantage of the new integer half gcd code written by Niels Moller. Jason Martin. myself and Brian Gladman are working on fixing that. This is not a FLINT issue. Bill. |