Re: [flint-devel] Heuristic gcd

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

Hmm, I think I have gotten ahead of myself with my argument about the
Mignotte bound.

If f(x) = a(x)*b(x) and g(x) = a(x)*d(x) with b(x) and d(x) coprime.

when I substitute x = 2^64 then certainly a(2^64) will be a common
factor of f(2^64) and g(2^64).

But it is also possible that even though b(x) and d(x) are coprime
that b(2^64) and d(2^64) are not.

But this means that we can't simply rely on the Mignotte bound for the
size of the gcd of f(x) and g(x). Certainly if 2^64 is bigger than the
Mignotte bound times the gcd of b(2^64) and d(2^64) then we are ok.
The polynomial gcd that we are after will just end up being multiplied
by some integer constant which we can remove by computing the content.

But there is no way that I can see to bound gcd of b(2^64) and d(2^64).

Thus it seems essential to me that one actually check that the
purported poly gcd actually divides f(x) and g(x).

But the time it takes to do this "divides" test is too great. I don't
have a solution to this problem at present.

Bill.

2008/11/9 Bill Hart <goo...@go...>:
> I coded up the packing code to pack into 32 bits instead of 64. There
> were a couple of problems with this. When the Mignotte bound is bigger
> than 32 bits then a divides gets carried out, which for small gcd's
> dominates the time. Thus sometimes it is better to pack into 64 bits
> instead.
>
> Once that is sorted out one soon realises that just computing the
> Mignotte bound takes too long. So I implemented an approximation which
> is sometimes slightly too large but isn't too bad.
>
> Once these issues are fixed, here is the result:
>
> http://sage.math.washington.edu/home/wbhart/flint-trunk/graphing/gcd11.png
>
> Now the brown in the bottom left must be where packing is done to the
> bit. Here the Minotte bound is usually less than the number of bits
> that one is packing to.
>
> Bill.
>
> 2008/11/8 Bill Hart <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
>>>
>>
>