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
Maybe the "b varies a lot more than b" statement in (1.) needs a litte clarification though. It doesn't make any sense to me.
/ Marcus Comstedt (ACROSS) (Hail Ilpalazzo!)
Previous text:
2003-01-15 13:44: Subject: Re: signed integer division
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!)
With some editing, of course (and it did read "a varies a lot more than b"). I interpreted it as "typically b is positive; array size, rsa modulo, etc, and a varies a lot more than b", which made sense to me.
/ Johan Sundström (a hugging punishment!)
Previous text:
2003-01-15 13:49: Subject: Re: signed integer division
Maybe the "b varies a lot more than b" statement in (1.) needs a litte clarification though. It doesn't make any sense to me.
/ Marcus Comstedt (ACROSS) (Hail Ilpalazzo!)
Well, perhaps it doesn't make sense ;-) But I'll give it a try:
I first wrote " a % n >= 0 for all a and n", because that's what I want. Then I realized that that's not true, it's negative if n < 0, but that's a case I don't care much about.
I think of the a % n operation as a way to implement arithmetic in Z_n, integers modulo n, were elements are represented uniquely as integers in the range 0, ..., n-1. There's no problem making sure that n is always positive. It's more important to handle negative a:s, because I'd like all of
(a + b) % n, (a - b) % n and (a*b) % n
to have values in the range 0 ... n-1. It's particularly important if the inputs a, b are in that same range, but the requirement that (a-c) % n >= 0 is enough to make the round-towards-zero convention look bad.
/ Niels Möller ()
Previous text:
2003-01-15 13:49: Subject: Re: signed integer division
Maybe the "b varies a lot more than b" statement in (1.) needs a litte clarification though. It doesn't make any sense to me.
/ Marcus Comstedt (ACROSS) (Hail Ilpalazzo!)
On Wed, Jan 15, 2003 at 01:45:03PM +0100, Johan Sundström (a hugging punishment!) @ Pike (-) developers forum wrote:
Excellent documentation material for `/ and `%, Niels; thanks. I'm taking the liberty of incorporating parts of that discussion to the refdocs.
not being a mathematician, could someone give some examples that demonstrate the braindamage of the rounding towards 0 way?
greetings, martin.
Hmm, I hope this is exported, or that Martin reads the lyskom conference.
Basically, I want (a + b*n) / n == a/n + b to hold. That means that the graph of the function f(x) = x/n should look something like
--- --- --- --- --- --------------------> x
A stair where all the steps are of the same shape. That is what you get if you always round downwards (or always upwards, but that's not an option). With round towards zero, you get one special step in the middle, like
--- --- ------ --- ---
Further properties that I'd like to hold are
a == b*(a/b) + a % b
(this one is actually guaranteed by c89 ANSI-C, I think), which is why the behaviour of % and / are interlinked.
And I want that, for n > 0, that a % n >= 0 for all n. That means that
arr[x % sizeof(arr)]
will never give you a range error (except if sizeof(arr) == 0), no matter how large or small x is.
/ Niels Möller ()
Previous text:
2003-01-15 14:45: Subject: Re: signed integer division
On Wed, Jan 15, 2003 at 01:45:03PM +0100, Johan Sundström (a hugging punishment!) @ Pike (-) developers forum wrote:
Excellent documentation material for `/ and `%, Niels; thanks. I'm taking the liberty of incorporating parts of that discussion to the refdocs.
not being a mathematician, could someone give some examples that demonstrate the braindamage of the rounding towards 0 way?
greetings, martin.
interested in doing pike programming, sTeam/caudium/pike/roxen training, sTeam/caudium/roxen and/or unix system administration anywhere in the world. -- pike programmer working in europe csl-gmbh.net open-steam.org (www.archlab|(www|db).hb2).tuwien.ac.at unix bahai.or.at iaeste.(tuwien.ac|or).at systemadministrator (stuts|black.linux-m68k).org is.(schon.org|root.at) Martin Bähr http://www.iaeste.or.at/~mbaehr/
/ Brevbäraren
On Wed, Jan 15, 2003 at 05:10:04PM +0100, Niels Möller () @ Pike (-) developers forum wrote:
Hmm, I hope this is exported, or that Martin reads the lyskom conference.
both, i am reading the conference via the exported list :-) i do understand the thing as far as math goes, what i am looking for is an example of a practical application that would break if you round towards 0.
greetings, martin.
class StupidHashTable { array(mixed) tab; int size;
static void create(int size) { this_program::size = size; tab = allocate(size); }
void insert(mixed x) { int hval; if (intp(x)) hval = x; else hval = hash(x); tab[hval % size] = x; } }
StupidHashTable(4)->insert(-17);
/ Henrik Grubbström (Lysator)
Previous text:
2003-01-15 17:51: Subject: Re: signed integer division
On Wed, Jan 15, 2003 at 05:10:04PM +0100, Niels Möller () @ Pike (-) developers forum wrote:
Hmm, I hope this is exported, or that Martin reads the lyskom conference.
both, i am reading the conference via the exported list :-) i do understand the thing as far as math goes, what i am looking for is an example of a practical application that would break if you round towards 0.
greetings, martin.
/ Brevbäraren
Weekdays are the typical example, imh:
-- cut -- #include <stdio.h>
int main() { int i; for (i=-10; i<=10; i++) printf("day %3d has weekday %d\n",i,i%7); return 0; } -- end cut --
day -10 has weekday -3 day -9 has weekday -2 day -8 has weekday -1 day -7 has weekday 0 day -6 has weekday -6 day -5 has weekday -5 day -4 has weekday -4 day -3 has weekday -3 day -2 has weekday -2 day -1 has weekday -1 day 0 has weekday 0 day 1 has weekday 1 day 2 has weekday 2 day 3 has weekday 3 day 4 has weekday 4 day 5 has weekday 5 day 6 has weekday 6 day 7 has weekday 0 day 8 has weekday 1 day 9 has weekday 2 day 10 has weekday 3
/ Mirar
Previous text:
2003-01-15 17:51: Subject: Re: signed integer division
On Wed, Jan 15, 2003 at 05:10:04PM +0100, Niels Möller () @ Pike (-) developers forum wrote:
Hmm, I hope this is exported, or that Martin reads the lyskom conference.
both, i am reading the conference via the exported list :-) i do understand the thing as far as math goes, what i am looking for is an example of a practical application that would break if you round towards 0.
greetings, martin.
/ Brevbäraren
pike-devel@lists.lysator.liu.se