Re: mini-gmp mpz_gcdext Bézout coefficients do not match documentation

marco.bodrato at tutanota.com marco.bodrato at tutanota.com
Sun Feb 18 11:37:22 CET 2024


Ciao Niels,

18 feb 2024, 10:10 da nisse at lysator.liu.se:

> marco.bodrato at tutanota.com writes:
>
>> What about;
>>
>>
>> /* Arrange so that |s| < |u| / 2g */
>>   mpz_add (s1, s0, s1);
>>   {
>>     int cmp = mpz_cmpabs (s0, s1);
>>     if (cmp >= 0)
>>       {
>>         mpz_swap (s0, s1);
>>         mpz_sub (t1, t0, t1);
>>         if (cmp != 0 || mpz_cmpabs (t0, t1) > 0)
>>           mpz_swap (t0, t1);
>>       }
>>   }
>>
>
> I think swapping of s and t must go together? I've tried out this
> similar variant 
>

You are right, it's better with the two swaps together.


>  mpz_add (s1, s0, s1);
>  mpz_sub (t1, t0, t1);
>  cmp = mpz_cmpabs (s0, s1);
>  if (cmp > 0 || (cmp == 0 && mpz_cmpabs (t0, t1) > 0))
>  {
>  mpz_swap (s0, s1);
>  mpz_swap (t0, t1);
>  }
>

The only reason why I prefer my solution is: when cmp<0, there is no need to compute
mpz_sub (t1, t0, t1);


> Seems to work fine, and it's a rather clear way to express the "lexical"
> preference that we want the cofactor pair with the smallest of |s|, |s'|, but
> in case of a tie, we choose the pair with smallest |t|, |t'|.
>

I agree.

Ĝis,
m


More information about the gmp-bugs mailing list