Re: is mod correct?
> 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. Good point, I tried some more timings on various configurations: ; Currently submitted (soon to be dethroned) patch (defn mod1 "Modulus of num and div. Truncates toward negative infinity." [num div] (let [m (rem num div)] (if (or (zero? m) (pos? (* num div))) m (+ m div ; verbatim from SBCL (defn mod2 "Modulus of num and div. Truncates toward negative infinity." [num div] (let [rem (rem 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 "Modulus of num and div. Truncates toward negative infinity." [num div] (let [r (rem num div)] (if (or (= (pos? num) (pos? div)) (zero? r)) r (+ r div ; use SBCL style if trick instead of comparing signs (defn mod4 "Modulus of num and div. Truncates toward negative infinity." [num div] (let [r (rem num div)] (if (or (if (pos? num) (pos? div) (neg? div)) (zero? r)) r (+ r div user=> (time (dorun (map #(mod4 % 3) (range -9 900)) )) "Elapsed time: 13119.193251 msecs" user=> (time (dorun (map #(mod4 % 3) (range -900 9)) )) "Elapsed time: 14771.158608 msecs" user=> (time (dotimes [i 1] (mod4 (bigint 1e1000M) (inc i "Elapsed time: 3809.305116 msecs" user=> (time (dorun (map #(mod3 % 3) (range -9 900)) )) "Elapsed time: 13109.544278 msecs" user=> (time (dorun (map #(mod3 % 3) (range -900 9)) )) "Elapsed time: 15408.188226 msecs" user=> (time (dotimes [i 1] (mod3 (bigint 1e1000M) (inc i "Elapsed time: 3801.648725 msecs" user=> (time (dorun (map #(mod2 % 3) (range -9 900)) )) "Elapsed time: 14642.528284 msecs" user=> (time (dorun (map #(mod2 % 3) (range -900 9)) )) "Elapsed time: 16286.011241 msecs" user=> (time (dotimes [i 1] (mod2 (bigint 1e1000M) (inc i "Elapsed time: 3826.870597 msecs" user=> (time (dorun (map #(mod1 % 3) (range -9 900)) )) "Elapsed time: 14151.776571 msecs" user=> (time (dorun (map #(mod1 % 3) (range -900 9)) )) "Elapsed time: 14975.93798 msecs" user=> (time (dotimes [i 1] (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. --~--~-~--~~~---~--~~ You received this message because you are subscribed to the Google Groups "Clojure" group. To post to this group, send email to clojure@googlegroups.com To unsubscribe from this group, send email to clojure+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/clojure?hl=en -~--~~~~--~~--~--~---
Re: is mod correct?
There are also unchecked versions. Don't know if they are needed at 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 On Feb 12, 1:12 pm, Timothy Pratley wrote: > On Feb 12, 10:47 pm, Frantisek Sodomka wrote: > > > Also, "mod" seems too strict about numbers it accepts (only > > integers!): > > *chuckle* indeed, why be so strict! > Removed the integer checks, hey it is looking really similar to SBCL > now > o_Ohttp://clojure.googlecode.com/issues/attachment?aid=-8203783698158074... --~--~-~--~~~---~--~~ You received this message because you are subscribed to the Google Groups "Clojure" group. To post to this group, send email to clojure@googlegroups.com To unsubscribe from this group, send email to clojure+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/clojure?hl=en -~--~~~~--~~--~--~---
Re: is mod correct?
On Feb 10, 2009, at 6:37 PM, Timothy Pratley wrote: > > I would have expected the mult to be a performance hit, but my overly > simple tests show it performing better: > user=> (time (dotimes [i 100] (zero? (* 5 11 > "Elapsed time: 183.358706 msecs" > user=> (time (dotimes [i 100] (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 100] (map #(mod2 % 3) (range -9 9)) )) > "Elapsed time: 966.868765 msecs" > user=> (time (dotimes [i 100] (map #(mod42 % 3) (range -9 9)) )) > "Elapsed time: 938.675334 msecs" > > But the multiply seems to have the edge in both expression and speed. > > 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 --~--~-~--~~~---~--~~ You received this message because you are subscribed to the Google Groups "Clojure" group. To post to this group, send email to clojure@googlegroups.com To unsubscribe from this group, send email to clojure+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/clojure?hl=en -~--~~~~--~~--~--~---
Re: is mod correct?
On Feb 12, 10:47 pm, Frantisek Sodomka wrote: > Also, "mod" seems too strict about numbers it accepts (only > integers!): *chuckle* indeed, why be so strict! 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 --~--~-~--~~~---~--~~ You received this message because you are subscribed to the Google Groups "Clojure" group. To post to this group, send email to clojure@googlegroups.com To unsubscribe from this group, send email to clojure+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/clojure?hl=en -~--~~~~--~~--~--~---
Re: is mod correct?
Also, "mod" seems too strict about numbers it accepts (only
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
On Feb 10, 10:30 pm, Chouser wrote:
> Is 'mod' working correctly?
>
> 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
--~--~-~--~~~---~--~~
You received this message because you are subscribed to the Google Groups
"Clojure" group.
To post to this group, send email to clojure@googlegroups.com
To unsubscribe from this group, send email to
clojure+unsubscr...@googlegroups.com
For more options, visit this group at
http://groups.google.com/group/clojure?hl=en
-~--~~~~--~~--~--~---
Re: is mod correct?
> Patch welcome, if you've all come to a conclusion. Attached to original issue http://code.google.com/p/clojure/issues/detail?id=23 --~--~-~--~~~---~--~~ You received this message because you are subscribed to the Google Groups "Clojure" group. To post to this group, send email to clojure@googlegroups.com To unsubscribe from this group, send email to clojure+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/clojure?hl=en -~--~~~~--~~--~--~---
Re: is mod correct?
On Feb 10, 11:18 pm, Mark Engelberg wrote: > I was the source of this error, and I agree that the behavior is an > 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. Patch welcome, if you've all come to a conclusion. Rich --~--~-~--~~~---~--~~ You received this message because you are subscribed to the Google Groups "Clojure" group. To post to this group, send email to clojure@googlegroups.com To unsubscribe from this group, send email to clojure+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/clojure?hl=en -~--~~~~--~~--~--~---
Re: is mod correct?
According to the GHC documentation [1]: 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 On Feb 10, 8:34 pm, Timothy Pratley wrote: > 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... > > (defn mod2 > "modulus of num and div." > [num div] > (let [m (rem num div)] > (cond > (or (not (integer? num)) (not (integer? div))) > (throw (IllegalArgumentException. > "mod requires two integers")) > (zero? m) 0 > (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 wrote: > > > Interesting! > > > Based uponhttp://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] > > > Notably that is still not the same as those other languages! However I > > 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. > > --~--~-~--~~~---~--~~ You received this message because you are subscribed to the Google Groups "Clojure" group. To post to this group, send email to clojure@googlegroups.com To unsubscribe from this group, send email to clojure+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/clojure?hl=en -~--~~~~--~~--~--~---
Re: is mod correct?
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 --~--~-~--~~~---~--~~ You received this message because you are subscribed to the Google Groups "Clojure" group. To post to this group, send email to clojure@googlegroups.com To unsubscribe from this group, send email to clojure+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/clojure?hl=en -~--~~~~--~~--~--~---
Re: is mod correct?
I would have expected the mult to be a performance hit, but my overly simple tests show it performing better: user=> (time (dotimes [i 100] (zero? (* 5 11 "Elapsed time: 183.358706 msecs" user=> (time (dotimes [i 100] (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 100] (map #(mod2 % 3) (range -9 9)) )) "Elapsed time: 966.868765 msecs" user=> (time (dotimes [i 100] (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. --~--~-~--~~~---~--~~ You received this message because you are subscribed to the Google Groups "Clojure" group. To post to this group, send email to clojure@googlegroups.com To unsubscribe from this group, send email to clojure+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/clojure?hl=en -~--~~~~--~~--~--~---
Re: is mod correct?
I was the source of this error, and I agree that the behavior is an 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. --~--~-~--~~~---~--~~ You received this message because you are subscribed to the Google Groups "Clojure" group. To post to this group, send email to clojure@googlegroups.com To unsubscribe from this group, send email to clojure+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/clojure?hl=en -~--~~~~--~~--~--~---
Re: is mod correct?
On Tue, Feb 10, 2009 at 9:37 PM, Timothy Pratley wrote: > > Great! > > (> (* num div) 0) > could be (pos? (* num div)) too I guess... but is sadly slightly > longer! But simpler and clearer. Thanks for the catch. --Chouser --~--~-~--~~~---~--~~ You received this message because you are subscribed to the Google Groups "Clojure" group. To post to this group, send email to clojure@googlegroups.com To unsubscribe from this group, send email to clojure+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/clojure?hl=en -~--~~~~--~~--~--~---
Re: is mod correct?
Great! (> (* num div) 0) could be (pos? (* num div)) too I guess... but is sadly slightly longer! --~--~-~--~~~---~--~~ You received this message because you are subscribed to the Google Groups "Clojure" group. To post to this group, send email to clojure@googlegroups.com To unsubscribe from this group, send email to clojure+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/clojure?hl=en -~--~~~~--~~--~--~---
Re: is mod correct?
On Tue, Feb 10, 2009 at 8:55 PM, Timothy Pratley 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 --~--~-~--~~~---~--~~ You received this message because you are subscribed to the Google Groups "Clojure" group. To post to this group, send email to clojure@googlegroups.com To unsubscribe from this group, send email to clojure+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/clojure?hl=en -~--~~~~--~~--~--~---
Re: is mod correct?
In the code I posted the let evaluated rem before checking the 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))) (throw (IllegalArgumentException. "mod requires two integers")) (let [m (rem num div)] (if (and (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) I'm sure there are better ways still, just wanted to correct my mistake. Regards, Tim. --~--~-~--~~~---~--~~ You received this message because you are subscribed to the Google Groups "Clojure" group. To post to this group, send email to clojure@googlegroups.com To unsubscribe from this group, send email to clojure+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/clojure?hl=en -~--~~~~--~~--~--~---
Re: is mod correct?
On Feb 10, 2009, at 8:34 PM, Timothy Pratley wrote: 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 smime.p7s Description: S/MIME cryptographic signature
Re: is mod correct?
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... (defn mod2 "modulus of num and div." [num div] (let [m (rem num div)] (cond (or (not (integer? num)) (not (integer? div))) (throw (IllegalArgumentException. "mod requires two integers")) (zero? m) 0 (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 wrote: > Interesting! > > Based uponhttp://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] > > Notably that is still not the same as those other languages! However I > 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. --~--~-~--~~~---~--~~ You received this message because you are subscribed to the Google Groups "Clojure" group. To post to this group, send email to clojure@googlegroups.com To unsubscribe from this group, send email to clojure+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/clojure?hl=en -~--~~~~--~~--~--~---
Re: is mod correct?
Interesting! 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] Notably that is still not the same as those other languages! However I 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. --~--~-~--~~~---~--~~ You received this message because you are subscribed to the Google Groups "Clojure" group. To post to this group, send email to clojure@googlegroups.com To unsubscribe from this group, send email to clojure+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/clojure?hl=en -~--~~~~--~~--~--~---
Re: is mod correct?
I've seen different theories on how mod should treat negative divisors, but
I've never seen that "solution".
On Tue, Feb 10, 2009 at 4:30 PM, Chouser wrote:
>
> Is 'mod' working correctly?
>
> 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
>
> >
>
--~--~-~--~~~---~--~~
You received this message because you are subscribed to the Google Groups
"Clojure" group.
To post to this group, send email to clojure@googlegroups.com
To unsubscribe from this group, send email to
clojure+unsubscr...@googlegroups.com
For more options, visit this group at
http://groups.google.com/group/clojure?hl=en
-~--~~~~--~~--~--~---
