[flint-devel] Polynomial GCD

[Bill H. <goo...@go...>]

I think I figured out why my gcd code for Z[x] is still slow compared
with Magma, even with half-gcd implemented for Z/pZ[x].

I timed the gcd in Z/pZ[x] on its own and it is now faster than Magma.
So the problem is with the modular gcd algorithm in Z[x].

I did some profiling and it spends most of its time in checking by
division that the gcd actually divides both the input polynomials.

I'm pretty sure the reason this is so slow is because Magma uses a
modular algorithm for this division. It must compute the quotient
modulo a certain number of primes, until it stabilises. Then it
multiplies the quotient by the divisor to see if it equals the
dividend.

I guess if it is not equal then this doesn't prove anything. In that
situation one might be able to prove that it doesn't divide some other
way. However the generic case will of course be that it does divide,
since almost all the time the gcd algorithm gets things right when the
chinese remaindeing stabilises.

I'll have to code up this modular division in the next few days. That
should dramatically speed things up.

Bill.