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.
