Re: [flint-devel] Heuristic gcd

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

I finally realised that if the number of bits one is packing into is
bigger than the Mignotte bound, then one does not need to do a divides
test at all. This is all that Magma is doing.

Here is why:

To do a divides, if one is under the Mignotte bound, one would pack A
and B and pack the purported GCD and see if the packed A and B divide
the packed GCD. This would be done by simply doing a multiprecision
division and seeing if there is a remainder. If not, they divide
precisely and the quotient is calculated exactly.

But in computing the heuristic gcd, we already have the packed
versions of A and B, as the gcd of these divides both of them by
definition. But the packed version of G is precisely the gcd of the
packed version of A and B.

I've now inserted code to compute the Mignotte bound and omit the
divides test in this case. The function passes the test code and I am
now doing a profile run against Magma again:

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

The light blue layer at the bottom left is due to the fact that FLINT
packs into 64 bits not 30 or 32 as Magma surely does. This means that
we more easily exceed the Mignotte bound so that the divides test is
not required.

The browny red region at the bottom left is surely due to the fact
that Magma is doing a heuristic gcd packing into 32 bits (or perhaps
30) instead of 64.

Bill.

2008/11/7 William Hart <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
>
>
>
>
> -------------------------------------------------------------------------
> 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
>