R4RS and modulo (was: need help understanding modulo)
Jussi Piitulainen
Leif Nixon <ni...@softlab.se> writes:
> [...]
>
> But I actually don't understand *why* R4RS defines modulo and
> remainder in this way. The usual definition of modulo for
> negative arguments (see for example Concrete Mathematics by
> Graham, Knuth & Patashnik or The C Programming Language by
> Kernighan & Ritchie) corresponds to R4RS's definition of
> remainder.
On the contrary, Graham, Knuth and Patashnik (second edition) agree
with Alan Bawden. I checked. Their definition of `mod' for arbitrary
reals is
x mod y = x - y * floor(x/y), for y /= 0 (3.21)
x mod 0 = x (3.22)
and they point out that
0 <= x mod y < y, for y > 0
0 >= x mod y > y, for y < 0.
Note that R4RS defines `modulo' for integers only, with nonzero second
argument.
Graham et al. call `floor(x/y)' the quotient, but it is different from
`quotient' in Scheme. They also call `x mod y' the remainder, but it
is actually a generalisation of `modulo' in Scheme.
> From: Al...@LCS.MIT.EDU (Alan Bawden)
> Subject: need help understanding modulo
> Date: 12 Sep 1996 05:57:20 -0400
>
> [...] It's trying to say that if
>
> (modulo i m) ==> j
>
> then either 0 <= j < m or m < j <= 0, depending on the sign of m. Just
> like the `mod' function in Common Lisp. [*]
>
> [...]
>
> I also often find myself wishing for the function that behaves for `modulo'
> the way that `quotient' behaves for `remainder'. I sure wish Scheme had it.
That would be the `quotient' of Graham, Knuth and Patashnik, or the
two-argument `floor' in Common Lisp, or something like
(lambda (n1 n2) (floor (/ n1 n2)))
in Scheme, right? Call it `quotient-1'. Then, in Scheme, we would
have
(= n1 (+ (* n2 (quotient n1 n2))
(remainder n1 n2)))
and
(= n1 (+ (* n2 (quotient-1 n1 n2))
(modulo n1 n2))).
Somebody tell me if I am mistaken?
> -------(footnote)-------
>
> [*] and if m is zero, it should return i, rather than signaling an error.
> But computer scientists insist on incorrectly thinking of `modulo' as
> having something to do with division, so I've given up arguing this point.
The subtitle to `Concrete Mathematics' is `A foundation for Computer
Science'. I gather they get it right ... and Scheme get it wrong.
Implementations are free to correct this. R4RS fails to specify any
behaviour for `(modulo n 0)'. It will not be portable.
--
Jussi Piitulainen
Leif Nixon
Jussi Piitulainen wrote:
>
> Leif Nixon <ni...@softlab.se> writes:
>
> > [...]
> >
> > But I actually don't understand *why* R4RS defines modulo and
> > remainder in this way. The usual definition of modulo for
> > negative arguments (see for example Concrete Mathematics by
> > Graham, Knuth & Patashnik or The C Programming Language by
> > Kernighan & Ritchie) corresponds to R4RS's definition of
> > remainder.
>
> On the contrary, Graham, Knuth and Patashnik (second edition) agree
> with Alan Bawden. I checked.
Yes, you're of course right. I'm sorry for not sleeping enough before
thinking about mathematics, and for any confusion I might have caused.
I find the margin note accompanying GKP's mod definition interesting:
"Beware of computer languages that use another definition."
Leif Nixon SoftLab AB
-------------------------------------------------
E-mail: ni...@softlab.se Phone: +46 13 23 57 61
-------------------------------------------------
Bradley J Lucier
Will Clinger asked me to post some previous e-mail he sent me
to this newsgroup; he apologizes that he can't reply himself
because of network problems.
Basically, everyone agrees on what modulo should do in Scheme and this
thread should die a quiet death.
From wi...@ccs.neu.edu Fri Sep 13 16:05:53 1996
To: Al...@LCS.MIT.EDU, Brad Lucier <luc...@MATH.Purdue.EDU>
Thank you all for setting me straight on Scheme's MODULO.
No wonder it seemed so useless to me! Had I understood
(and implemented) it correctly, I too would have used it
more often than REMAINDER.
Will
Jussi Piitulainen
b...@cs.purdue.edu (Bradley J Lucier) writes:
> [...]
>
> Basically, everyone agrees on what modulo should do in Scheme and this
> thread should die a quiet death.
Why do you insist that the thread should die? There is little more to
be said, but what has been said has been about an unclear description
of a Scheme procedure in R4RS, which seems an appropriate topic in
comp.lang.scheme.
Let me put it this way: Does everyone now agree that the description
of `modulo' in R4RS is both clear and correct? I hope not.
--
Bradley J Lucier
I made a mistake---there is no topic on which everyone agrees.
Clinger, Bawden, I, and several other people now agree that if
(modulo j m) ==> k
then either 0 <= k < m or m < k <= 0, depending on the sign of m.
This agrees with mathematical usage when m>0, and Graham, Knuth,
and Patashnik (page 82) when $m>0$ or $m<0$. When $m=0$, I would
think that the above property implies that (modulo j 0) is undefined
since there are no numbers in the range given above when $m=0$.
However, Graham, Knuth, and Patashnik say it is important for some
of their applications that j mod 0 = j. They also define mod for
all real j and m.
It's unfortunate that the wording of R4RS seems to be unclear on
this. It would be good if this section were rewritten to reflect
what can be agreed on, and perhaps to extend the definition of modulo
to real arguments or m=0.
Brad Lucier luc...@math.purdue.edu
Jussi Piitulainen
b...@cs.purdue.edu (Bradley J Lucier) writes:
> I made a mistake---there is no topic on which everyone agrees.
(True ...)
> [...]
>
> It's unfortunate that the wording of R4RS seems to be unclear on
> this. It would be good if this section were rewritten to reflect
> what can be agreed on, and perhaps to extend the definition of modulo
> to real arguments or m=0.
Thank you for this clarification. We are in perfect agreement.
--
Jussi Piitulainen