RE: [Caml-list] Integer arithmetic: mod

RE: [Caml-list] Integer arithmetic: mod

[Dave Berry]

The Standard ML Basis Library also has both div/mod and rem/quot.  (This
was after some people complained that the original language definition
required the slower, Knuth-approved, behaviour).



-----Original Message-----
From: Marcin 'Qrczak' Kowalczyk [mailto:qrczak@knm.org.pl]
Sent: 04 August 2001 21:26
To: caml-list@inria.fr
Subject: Re: [Caml-list] Integer arithmetic: mod


Sat, 04 Aug 2001 11:48:07 -0700, Chris Hecker <checker@d6.com> pisze:

> Most computer languages (and chips) simply say "(a/b)*b + a mod b =
> a" and leave it at that.

Fortunately not all, e.g. in Python (-123) % 10 == 7. In C89 the
behavior for negative numbers was left implementation-defined but
in C99 it is specified as truncation towards 0.

> Unfortunately, people (and language and chip designers) assume
> (-4)/3 = -1 (truncate towards zero) rather than -2 (floor),

Not all people: Donald Knuth clearly disagrees. He has written
something along the lines "beware of programming languages which use
a different definition than the one which says (-4)/3 = -2".

Haskell has both: div & mod truncate downwards, quot & rem truncate
towards 0.

-- 
 __("<  Marcin Kowalczyk * qrczak@knm.org.pl http://qrczak.ids.net.pl/
 \__/
  ^^                      SYGNATURA ZASTĘPCZA
QRCZAK

-------------------
Bug reports: http://caml.inria.fr/bin/caml-bugs  FAQ:
http://caml.inria.fr/FAQ/
To unsubscribe, mail caml-list-request@inria.fr  Archives:
http://caml.inria.fr
-------------------
Bug reports: http://caml.inria.fr/bin/caml-bugs  FAQ: http://caml.inria.fr/FAQ/
To unsubscribe, mail caml-list-request@inria.fr  Archives: http://caml.inria.fr

Re: [Caml-list] Integer arithmetic: mod

[Krishnaswami, Neel]

Xavier Leroy [mailto:xavier.leroy@inria.fr] wrote:
> 
> I'm favorable to providing proper Euclidean division and modulus as
> library functions. The way I learned Euclidean division in college 
> is that the quotient q and the modulus r of a divided by b are 
> defined by
>
>       a = b * q + r  with 0 <= r < |b|
>
> Any mathematician on this list who could look it up in Bourbaki?

I haven't checked Bourbaki, but this is my understanding as well.

There's also a paper on the subject in the ACM TOPLAS from 1992. 
"The Euclidean definition of the functions div and mod", by Raymond 
Boute:

http://portal.acm.org/citation.cfm?id=128862&coll=portal&dl=ACM&CFID=745503&
CFTOKEN=75650609#FullText

--
Neel Krishnaswami
neelk@cswcasa.com
 
-------------------
Bug reports: http://caml.inria.fr/bin/caml-bugs  FAQ: http://caml.inria.fr/FAQ/
To unsubscribe, mail caml-list-request@inria.fr  Archives: http://caml.inria.fr

Re: [Caml-list] Integer arithmetic: mod

[Edmund GRIMLEY EVANS]

I'm responding to some old messages I found in the archive, and I'm
not subscribed, so please forgive the intrusion, but recently I've
been looking at how different languages define integer division and
remainder becaue I had to implement some compiler optimisations
involving those functions.

I strongly advise against leaving the meaning of any built-in or
library function or operator as implementation-defined. If you do this
you will get unportable programs and inefficient programs (because
people who want their programs to be portable will be forced to define
their own versions of the functions).

In my opinion and in most people's opinion, as far as I can tell, if
you're starting afresh, the best way to define integer division is as
rounding downwards. Integer remainder, to be consistent with this, has
the sign of the divisor. There are lots of arguments that support this
type of division, both mathematical and practical, and the only
arguments against it seem to involve compatibility: the other sort of
division is faster on some widely used hardware, is required by some
widely used programming languages and assumed by some existing
software.

A good way to keep everyone happy and make sure people don't get
caught out by their own assumptions is to provide both sorts. If you
do this, the best names to use are DIV and MOD for the good functions
(rounding downwards) and QUOT and REM for the legacy functions
(rounding towards 0). These are exactly the names used in Haskell and
ML and consistent with the names used in Ada, Prolog, Ruby and Scheme.
(I admit I'm not very sure about Prolog. If anyone has a copy of the
ISO standard, please check this for me.)

Here's a little table I made (I hope it doesn't contain too many
errors):

              BAD LEGACY!                     GOOD!
