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
