is mod correct?
Chouser
user=> (map #(mod % 3) (range -9 9))
(3 1 2 3 1 2 3 1 2 0 1 2 0 1 2 0 1 2)
It disagrees with, for example, Ruby:
irb(main):002:0> (-9..9).map{|x| x % 3}
=> [0, 1, 2, 0, 1, 2, 0, 1, 2, 0, 1, 2, 0, 1, 2, 0, 1, 2, 0]
And python:
>>> map( lambda x: x % 3, range(-9,9) )
[0, 1, 2, 0, 1, 2, 0, 1, 2, 0, 1, 2, 0, 1, 2, 0, 1, 2]
--Chouser
Jeffrey Straszheim
Timothy Pratley
Based upon
http://mathforum.org/library/drmath/view/52343.html
mod might be modified to look like this
(defn mod1
"modulus of num and div."
[num div]
(cond
(or (not (integer? num)) (not (integer? div)))
(throw (IllegalArgumentException.
"mod requires two integers"))
(< num 0 div) (- (rem num div))
(< div 0 num) (rem num (- div))
:else (rem num div)))
user=> (map #(mod1 % 3) (range -9 9))
(0 2 1 0 2 1 0 2 1 0 1 2 0 1 2 0 1 2)
> [0, 1, 2, 0, 1, 2, 0, 1, 2, 0, 1, 2, 0, 1, 2, 0, 1, 2]
believe it is 'correct' due to Java and Clojure's definition of div.
Ruby and Python define integer division of or by a negative number
differently that C and Java do. Consider the quotient -7/3. Java gives
-2. Ruby gives -3.
Regards,
Tim.
Timothy Pratley
mod performs the operation floor on number and divisor and returns the
remainder of the floor operation.
Which would indicate that mod1 is not consistent with LISP.
Seeing Java doesn't have a proper mod, it would seem sensible to
follow the LISP/Ruby/Python convention...
(defn mod2
[num div]
(or (not (integer? num)) (not (integer? div)))
(throw (IllegalArgumentException.
"mod requires two integers"))
(or (< num 0 div) (< div 0 num)) (+ m div)
:else m)))
user=> (map #(mod2 % 3) (range -9 9))
(0 1 2 0 1 2 0 1 2 0 1 2 0 1 2 0 1 2)
user=> (map #(mod2 % -3) (range -9 9))
(0 -2 -1 0 -2 -1 0 -2 -1 0 -2 -1 0 -2 -1 0 -2 -1)
>>> map(lambda x: x % -3, range(-9,9) )
[0, -2, -1, 0, -2, -1, 0, -2, -1, 0, -2, -1, 0, -2, -1, 0, -2, -1]
ie: I think the original implementation simply overlooked the case
where rem div num is 0, as per floor.
Regards,
Tim.
On Feb 11, 10:46 am, Timothy Pratley <timothyprat...@gmail.com> wrote:
> Interesting!
>
> Based uponhttp://mathforum.org/library/drmath/view/52343.html
Stephen C. Gilardi
> I spoke too soon. Apparently from the Lisp HyperSpec
> mod performs the operation floor on number and divisor and returns the
> remainder of the floor operation.
> Which would indicate that mod1 is not consistent with LISP.
> Seeing Java doesn't have a proper mod, it would seem sensible to
> follow the LISP/Ruby/Python convention...
I agree.
Absent some compelling reason to the contrary, I think it would be a
wise policy for Clojure to defer to Common Lisp in cases like this.
Those behaviors have been pored over for years by really smart people--
not a guarantee of correctness, of course, but the probability is
really high.
The fact that apparently we can also simultaneously include the really
smart folks who've been refining Python and Ruby for years is a great
bonus.
--Steve
Timothy Pratley
arguments.
It would be better arranged like so:
(defn mod2
"Modulus of num and div. Truncates toward negative infinity."
[num div]
(if (or (not (integer? num)) (not (integer? div)))
(not (zero? m))
(or (< num 0 div) (< div 0 num)))
(+ m div)
m))))
Same behavior:
user=> (map #(mod2 % 3) (range -9 9))
(0 1 2 0 1 2 0 1 2 0 1 2 0 1 2 0 1 2)
user=> (map #(mod2 % -3) (range -9 9))
(0 -2 -1 0 -2 -1 0 -2 -1 0 -2 -1 0 -2 -1 0 -2 -1)
mistake.
Regards,
Tim.
Chouser
<timothy...@gmail.com> wrote:
>
> In the code I posted the let evaluated rem before checking the
> arguments.
Thanks for doing all the hard work. :-)
How about:
(defn mod42
"Modulus of num and div. Truncates toward negative infinity."
[num div]
(if-not (and (integer? num) (integer? div))
(throw (IllegalArgumentException. "mod requires two integers"))
(let [m (rem num div)]
(if (or (zero? m) (> (* num div) 0))
m
(+ m div)))))
--Chouser
Timothy Pratley
(> (* num div) 0)
could be (pos? (* num div)) too I guess... but is sadly slightly
longer!
Chouser
But simpler and clearer. Thanks for the catch.
--Chouser
Mark Engelberg
error. I missed the case of a negative divisor and a 0 remainder
among my test cases for the mod function.
Thanks for noticing and fixing the problem.
Although Chouser's version is slightly more compact than Pratley's, I
wonder if a multiplication followed by a single comparison to zero is
a significantly more or less expensive operation than several
comparisons to zero? My instinct is that multiplication is more
expensive, but I haven't had a chance to really check.
Timothy Pratley
simple tests show it performing better:
user=> (time (dotimes [i 1000000] (zero? (* 5 11))))
"Elapsed time: 183.358706 msecs"
user=> (time (dotimes [i 1000000] (or (< 5 0 11) (< 11 0 5))))
"Elapsed time: 682.586025 msecs"
In practice it doesn't seem to make much difference overall:
user=> (time (dotimes [i 1000000] (map #(mod2 % 3) (range -9 9)) ))
"Elapsed time: 966.868765 msecs"
user=> (time (dotimes [i 1000000] (map #(mod42 % 3) (range -9 9)) ))
"Elapsed time: 938.675334 msecs"
But the multiply seems to have the edge in both expression and speed.
Regards,
Tim.
David Sletten
On Feb 10, 2009, at 4:15 PM, Chouser wrote:
>
>
> (defn mod42
> "Modulus of num and div. Truncates toward negative infinity."
> [num div]
> (if-not (and (integer? num) (integer? div))
> (throw (IllegalArgumentException. "mod requires two integers"))
> (let [m (rem num div)]
> (if (or (zero? m) (> (* num div) 0))
> m
> (+ m div)))))
>
Just for giggles, here's how SBCL (Steel Bank Common Lisp) defines
the two functions:
(defun rem (number divisor)
#!+sb-doc
"Return second result of TRUNCATE."
(multiple-value-bind (tru rem) (truncate number divisor)
(declare (ignore tru))
rem))
(defun mod (number divisor)
#!+sb-doc
"Return second result of FLOOR."
(let ((rem (rem number divisor)))
(if (and (not (zerop rem))
(if (minusp divisor)
(plusp number)
(minusp number)))
(+ rem divisor)
rem)))
Notice that despite the documentation, MOD does not actually call
FLOOR. It indirectly calls TRUNCATE via REM. It's also important to
notice that Common Lisp is a Lisp-2, so that we can store the result
of the REM call in a variable with the same name in the LET form.
Aloha,
David Sletten
Vincent Foley
rem :: a -> a -> a
integer remainder, satisfying (x `quot` y)*y + (x `rem` y) == x
mod :: a -> a -> a
integer modulus, satisfying (x `div` y)*y + (x `mod` y) == x
div truncates toward negative infinity while quot (which is in
Clojure) truncates toward 0.
Vincent.
[1] http://www.haskell.org/ghc/docs/6.8.3/html/libraries/base/Prelude.html
Rich Hickey
Rich
Timothy Pratley
http://code.google.com/p/clojure/issues/detail?id=23
Frantisek Sodomka
integers!):
user=> (rem 1 2/3)
1/3
user=> (mod 1 2/3)
java.lang.IllegalArgumentException: mod requires two integers
(NO_SOURCE_FILE:0)
user=> (rem 4.5 2.0)
0.5
user=> (mod 4.5 2.0)
java.lang.IllegalArgumentException: mod requires two integers
(NO_SOURCE_FILE:0)
Frantisek
Timothy Pratley
On Feb 12, 10:47 pm, Frantisek Sodomka <fsodo...@gmail.com> wrote:
> Also, "mod" seems too strict about numbers it accepts (only
> integers!):
Removed the integer checks, hey it is looking really similar to SBCL
now o_O
http://clojure.googlecode.com/issues/attachment?aid=-820378369815807498&name=mod-fix.patch
David Sletten
The real hit would come with bignums, no? But as far as the routine
use of MOD goes we're probably talking about fixnums > 99% of the time.
Aloha,
David Sletten
Frantisek Sodomka
this moment. We have unchecked-remainder, but there isn't unchecked-
quotient or unchecked-modulo.
I added tests for mod, rem & quot to test-clojure.numbers:
http://code.google.com/p/clojure-contrib/source/browse/trunk/src/clojure/contrib/test_clojure/numbers.clj
Frantisek
Timothy Pratley
> use of MOD goes we're probably talking about fixnums > 99% of the time.
I tried some more timings on various configurations:
; Currently submitted (soon to be dethroned) patch
(defn mod1
[num div]
m
(+ m div))))
; verbatim from SBCL
"Modulus of num and div. Truncates toward negative infinity."
[num div]
(if (and (not (zero? rem))
(if (neg? div)
(pos? num)
(neg? num)))
(+ rem div)
rem)))
; comparing the signs, inverse logic to SBCL for slightly less
function calls and common case first
(defn mod3
[num div]
(if (or (= (pos? num) (pos? div)) (zero? r))
r
(+ r div))))
; use SBCL style if trick instead of comparing signs
(defn mod4
[num div]
(if (or (if (pos? num)
(pos? div)
(neg? div))
(zero? r))
r
(+ r div))))
user=> (time (dorun (map #(mod4 % 3) (range -9 9000000)) ))
"Elapsed time: 13119.193251 msecs"
user=> (time (dorun (map #(mod4 % 3) (range -9000000 9)) ))
"Elapsed time: 14771.158608 msecs"
user=> (time (dotimes [i 10000] (mod4 (bigint 1e1000M) (inc i))))
"Elapsed time: 3809.305116 msecs"
user=> (time (dorun (map #(mod3 % 3) (range -9 9000000)) ))
"Elapsed time: 13109.544278 msecs"
user=> (time (dorun (map #(mod3 % 3) (range -9000000 9)) ))
"Elapsed time: 15408.188226 msecs"
user=> (time (dotimes [i 10000] (mod3 (bigint 1e1000M) (inc i))))
"Elapsed time: 3801.648725 msecs"
user=> (time (dorun (map #(mod2 % 3) (range -9 9000000)) ))
"Elapsed time: 14642.528284 msecs"
user=> (time (dorun (map #(mod2 % 3) (range -9000000 9)) ))
"Elapsed time: 16286.011241 msecs"
user=> (time (dotimes [i 10000] (mod2 (bigint 1e1000M) (inc i))))
"Elapsed time: 3826.870597 msecs"
user=> (time (dorun (map #(mod1 % 3) (range -9 9000000)) ))
"Elapsed time: 14151.776571 msecs"
user=> (time (dorun (map #(mod1 % 3) (range -9000000 9)) ))
"Elapsed time: 14975.93798 msecs"
user=> (time (dotimes [i 10000] (mod1 (bigint 1e1000M) (inc i))))
"Elapsed time: 3840.114813 msecs"
Obviously these numbers are subject to variance etc... but the upshot
seemed to be that there wasn't a substantial difference between any of
the forms (I was especially surprised by bigint not playing a factor,
perhaps my tests were flawed. In terms of style I think checking that
the signs are equal is in some ways more obvious than multiplying,
however = pos? pos? is arguably confusing also. The SBCL if nesting is
neat too, so I really don't know which is best.
Regards,
Tim.