LANGUAGE  Division rounding towards 0     Division rounding downwards
          Remainder has sign of dividend  Remainder has sign of divisor
-----------------------------------------------------------------------
Ada           / rem                           mod
C89           div[quot/rem]
C9x           / % div[quot/rem]
Fortran 90    / MOD                           MODULO
Haskell       quot rem                        div mod
Java          / %
JVM           idiv irem
ML            quot rem                        div mod
Modula-2      div mod
Perl                                          %
Prolog        // rem                          mod
Python                                        / // %
Ruby          remainder                       / modulo divmod
Scheme        quotient remainder              modulo

Edmund

Keywords: negative integer division round truncate quotient remainder
number theory
-------------------
Bug reports: http://caml.inria.fr/bin/caml-bugs  FAQ: http://caml.inria.fr/FAQ/
To unsubscribe, mail caml-list-request@inria.fr  Archives: http://caml.inria.fr

Re: [Caml-list] Integer arithmetic: mod

[Xavier Leroy]

> I strongly advise against leaving the meaning of any built-in or
> library function or operator as implementation-defined. If you do this
> you will get unportable programs and inefficient programs (because
> people who want their programs to be portable will be forced to define
> their own versions of the functions).

I can agree with this argument.

> In my opinion and in most people's opinion, as far as I can tell, if
> you're starting afresh, the best way to define integer division is as
> rounding downwards. Integer remainder, to be consistent with this, has
> the sign of the divisor. There are lots of arguments that support this
> type of division, both mathematical and practical, and the only
> arguments against it seem to involve compatibility: the other sort of
> division is faster on some widely used hardware, is required by some
> widely used programming languages and assumed by some existing
> software.

Well, all hardware today implements round-towards-zero for division,
and this is unlikely to change in the future since ISO C9x requires
this behavior, so this will remain the behavior of "/" in OCaml.
We certainly do not want to penalize the existing programs that use
"/" and "mod" correctly, i.e. on positive arguments.

I'm favorable to providing proper Euclidean division and modulus as
library functions.  But: I disagree with your statement that

> the best way to define integer division is as
> rounding downwards. Integer remainder, to be consistent with this, has
> the sign of the divisor.

The way I learned Euclidean division in college is that the quotient q
and the modulus r of a divided by b are defined by

        a = b * q + r  with 0 <= r < |b|

e.g. the modulus is never negative, and division does not necessarily
rounds downwards.  I believe what mathematically-oriented minds really
want is a modulus that is always positive.

Any mathematician on this list who could look it up in Bourbaki?

- Xavier Leroy
-------------------
Bug reports: http://caml.inria.fr/bin/caml-bugs  FAQ: http://caml.inria.fr/FAQ/
To unsubscribe, mail caml-list-request@inria.fr  Archives: http://caml.inria.fr

Re: [Caml-list] Integer arithmetic: mod

[Vesa Karvonen]

IIRC, the appendix on arithmetic in Computer Architecture: A Quantitative
Approach by Hennessy and Patterson (ISBN: 1558603298) has some rather
convincing arguments on the superior definition of integer div and mod. Well
worth reading.

Regards,
  Vesa Karvonen

----- Original Message -----
From: "Xavier Leroy" <xavier.leroy@inria.fr>
To: "Edmund GRIMLEY EVANS" <edmundo@rano.org>
Cc: <caml-list@inria.fr>
Sent: Monday, November 19, 2001 17:49
Subject: Re: [Caml-list] Integer arithmetic: mod


