floored division, variadic mod

[primo-ppcg]

Consistent modular arithmetic

A modular arithmetic is said to be consistent if the following property holds for any a and non-zero b:

(= a (+ (* (div a b) b) (mod a b)))

where div represents an appropriate integer division. From the C99 standard onward, modular arithmetic is consistent, and therefore also with Janet int types:

(for a (int/s64 -99) (int/s64 100)
  (for b (int/s64 -99) (int/s64 100)
    (unless (compare= b 0)
      (assert (= a (+ (* (/ a b) b) (% a b)))))))

I find this usage to be intuitive. What isn't so intuitive is when using the default numeric type:

(def quo (comp math/trunc /))
(def div (comp math/floor /))
(for a -99 100
  (for b -99 100
    (unless (= b 0)
      (assert (= a (+ (* (quo a b) b) (% a b))))
      (assert (= a (+ (* (div a b) b) (mod a b)))))))

in particular that % is consistent with truncated division may not be expected. Defining integer division in this way is also very slow. It can also be defined like this:

(defn div [a b] (math/floor (/ a b)))

which is a lot faster, but no longer variadic. I've found it's best to inline math/floor everywhere, which can get a bit messy. I think it would be useful to add a floored division (div) which is consistent with mod. I don't know that it's necessary to have a symbolic truncated division that agrees with %; in most cases, you would want to be using div and mod anyway, or at very least it would be sufficient.

Mod zero

Modulo zero is a well-defined mathematical operation. Two values a and b are said to be equivalent mod m if there exists some integer k for which a = b + k·m. To state that a is equivalent to b mod 0 is to state that a is equal to b, and nothing more. Programming languages that care very much for mathematical correctness (APL, J, K, others) all agree that x mod 0 = x, because it is. Even Donald Knuth agrees. I'm not saying that Janet must necessarily do this (and given that the default numeric type is IEEE floating point, very probably shouldn't), but I am saying that it is correct, and relevant to the next point.

Variadic mod

mod is the only arithmetic function that isn't variadic, and seems to have been unnecessarily singled out in that regard. For two or more arguments, the behavior is clear. For a single argument, the first argument should be taken as 1, in agreement with division, such that the following is true for any non-zero b:

(= 1 (+ (* (div b) b) (mod b)))

Without arguments, it should return the operator identity as all other arithmetic functions do, which as established in the previous point is 0.

---

I've prepared an implementation for both floored division and variadic mod on my local fork for the purpose of testing/review.

Throughout the implementation, I refer to floored division as either DIVIDE_FLOOR or divf as appropriate. The result is much faster than any current alternatives:

(defn div [a b] (math/floor (/ a b)))
(timeit-loop [i :range [0 100_000_000]]
  (div i 7))
# ->
Elapsed time: 5.381s, 0.05381µs/body

(timeit-loop [i :range [0 100_000_000]]
  (math/floor (/ i 7)))
# ->
Elapsed time: 2.661s, 0.02661µs/body

(timeit-loop [i :range [0 100_000_000]]
  (div i 7))
# ->
Elapsed time: 1.290s, 0.0129µs/body

[sogaiu]

I gave the fork a try and got numbers similar to what was reported.

Regarding:

For a single argument, the first argument should be taken as 1, in agreement with division, such that the following is true in any case:

(= 1 (+ (* (div b) b) (mod b)))

one thing I noticed was:

(seq [b :range-to [-2 2]]
  [b (= 1 (+ (* (div b) b) (mod b)))])
# =>
'@[(-2 true) 
   (-1 true) 
   (0 false) 
   (1 true)
   (2 true)]

but earlier there was this remark:

A modular arithmetic is said to be consistent if the following property holds for any a and non-zero b:

(= a (+ (* (div a b) b) (mod a b)))

...so may be there was an implied non-zero b :)

[primo-ppcg]

...so may be there was an implied non-zero b :)

Yes, that's right. Generally, "floored reciprocal" would only make sense for values between -1 and 1, excluding zero.

[bakpakin]

These changes look good to me and floored division (integer division) is certainly a useful core language feature. It might also be worth looking at defining (mod x 0) to be x as suggested.

[primo-ppcg]

It might also be worth looking at defining (mod x 0) to be x as suggested.

I agree that it makes sense for mod, but probably not for remainder. I believe that remainder is defined in terms of division, and not a separate mathematical construct of its own.