Simplify X * C1 == C2 with undefined overflow

Marc Glisse marc.glisse@inria.fr
Fri Aug 7 20:57:54 GMT 2020


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.

> However, there are cases were the second division will not be possible 
> without rest.
> Consider : 7*X == 3
> 3/7 is 0 rest 3.
> 0x100000000 / 7 is 0x24924924 rest 4
> Since 3 cannot be represented as an integer multiple of -4, we can conclude 
> that the predicate
> is always false.

613566757*7-2^32==3

> Also: 14*X == 28
> has a non-zero power of two in the constant factor, so we have to factor out 
> the power of two
> (if the right hand side has a lower power of two, the predicate is always 
> false) and consider
> in modulo arithmetic with a number of bits less by the factored out power of 
> two, i.e. 31 bit here:
> 7*X == 14
> which is solved as above - but in 32 bit arithmetic - to
> X == 2
> and to convert back to 32 bit arithmetic, we get:
> X & 0x7fffffff == 2
> or
> 2*x == 4

Yes, we can reduce the size of the numbers a bit, but the gains won't be 
as nice for even numbers. I think the always-false case is already handled 
by CCP, tracking which bits can be 0 (I didn't check).

-- 
Marc Glisse


More information about the Gcc-patches mailing list