[ minimal C++ content, unless you are bored, or wish to
  file this one away for perverse C++ implementations
  on sensible machines. ]

Paul D. DeRocco wrote:

> But this is also hard on machines that do round-to-zero division, and
> what you want is round-to-minus-infinity.

This is true, but irrelevant to the discussion, because the C++ standard
will not settle on round-to-minus infinity for division, given that
every single machine that I know of that implements division, implements
round-to-zero -- if the standard specified anything, it would have to
specify that one.

> In cases where I'm dividing by
> a constant (fairly common), I'm in the habit of adding the largest
> multiple of the constant that won't overflow, doing an unsigned divide,
> and then subtracting that multiple. E.g., to take a 16-bit int modulo
> 10, I do (x+32760)/10-3276 and (x+32760)%10. But that fails for numbers
> in -32768..-32761. Any neat tricks for doing this in the general case
> where the divisor is a variable?

Hoo-boy.  Beats me.  For constants, I might try doing it in unsigned
arithmetic, with a correction (not that I have any confidence that
this will work; you can tell from the delay in replying that I don't
have a canned answer floating around in my head).

So, you've got a machine that does RTZ remainder, and you want the
round to negative infinity modulus.  For positive numbers, they agree.
For negative N, aren't they just backwards?  For instance, suppose
you are looking at arithmetic mod 10 (your example)?  The results
are:

  N   N rem 10  N mod 10
  0      0         0
 -1     -1         9
 -2     -2         8
 -3     -3         7
 ...
 -9     -9         1
 -10    -10        0

I think I would try this:

  int Remainder = Dividend % 10;
  int Sign = Remainder >> (bitsperword-1);
  int Konstant = 10 & Sign;
  Modulus = Remainder + Konstant;

I think this works in general.

I thought I had an answer for division, but it was clearly busted.
Starting from an example might not hurt:

 N   N rtz/ 3  N rtni/ 3
 4      1         1
 3      1         1
 2      0         0
 1      0         0
 0      0         0
-1      0         -1
-2      0         -1
-3     -1         -1
-4     -1         -2
-5     -1         -2
-6     -2         -2

The thing to note is that you cannot do the "obvious" trick of
subtracting the divisor-1 from the dividend (for opposite-sign
input) because you can get an overflow at the corner cases.

For positive divisor and negative dividend, if you
add 1 (the sign of the divisor) to the dividend, divide,
then subtract 1 (the sign of the divisor), it appears that
you will get the right answer, except if the dividend
is zero.  I worked this on paper, it holds in general:

  implementing z = x RTNIDIV y given RTZ division:

  if (x ^ y < 0 && x != 0) {
    t = y >> (bitsperword - 1);
    sign = t + t + 1;  // Could also do a ROL 2, AND 2, INC on Intel
    x = x + sign
    z = (x/y) - sign;
  } else {
    z = x/y;
  }

That's not wonderful, but division is relatively expensive.

David Chase
---
[ comp.std.c++ is moderated.  To submit articles: try just posting with      ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu         ]
[ FAQ:      http://reality.sgi.com/employees/austern_mti/std-c++/faq.html    ]
[ Policy:   http://reality.sgi.com/employees/austern_mti/std-c++/policy.html ]
[ Comments? mailto:std-c++-request@ncar.ucar.edu                             ]