Re: Simplify X * C1 == C2 with undefined overflow

[Marc Glisse <marc.glisse@inria.fr>]

On Fri, 7 Aug 2020, Jakub Jelinek wrote:

> On Fri, Aug 07, 2020 at 10:57:54PM +0200, Marc Glisse wrote:
>> On Fri, 7 Aug 2020, Joern Wolfgang Rennecke wrote:
>>
>>>
>>> On 07/08/20 19:21, Marc Glisse wrote:
>>>>
>>>> If we are going to handle the wrapping case, we shouldn't limit to
>>>> the non-wrapping meaning of multiplicity. 3*X==5 should become
>>>> X==1431655767 (for a 32 bit type), etc.
>>>>
>>>> Do we have an extended gcd somewhere in gcc, to help compute 1431655767?
>>> I don't quite see yet how this relates to gcd,
>>
>> https://en.wikipedia.org/wiki/Extended_Euclidean_algorithm is the most
>> common way to compute the modular multiplicative inverse of a number. For 3
>> and 2^32, it could tell us that 2863311531*3-2*2^32=1, so modulo 2^32
>> 2863311531*3==1, and 3*X==5 is the same as 2863311531*3*X==2863311531*5,
>> i.e. X==1431655767.
>
> wi::gcd ?

That's the first place I looked, but this is only the regular Euclid 
algorithm, not the extended one. It tells you what the gcd is, but does 
not give you the coefficients of the Bézout identity. For 3 and 2^32, it 
would tell me the gcd is 1, while I want the number 2863311531 (inverse of 
3).

Ah, found it, there is mod_inv hidden in expr.c!

-- 
Marc Glisse