Modulus by constant

[Waldek Hebisch]

Richard Kenner wrote:
>Does anybody understand the code that Torbjorn wrote to do divides and modulus
>operations as multiplies?
>
>Consider the following:
>
>unsigned short r2286 () { return 2286;}
>
>int
>main ()
>{
>  unsigned short x = r2286 () % 255;
>
>  printf ("x = %d\n", x);
>}
>
>(The first line should be in a different file to avoid inlining.)
>
>This should print 246.  But, at least on x86-64, it prints a different value.
>This is the cause of least one Ada ACATS failure.

In short: division is equivalet to multiplication by true (fractional)
inverse. One can replace inverse by fixed point approximation. Crucial
point is to have error bounded by 1. (It has nothing to do with modular
inverse.) 

AFAKIS the program above runs (on x86_64) fine with 3.3 using multipler
32897 and fail with 3.5 using multipler -32639. Since 32897 = -32639
mod 2**16 I think that multipler just got truncated -- note that for
correctnes multiplication has to be done with double precision, and
multiplier must have double precision (32 bits for 16 bit result).


-- 
                              Waldek Hebisch
hebisch@math.uni.wroc.pl