> > I strongly advise against leaving the meaning of any built-in or
> > library function or operator as implementation-defined. If you do this
> > you will get unportable programs and inefficient programs (because
> > people who want their programs to be portable will be forced to define
> > their own versions of the functions).
>
> I can agree with this argument.
>
> > In my opinion and in most people's opinion, as far as I can tell, if
> > you're starting afresh, the best way to define integer division is as
> > rounding downwards. Integer remainder, to be consistent with this, has
> > the sign of the divisor. There are lots of arguments that support this
> > type of division, both mathematical and practical, and the only
> > arguments against it seem to involve compatibility: the other sort of
> > division is faster on some widely used hardware, is required by some
> > widely used programming languages and assumed by some existing
> > software.
>
> Well, all hardware today implements round-towards-zero for division,
> and this is unlikely to change in the future since ISO C9x requires
> this behavior, so this will remain the behavior of "/" in OCaml.
> We certainly do not want to penalize the existing programs that use
> "/" and "mod" correctly, i.e. on positive arguments.
>
> I'm favorable to providing proper Euclidean division and modulus as
> library functions.  But: I disagree with your statement that
>
> > the best way to define integer division is as
> > rounding downwards. Integer remainder, to be consistent with this, has
> > the sign of the divisor.
>
> The way I learned Euclidean division in college is that the quotient q
> and the modulus r of a divided by b are defined by
>
>         a = b * q + r  with 0 <= r < |b|
>
> e.g. the modulus is never negative, and division does not necessarily
> rounds downwards.  I believe what mathematically-oriented minds really
> want is a modulus that is always positive.
>
> Any mathematician on this list who could look it up in Bourbaki?
>
> - Xavier Leroy
> -------------------
> Bug reports: http://caml.inria.fr/bin/caml-bugs  FAQ:
http://caml.inria.fr/FAQ/
> To unsubscribe, mail caml-list-request@inria.fr  Archives:
http://caml.inria.fr
>

-------------------
Bug reports: http://caml.inria.fr/bin/caml-bugs  FAQ: http://caml.inria.fr/FAQ/
To unsubscribe, mail caml-list-request@inria.fr  Archives: http://caml.inria.fr

Re: [Caml-list] Integer arithmetic: mod

[Marcin 'Qrczak' Kowalczyk]

Sat, 04 Aug 2001 11:48:07 -0700, Chris Hecker <checker@d6.com> pisze:

> Most computer languages (and chips) simply say "(a/b)*b + a mod b =
> a" and leave it at that.

Fortunately not all, e.g. in Python (-123) % 10 == 7. In C89 the
behavior for negative numbers was left implementation-defined but
in C99 it is specified as truncation towards 0.

> Unfortunately, people (and language and chip designers) assume
> (-4)/3 = -1 (truncate towards zero) rather than -2 (floor),

Not all people: Donald Knuth clearly disagrees. He has written
something along the lines "beware of programming languages which use
a different definition than the one which says (-4)/3 = -2".

Haskell has both: div & mod truncate downwards, quot & rem truncate
towards 0.

-- 
 __("<  Marcin Kowalczyk * qrczak@knm.org.pl http://qrczak.ids.net.pl/
 \__/
  ^^                      SYGNATURA ZASTĘPCZA
QRCZAK

-------------------
Bug reports: http://caml.inria.fr/bin/caml-bugs  FAQ: http://caml.inria.fr/FAQ/
To unsubscribe, mail caml-list-request@inria.fr  Archives: http://caml.inria.fr

Re: [Caml-list] Integer arithmetic: mod

[Chris Hecker]

> > Unfortunately, people (and language and chip designers) assume
> > (-4)/3 = -1 (truncate towards zero) rather than -2 (floor),
> Not all people: Donald Knuth clearly disagrees. He has written
> something along the lines "beware of programming languages which use
> a different definition than the one which says (-4)/3 = -2".

Yeah, Concrete Mathematics by Knuth, Graham, and Patashnik is the
bible for this sort of thing.

> Haskell has both: div & mod truncate downwards, quot & rem truncate
> towards 0.

Ah, that's a good idea, although I'd assume the div floor behavior is
surprising at first.

Chris


-------------------
Bug reports: http://caml.inria.fr/bin/caml-bugs  FAQ: http://caml.inria.fr/FAQ/
To unsubscribe, mail caml-list-request@inria.fr  Archives: http://caml.inria.fr

Re: [Caml-list] Integer arithmetic: mod

[John Gerard Malecki]

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?

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**N-1)

