[Camllist] Integer arithmetic: mod
[
Home
]
[ Index:
by date

by threads
]
[ Message by date: previous  next ] [ Message in thread: previous  next ] [ Thread: previous  next ]
[ Message by date: previous  next ] [ Message in thread: previous  next ] [ Thread: previous  next ]
Date:  20010806 (09:10) 
From:  Xavier Leroy <Xavier.Leroy@i...> 
Subject:  Re: [Camllist] Integer arithmetic: mod 
> I have a question regarding the 'mod' operator in OCaml. While playing > around with the toplevel, I found that > > 1 mod 10 = 1 instead of 1 mod 10 = 9. > > Looking into the Handbook showed me, that the behaviour of 'mod' is > platform dependent for negative arguments. > Now, I could live with 1 mod 10 = 1, but why is it platformdependent? That's a classic "gotcha" of computer arithmetic. There are three natural properties that should hold for / and mod, namely: (a) (x) / y = x / (y) =  (x / y) (b) (x / y) * y + x mod y = x (c) 0 <= x mod y < y if y > 0 however it's impossible to satisfy all three simultaneously! Euclidean division satisfies (b) and (c), but most hardware platforms satisfy (a) and (b). C leaves the behavior of / and mod unspecified for negative arguments, and since the bytecode interpreter maps / and mod directly to the C / and % operators, Caml "inherits" the unspecified behavior from C. > As far as I can see it would be better to specify a certain behaviour > and emulate it on platforms, where it is not directly supported by the > cpu, especially for a highlevel language as OCaml. That's a reasonable argument. The counterargument is that *if* the hardware doesn't implement the specified behavior *and* you really care for speed *and* you know that you always pass positive arguments to / and mod, *then* you're paying an unnecessary overhead. But that's a very weak argument, because all platforms I've seen in the last 10 years implement "round toward zero" division, i.e. guarantee (a) and (b). So, specifying it wouldn't cost much. Marcin Kowalczyk adds: > In C89 the behavior for negative numbers was left > implementationdefined but in C99 it is specified as truncation > towards 0. Interesting information. > Haskell has both: div & mod truncate downwards, quot & rem truncate > towards 0. So does Ada, I think. It's probably a good idea to have two sets of operators, and document that one of them (those that truncate downwards) is a bit less efficient. John Gerard Malecki adds: > Does anyone know if the hardware implementation of integer division > and/or remainder is faster because the returned value from remainder > is sometimes negative? Maybe its slower but everyone does it the same > way for backwards compatibility? I believe it doesn't make much of a speed difference for a hardware implementation (just a few extra gates to handle the signs :), so the hardware designers just implement what everyone else previously implemented, i.e. truncation towards 0. It's actually the right choice given that Java and C99 require this behavior. > One reason for the hardware remainder to be positive is that it allows > for easier compiler optimizations. If the remainder is always > positive then the following transformations are always available: > > M / (2**N) == M asr N > M mod (2**N) == M land (2**N1) Correct. C compilers can still implement these transformations for unsigned integers. For signed integers, gcc and ocamlopt implement some funny tricks such as M / 2^N = (if M >= 0 then M else M + 2^N1) asr N M mod 2^N = M  ((if M >= 0 then M else M + 2^N1) land (2^N)) just to get a consistent behavior with the hardware "mod" instruction!  Xavier Leroy  Bug reports: http://caml.inria.fr/bin/camlbugs FAQ: http://caml.inria.fr/FAQ/ To unsubscribe, mail camllistrequest@inria.fr Archives: http://caml.inria.fr