# "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](http://en.wikipedia.org/wiki/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.