I guess it doesn't much matter as this optimization is normally
applied to array indices which usually are non-negative anyway.

PS - i'm not sure if this trick also works with 1s complement
     representation but when was the last time anyone built one of
     those machines?
-------------------
Bug reports: http://caml.inria.fr/bin/caml-bugs  FAQ: http://caml.inria.fr/FAQ/
To unsubscribe, mail caml-list-request@inria.fr  Archives: http://caml.inria.fr

[Caml-list] Integer arithmetic: mod

[Kai Kaminski]

Hi,

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 platform-dependent?
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 high-level language as OCaml.
The reason is that whenever such a behaviour is platform-dependent, you
can't use it at all, as long as you want to have your programs portable.
Beside that the speed penalty (are there other problems with this
approach?) would probably be not too bad, would it?

On the other hand I'm just a student, who doesn't know too much about
programming languages and their implementation. So could someone please
enlighten me?

Kai Kaminski
-------------------
Bug reports: http://caml.inria.fr/bin/caml-bugs  FAQ: http://caml.inria.fr/FAQ/
To unsubscribe, mail caml-list-request@inria.fr  Archives: http://caml.inria.fr

Re: [Caml-list] Integer arithmetic: mod

[Chris Hecker]

> Now, I could live with -1 mod 10 = -1, but why is it platform-dependent?

There are two ways to define mod for negative numbers.  They're both mathematically valid (meaning you can write equations with them both).

Most computer languages (and chips) simply say "(a/b)*b + a mod b = a" and leave it at that.  Unfortunately, people (and language and chip designers) assume (-4)/3 = -1 (truncate towards zero) rather than -2 (floor), and that seals the fate of (-4) mod 3 to be -1 instead of 2.

Here's a good discussion:
http://forum.swarthmore.edu/dr.math/problems/anne.4.28.99.html

>The reason is that whenever such a behaviour is platform-dependent, you
>can't use it at all, as long as you want to have your programs portable.
>Beside that the speed penalty (are there other problems with this
>approach?) would probably be not too bad, would it?

I think caml did the right thing (just let the cpu do it) with a bad situation (inconsistencies).  You're free to define your own versions if the built in ones don't work for you, and this doesn't penalize everybody (some people like the "remainder" result rather than the "floor" result).

Chris

-------------------
Bug reports: http://caml.inria.fr/bin/caml-bugs  FAQ: http://caml.inria.fr/FAQ/
To unsubscribe, mail caml-list-request@inria.fr  Archives: http://caml.inria.fr

Re: [Caml-list] Integer arithmetic: mod

[John Max Skaller]

Kai Kaminski wrote:
> 
> Hi,
> 
> 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.


> The reason is that whenever such a behaviour is platform-dependent, you
> can't use it at all, as long as you want to have your programs portable.

	Yes you can: it works for non-negative arguments.
And you can always roll your own function that works as you desire
for negative ones:

	let mymod x y = 
		if ((x mod y) as r) < 0 
		then r + y 
		else r

which works for negative x provided the result is in the range

	 y .. -1

This way, YOU choose whether you want a deterministic result
for non-negative values (use mod, its fast), or are willing
to pay extra for determinism for negative values.

But I agree with you anyhow. :-)

-- 
John (Max) Skaller, mailto:skaller@maxtal.com.au 
10/1 Toxteth Rd Glebe NSW 2037 Australia voice: 61-2-9660-0850
New generation programming language Felix  http://felix.sourceforge.net
Literate Programming tool Interscript     
http://Interscript.sourceforge.net
-------------------
Bug reports: http://caml.inria.fr/bin/caml-bugs  FAQ: http://caml.inria.fr/FAQ/
To unsubscribe, mail caml-list-request@inria.fr  Archives: http://caml.inria.fr

Re: [Caml-list] Integer arithmetic: mod

[Kai Kaminski]

