David Chase <chase@world.std.com> writes:

>Regarding whether the behavior of integer division and remainder
>should be specified or not, I thought I'd do a brief bit of
>research as to what the popular processors actually do:
>
>Sparc, does the Fortran rules.
>Intel x86, does the Fortran rules.
>PowerPC, does the Fortran rules.
>Motorola 680x0, does the Fortran rules.
>VAX, does the Fortran rules.
[...]
>Intel i860, has no integer division.
>HPPA 1.0, has only divide step.
>TERA, has an instruction for each way.
>ARM 810, seems to have no division instruction.
[...]
>MIPS, has a division instruction, but it's unclear
>      which one (they say "div" and "mod" but this
>      seems odd on a workstation chip).

Empirically, MIPS seems to use the Fortran rules (round towards zero),
at least for the cases I've tried.  So does the Alpha.

The good news is that this will almost certainly be addressed by C9X.

--
Fergus Henderson <fjh@cs.mu.oz.au>   |  "I have always known that the pursuit
WWW: <http://www.cs.mu.oz.au/~fjh>   |  of excellence is a lethal habit"
PGP: finger fjh@128.250.37.3         |     -- the last words of T. S. Garp.
---
[ 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                             ]

David Chase wrote:
>
> So, the costs of emulating round-to-zero are not that large.  I did a
> back of the envelope check for overflow problems, I think there are
> none (negative + positive cannot overflow; it's possible to change
> the sign of "x", but in that case the answer is zero anyway).  This does
> complicate remainder calculation on those machines which
>
>   a. do round-to-negative-infinity division and
>   b. have a single instruction producing both quotient and remainder.

Exactly. The remainder is the hard one to do, in the case where x<0 and
y>-x.

But this is also hard on machines that do round-to-zero division, and
what you want is round-to-minus-infinity. 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?

--

Ciao,
Paul

(Please send e-mail to mailto:pderocco@ix.netcom.com instead of the
return address, which has been altered to foil junk mail senders.)
---
[ comp.std.c++ is moderated.  To submit articles: Try just posting with your
                newsreader.  If that fails, use mailto:std-c++@ncar.ucar.edu
  comp.std.c++ FAQ: http://reality.sgi.com/austern/std-c++/faq.html
  Moderation policy: http://reality.sgi.com/austern/std-c++/policy.html
  Comments? mailto:std-c++-request@ncar.ucar.edu
]

Regarding whether the behavior of integer division and remainder
should be specified or not, I thought I'd do a brief bit of
research as to what the popular processors actually do:

Sparc, does the Fortran rules.
Intel x86, does the Fortran rules.
PowerPC, does the Fortran rules.
Motorola 680x0, does the Fortran rules.
VAX, does the Fortran rules.

Those were the machines with well-documented architectures,
and a division instruction.

Intel i860, has no integer division.
HPPA 1.0, has only divide step.
TERA, has an instruction for each way.
ARM 810, seems to have no division instruction.

Those machines are neutral on the subject -- either they
go either way, or division is expensive.  (The TERA is
"popular" because I have a description of their machine
handy.)

MIPS, has a division instruction, but it's unclear
      which one (they say "div" and "mod" but this
      seems odd on a workstation chip).
i960, has a division instruction, but they don't say which one.

Those two machines have ambiguous documentation, at least on
the net.  Tsk, tsk, tsk.  They have this operation that they call
"division" but don't get around to describing its behavior.

I couldn't quickly get information for the HPPA 2.0, or
for the AMD29k.  I got tired of looking before I got
around to the Alpha.

I suspect that rounding to zero is the usual case, because
of Fortran/tradition.

It would be nice, if the C++ committee cannot bring themselves
to settle on the Fortran choice, if they could at least list
which hardware does what, as of the completion date of the
standard.  It would also be nice if they could get a macro
defined (e.g., DIVIDE_ROUNDS_TO_NEGATIVE_INFINITY) so that
people could (perish the thought) write portable code that
used integer division.  Note that I chose a macro which if
left undefined (hence zero) would generate the correct result
on all the machines where I could find an answer.

Paul DeRocco is half-right, it is more than one or two
cycles, if the hardware implements round-to-negative
infinity and the language specifies round-to-zero.
However, it is not much more.

If the signs differ, then to get the quotient right,
the divisor, reduced in magnitude by one, must be added
to the dividend before the division.  This code might look
like:

  z = x RTZDIV y

  sz = x ^ y;                     // 1 instruction
  if (sz < 0) {                   // 1 instruction
     sy = y >> (BitsPerInt-1);    // 1 instruction
     x = x + y - 1 + sy + sy;     // 4 instructions (fast instructions)
  }
  z = x / y;

For the positive result case, this takes two extra cycles.
Otherwise, probably an additional three cycles, on a typical
superscalar chip, which would issue the instructions like this:

   sy = y >> constant ; t1 = x + y
   t1 = t1 - 1; t2 = sy + sy;
   x = t1 + t2

So, the costs of emulating round-to-zero are not that large.  I did a
back of the envelope check for overflow problems, I think there are
none (negative + positive cannot overflow; it's possible to change
the sign of "x", but in that case the answer is zero anyway).  This does
complicate remainder calculation on those machines which

  a. do round-to-negative-infinity division and
  b. have a single instruction producing both quotient and remainder.

I don't think there's any hardware out there like this, so I don't think
that is a problem (the i960 is one possibility, it has a divide instruction
that does both, and a poorly documented instruction set).

My point in all of this is that I think that the value of the C++ standard
is being reduced; I think people care more about portability from platform
to platform, than they do about portability from C-to-C++, especially when
the C-to-C++ portability (for a given program) is only confined to a single
machine.  Furthermore,  I think that in most cases (again, everywhere that
I've looked and gotten a definitive answer) the code follows the Fortran
rules.  All PCs, all Macintoshes, all Sun workstations (probably all
workstations, period, because of the Fortran influence).  To an engineering
approximation, all desktop machines do division the Fortran way.  Why not
make life a little easier for programmers and guarantee that what is
usually true by accident, is in fact the way that the language is supposed
to work?  I realize that there's embedded processors out there that I don't
know much about, but I haven't heard of even one that implements division
and uses round-to-negative-infinity.

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                             ]