New subject: signed integer division

15 Jan 2003

      Excellent documentation material for `/ and `%, Niels; thanks. I'm
taking the liberty of incorporating parts of that discussion to the
refdocs.
/ Johan Sundström (a hugging punishment!)
Previous text:
...
2003-01-15 11:41:
Subject: Re: signed integer division

Rene van Rueschen rueschi@berit-broese.de writes:
...
There is a big difference between C/Pascal/LPC and Pike in signed integer division:
In Pike, results are rounded down, while in all other languages the results are
rounded towards 0.
This behaviour was argued about and decided several years ago. As I
was one of those who argued strongly for the current behaviour, I
should perhaps explain why I prefer that:

It means that a % b always have the same sign as b (typically b
is positive (array size, rsa modulo, etc), and a varies a lot
more than b.

That means that the function f(x) = x % n behaves in a sane way,
as x increases, f(x) cycles through the values 0,1, ..., n-1, 0,
.... Nothing strange happens when you cross zero.

Furthermore, the function f(x) = x/n behaves in a sane way. When
you increase x, f(x) will jump one step for each n:th increment.
For all x, (x + n) / n = x/n + 1. Zero is not special.

The % operator implements the binary "mod" operation, as defined
by our god Donald Knuth (see the Art of Computer Programming,
1.2.4) [1].

...
(Results of the modulo operation are 'correct' referring to this
unusual rounding style.)
It's important that / and % are compatible, so that a = b*(a/b) + a%b
for alla and b.
Also note the recent 15-20 years of history of the % operations.
Traditionally in C (i.e. at least up c89 ANSI C), the rounding
behaviour of % for negative numbers was left as implementation
defined. If there was a machine code instruction for division, C
typically did whatever the machine code did.
It's unfortunate to have a basic operation like % not well defined.
When the Pike developers were annoyed about it, the question was
argued and in the end Pike chose the, in my opinion, sanest convention
for how it ought to work. Then java came a long, and choose the
round-towards-zero convention, which in my opinion is brain damaged.
I'm not sure what c99 says, perhaps it specifies the same behaviour as
java.
Anyway, as you compare to C, you should be aware that a portable
programs can't make any assumptions about the rounding conventions of
%, it's all up to the compiler implementation (at least if you don't
require a c99 compiler). So any C program that depends on that %
behaviour is *broken*. I guess the same is true for LPC, at least
older versions of Pike and ulpc used to inherit the %-behaviour from
the C compiler that was used for compiling it, which in turn inherited
it from the corresponding machine code instruction.
...
This strange behavour makes it extremly difficult to port algorithms
written in other languages to Pike.
Can you give some examples of the extreme difficulties?
/Niels
[1] Ok, Knuth's definition also says that x mod 0 = 0 for all x.
   That's not true for Pike's %; it treats %-by-0 as an error. But
   that's really a border case.
/ Brevbäraren

Re: signed integer division

greetings, martin.