Re: [flint-devel] Heuristic gcd

[William H. <ha...@ya...>]

I decided to remove the test for correctness in the Heuristic GCD (which it actually can't do without) and see if that sped things up. It did:

http://sage.math.washington.edu/home/wbhart/flint-trunk/graphing/gcd10.png

The red on the bottom left turned blue. So it looks like it is the function fmpz_poly_divides which checks if the purported GCD actually divides the original polynomials is taking most of the time (like 80%).

One way of doing a quick check is to pack the coefficients of the polynomials into large integers and divide. If the integer divides exactly one gets the quotient, which one can unpack into a polynomial and then if that quotient times the divisor is the dividend, one can prove that the polynomials divide exactly.

Clearly the brown at the bottom of the graph on the left is because Magma is packing (both in the GCD and the divides function) into 32 bits instead of 64.

So I think it is clear now what has to be implemented. 

I'm quite surprised that the fmpz_poly_divides_modular function was not sufficiently fast. It seems one can do a lot better if exact division is expected.

Bill.

--- On Fri, 11/7/08, Bill Hart <goo...@go...> wrote:

> From: Bill Hart <goo...@go...>
> Subject: [flint-devel] Heuristic gcd
> To: "Development list for FLINT" <fli...@li...>
> Date: Friday, November 7, 2008, 2:07 PM
> I implemented the heuristic gcd for polynomials whose
> bitsize is up to
> 63 bits. The result looks like this:
> 
> http://sage.math.washington.edu/home/wbhart/flint-trunk/graphing/gcd9.png
> 
> Interestingly although it makes the bottom of the graph
> nice and blue,
> the big red patch on the left is still there.
> 
> I think perhaps this is just a highly efficient euclidean
> algorithm,
> or perhaps a Lehmer GCD algorithm.
> 
> The red on the right is nor due to FLINT. That is due to a
> lack of
> integer half-gcd in GMP. We're still working on fixing
> that.
> 
> Bill.
> 
> -------------------------------------------------------------------------
> This SF.Net email is sponsored by the Moblin Your Move
> Developer's challenge
> Build the coolest Linux based applications with Moblin SDK
> & win great prizes
> Grand prize is a trip for two to an Open Source event
> anywhere in the world
> http://moblin-contest.org/redirect.php?banner_id=100&url=/
> _______________________________________________
> flint-devel mailing list
> fli...@li...
> https://lists.sourceforge.net/lists/listinfo/flint-devel