"Integer Division" and Modulo

An interesting programming language/library design choice recently came to my attention, and that is how to handle integer division and remainder for negative numbers.

The two common approaches for stripping the fractional part off a negative quotient are either to "truncate" towards zero, or to "floor" towards negative infinity.

Example:

-5/2 = -2.5
floor(-2.5) = -3
trunc(-2.5) = -2

The remainder of a/b given a integer conversion function int (either floor or trunc) must satisfy the equation:

remainder(a/b) + int(a/b)*b = a

Using floor this breaks down using substitution like this:

remainder(-5/2) + floor(-5/2)*2 = -5
remainder(-5/2) + floor(-2.5)*2 = -5
remainder(-5/2) + -3*2 = -5
remainder(-5/2) + -6 = -5
remainder(-5/2) = -5 + 6 = 1

Using trunc:

remainder(-5/2) + trunc(-5/2)*2 = -5
remainder(-5/2) + trunc(-2.5)*2 = -5
remainder(-5/2) + -2*2 = -4
remainder(-5/2) + -4 = -5
remainder(-5/2) = -5 + 4 = -1

One thing to observe is that if we use trunc the result is negative if the divison's left-hand operator or "top" or dividend is negative, but using floor the result is always positive if the divisor is positive. This is, in fact, how they split the modulo function on Wikipedia - whether the sign of the modulo matches the dividend or divisor.

Having the sign of the modulo result match the divisor is nicer when you are using the modulo operator. This is because we often forget to check for negative numbers, so we might do an operation like:

dayOfWeek = daysSinceReferenceMonday % 7

Using the trunc method of integer division, this may result in a negative day of the week number.

The floor method of integer division, on the other hand, favors division. Compare these results:

floor(5 / 2) * -1 == -2 ; floor(-5 / 2) == -3
trunc(5 / 2) * -1 == trunc(-5 / 2) == -2
floor(-5 / 2) + floor(5 / 2) == -1
trunc(5 / 2) + trunc(-5 / 2) == 0

Notice how the order of operations can lead to off-by-one errors when using the floor style integer division.

As one can see, the floor technique is better for modulo and the trunc technique is better for division.

Languages can easily provide both operations but the nice operator shorthand % will have to pick one, and if there's a matching / or // operator for integer division it should probably match, just in case the two are used together in the same code.

Euclidean division

I stumbled on this paper on the matter which describes a third and better looking option, called "Euclidean division":

http://legacy.cs.uu.nl/daan/download/papers/divmodnote.pdf

Euclidean division always results in a positive remainder, and can be calculated as:

a/b = sign(b) * floor(a/|b|)

Does it solve the problems with floor based division?

divE(5,2) * -1 == -2, where divE(-5,2) == -3

So, not really. But it may be better than the floor based division in some ways. Read this paper here for the argument in favor of this kind of integer division:

https://biblio.ugent.be/input/download?func=downloadFile&recordOId=314490&fileOId=452146

Church Encoding is like the Visitor Pattern

Church Encoding is like the visitor pattern, especially for booleans, lists, and so on.

Boolean is the most obvious - a Church Boolean is a function that takes two functions, one to call if the boolean is true and one to call if the boolean is false. The visitor pattern version would be for boolean to accept a visitor with two methods.

For lists there are a few alternate variations in lambda calculus, but it's not hard to imagine a visitor pattern implementation that calls back to an empty nullary visitor or a nonEmpty binary visitor method.