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