On Mon, Aug 06, 2001 at 09:35:15AM +1000, John Max Skaller wrote:
> > The reason is that whenever such a behaviour is platform-dependent, you
> > can't use it at all, as long as you want to have your programs portable.
> 
> 	Yes you can: it works for non-negative arguments.
> And you can always roll your own function that works as you desire
> for negative ones:
I'm using a high-level language like OCaml and I still have to define my
own 'mod'-operator? I know that it is possible to write a function that
gives me what I want.

> This way, YOU choose whether you want a deterministic result
> for non-negative values (use mod, its fast), or are willing
> to pay extra for determinism for negative values.
With a second operator this wouldn't be a problem. If you need really
fast code and the behaviour for negative numbers doesn't matter, you
just choose the faster one. Your code gets a bit platform specific, but
it is better to 'punish' the few implementors of speed-critical
applications, than all the rest of us.

> But I agree with you anyhow. :-)
IMHO, that's always a good thing ;)

Kai Kaminski
-------------------
Bug reports: http://caml.inria.fr/bin/caml-bugs  FAQ: http://caml.inria.fr/FAQ/
To unsubscribe, mail caml-list-request@inria.fr  Archives: http://caml.inria.fr

Re: [Caml-list] Integer arithmetic: mod

[Xavier Leroy]

> 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 platform-dependent?

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 high-level language as OCaml.

That's a reasonable argument.  The counter-argument 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
> implementation-defined 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**N-1)

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^N-1) asr N
         M mod 2^N = M - ((if M >= 0 then M else M + 2^N-1) land (-2^N))

just to get a consistent behavior with the hardware "mod" instruction!

- Xavier Leroy

-------------------
Bug reports: http://caml.inria.fr/bin/caml-bugs  FAQ: http://caml.inria.fr/FAQ/
To unsubscribe, mail caml-list-request@inria.fr  Archives: http://caml.inria.fr

Re: [Caml-list] Integer arithmetic: mod

[Kai Kaminski]

On Mon, Aug 06, 2001 at 11:10:00AM +0200, Xavier Leroy wrote:
> > 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.
I agree. Is there a chance that this will really happen in a future
release of OCaml? Is there a roadmap for OCaml-development?

Kai Kaminski
-------------------
Bug reports: http://caml.inria.fr/bin/caml-bugs  FAQ: http://caml.inria.fr/FAQ/
To unsubscribe, mail caml-list-request@inria.fr  Archives: http://caml.inria.fr

Re: [Caml-list] Integer arithmetic: mod

[Xavier Leroy]

> > 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.
> I agree. Is there a chance that this will really happen in a future
> release of OCaml?

There is a chance, yes.  It takes a bit of implementation work, and I
consider this a low-priority feature, but yes it will probably be
implemented once the higher-priority stuff is dealt with.

> Is there a roadmap for OCaml-development?

<JOKE>
I'm glad you asked this, because it's time to reveal to the world that
the development of OCaml is actually entirely handled by a collection of
super-advanced genetic algorithms that simply mutate the sources until
cool features emerge.  We just sit and watch.  The mutations can be
directed by some sample code fragments written in any other language;
the genetic algorithms then try to extract new language features that
match the sample code.  For instance, the object system in OCaml
started to emerge when we fed it some Java and Smalltalk sources.
Later, Jacques Garrigue threw in some Ada and Visual Basic code, and
bingo! we got the labels of OCaml 3.00.  The next step will probably
be some Cobol fragments.  I fully expect to get some interesting
concepts out of this, such as BCD arithmetic, or even cool new syntax
such as "divide a by b giving c in ..."
</JOKE>

(But see http://www.technologyreview.com/web/knorr/knorr080301.asp
for similar ideas being actually experimented for producing patent
applications.)

More seriously: yes, there is a roadmap, at least for important
changes (in the language or in the basic architecture of the
implementation); no, we don't normally discuss it publicly.  Small
changes such as adding new library functions are generally dealt on a
"by need" basis.

- Xavier Leroy
-------------------
Bug reports: http://caml.inria.fr/bin/caml-bugs  FAQ: http://caml.inria.fr/FAQ/
To unsubscribe, mail caml-list-request@inria.fr  Archives: http://caml.inria.fr