Simplify X * C1 == C2 with undefined overflow

Joern Wolfgang Rennecke gnu@amylaar.uk
Fri Aug 7 21:58:43 GMT 2020


On 07/08/20 21:57, Marc Glisse wrote:
> On Fri, 7 Aug 2020, Joern Wolfgang Rennecke wrote:
>
>
>> 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
Ah, right.  I thought to decompose the variable factor into a 
non-overflowing and an overflowing part.
But now I see that the former will not always be found with a standard 
division.  Here we'd have to
consider:
3 by 7 is 1 rest -4 .. and then I get your result above.  But of course 
it's no longer an efficient algorithm
if I have to test lots of non-canonical division results.




More information about the Gcc-patches mailing list