builtin functions for integer division and remainder division

[andrewrk]

let's define the modulus operator to be euclidean mod. here is some pre-written justification: https://eev.ee/blog/2016/12/01/lets-stop-copying-c/#negative-modulo

We can provide an implementation that achieves this regardless of what instructions are actually available on the system.

If a programmer wants to use a modulus that has undefined behavior for a negative operand, we can provide a builtin for that, and it can have a debug safety check.

[andrewrk]

Proposal:

• remove % binary operator
• add @rem(a, b) builtin function that does remainder division. This is equivalent to % in C (and status quo zig). This has debug safety features for division by zero and overflow. @rem(-5, 3) is -2.
• add @mod(a, b) builtin function that does euclidean modulus. This is equivalent to % in Python. @mod(-5, 3) is 1.

[thejoshwolfe]

@rem(a, b) should assert b > 0. In C, % with a negative denominator is undefined behavior (actually bounded, implementation-defined behavior).

Trying to think of any objections, I suppose I could point out that the name "rem" is somewhat ambiguous. In Batch, "rem" is short for "remark" and starts a single-line comment, but I really don't think we need to worry about that. I do think that out of context, "rem" is usually short for "remove" rather than "remainder", but perhaps the context would be enough to clarify the meaning of the Zig function.

I like the @mod(a, b) proposal, but it's actually not completely specified yet. Python's % is not euclidean modulo. wikipedia calls it "floored division", because the result has the same sign as the divisor. Euclidean modulo always has a positive result.

My hunch of what we should do is make @mod(a, b) also assert b > 0 to avoid all this confusion. Then the important difference between @rem and @mod is when a is negative. I believe I have never in my programming career wanted a negative divisor for a modulo operation, which is partly why I'm proposing this restriction.

So here's a completely specified definition of both functions:

• @rem(a, b): assert(b > 0). Return @sign(a) * @mod(@abs(a), b).
• @mod(a, b): assert(b > 0). Return an integer n such that (0 <= n) && (n < b) && (k * b + n == a) for some integer k.

(Mathematically, @rem is more complicated than @mod, but I believe @rem is easier to implement in hardware.)

Speaking of "some integer k", that's actually the result of floored division. Is the / operator defined as floored division or as C's truncate-toward-zero division? In my programming career, every single time I've wanted modulo with a negative a, I've also wanted floored division at the same time. Do we have a floored division builtin in Zig? As with euclidean modulo, it can be implemented in userspace with enough ifs, but it may be strange to include a builtin for @mod without the corresponding division operation.

[thejoshwolfe]

Here's a radical proposal: allow a / operator for division, but only for floats not integers (reminder that there's no automatic coercion between integers and floats), since float division works very similar to how it works in math, but integer division is more mathematically complicated.

For integer division, we add builtin functions for different variants:

• @divTrunc(-5, 3) == -1: this is llvm's sdiv (or udiv).
• @divFloor(-5, 3) == -2: a little more complicated to implement, but pairs nicely with @mod.
• @divExact(-6, 3) == -2: asserts there is no remainder. this is llvm's sdiv exact.

Negative divisor cases for division (as opposed to remainder) are pretty well defined by math. In all variants of integer division a/b == -a/-b && sign(a/b) == sign(a) * sign(b) (assuming assert(b != 0) and no overflow).

We could also do a @divCeil(5, 3) == 2, but I don't think that's necessary. I also looked into some round-to-nearest division ideas, but there are way too many ways to resolve .5 cases, so that's definitely not a good idea for a builtin function.

Here's my worksheet to make sure the above proposal is coherent:

• @divTrunc(-5, 3) == -1, @divTrunc(5, -3) == -1
• @divTrunc(5, 3) == 1, @divTrunc(-5, -3) == 1
• @divFloor(-5, 3) == -2, @divFloor(5, -3) == -2
• @divFloor(5, 3) == 1, @divFloor(-5, -3) == 1

Here's a userland implementation of @divFloor:

fn divFloor(a: i32, b: i32) -> i32 {
    %%divFloorOverflow(a, b)
}
fn divFloorOverflow(a: i32, b: i32) -> %i32 {
    assert(b != 0);
    if (b < 0) {
        // canonicalize the sign of the divisor
        return divFloorOverflow(
            // note that some "overflow" cases might actually be capable of returning mathematically correct results,
            // but it's easier for implementations to define division such that negation overflow cases are also overflow cases for the division.
            %return math.mulOverflow(a, -1),
            %return math.mulOverflow(b, -1),
        );
    }
    if (a >= 0) {
        // we've already checked for negative b, so overflow cannot happen here
        return @divTrunc(a, b);
    } else {
        return -@divTrunc(
            // see above comment about overflow
            %return math.addOverflow(
                %return math.mulOverflow(a, -1), b - 1),
            b,
        );
    }
}

Here are test cases that hit each of the %returns in the above code. These are all cases where the overflow could be considered "unfair", since there is a mathematically correct answer that the algorithm didn't figure out.

• @divFloor(-0x80000000, -2): overflow, even though 0x40000000 is mathematically correct.
• @divFloor(0, -0x80000000): overflow, even though 0 is mathematically correct.
• @divFloor(-0x40000001, 0x40000000): overflow, even though -0x80000000 is mathematically correct.
• @divFloor(-0x80000000, 1): overflow, even though -0x80000000 is mathematically correct.

[andrewrk]

This proposal goes nicely with the modulus/remainder proposal.

An alternate set of proposals:

• Keep % and / operators for integers. Have them be floored modulus and floored division, respectively, the idea being that this is what programmers want, almost every time.
• Add @rem and @divTrunc as described.

[thejoshwolfe]

Is it safe to claim (in a Zig user guide, for example) that @divTrunc and @rem have better performance than @divFloor and @mod? For reference, LLVM IR only has primitive functions for the former, not the latter. So as long as Zig is backed by LLVM, it seems like a pretty safe claim.

With that in mind, I'm not comfortable encouraging users to use slower functions when they might know that they don't need the negative cases at all. One happy coincidence of my proposal above is that all three functions have the same size name. This means Zig is not biasing programmers to use any of them over the others. As an additional bonus, when programmers find out that there's no / operator for integers, they'll discover all three division functions at once. This way Zig is encouraging users to know what they're doing instead of encouraging users to do what Zig thinks they should be doing.

It might be worth noting that for unsigned integers, @divTrunc and @divFloor are identical. I argue that this doesn't violate orthogonality though, because we want the functions to work when the integer type is generic, and we don't want generic functions to have to use a different function depending on the signedness of a caller-supplied type.

[andrewrk]

Is it safe to claim (in a Zig user guide, for example) that @divTrunc and @rem have better performance than @divFloor and @mod? For reference, LLVM IR only has primitive functions for the former, not the latter. So as long as Zig is backed by LLVM, it seems like a pretty safe claim.

I agree with your reasoning here, and I think this is a pretty good argument for accepting your proposal, where integer division is done via builtin functions, not the / operator.

[andrewrk]

One more thing: should we allow / for unsigned integers and positive number literals, since @divTrunc and @divFloor are identical?

[thejoshwolfe]

should we allow / for unsigned integers and positive number literals, since @divTrunc and @divFloor are identical?

More generally, we could allow / when @divTrunc and @divFloor would be identical, such as diving a slice.len by a @sizeOf.

But that actually leaves out @divExact. In the case of slice.len / @sizeOf(T), it seems like @divExact might be a better fit than @divTrunc. Do we even want to bother with @divExact? I only propose it because LLVM IR supports it, and it seems useful in some cases, but we can definitely do without it.

[andrewrk]

Fun fact, we already have @divExact and it works exactly as you proposed.

[thejoshwolfe]

Fun fact, we already have @divExact and it works exactly as you proposed.

Nice. So that leaves the question of if we should allow / to mean @divTrunc or @divFloor but not @divExact. Even for positive integers, there's still two different definitions of division, so do we want a / operator to chose one of them and not the other?

I'll throw in the elephant in the room argument, which is that the / operator works fine in Java, C, Go, Python 2 (not Python 3), etc., and people expect it to work, so we might be upsetting a lot of programmers by making it difficult to do truncating integer division with positive numbers.

All that being said, I like the idea of making programmers choose between @divTrunc and @divExact. It seems pretty hostile, so maybe I'd like to try subjecting myself to it before I really say that it's a good idea.

Let's take a look at some "real world" Zig code for inspiration: https://github.com/andrewrk/tetris/blob/91dfddb6c96245429737b0b402b8ea67c49a8510/src/main.zig#L337

This is code to center the display of text by dividing the pixel width of the text in half and the width of the display area in half. What happens if either of these widths is odd? In that specific case, neither can be odd, so @divExact would be slightly more optimal. In the case of centering the display of something, it's also sometimes a good idea to stick with float pixel coordinates and do anti-aliasing to make the thing appear actually centered. Or if you don't want that effect on your pixels, you could do @divTrunc to make sure the display is pixel-aligned (shifting to the left if needed, unless your width is negative, then shifting to the right, or if you use @divFloor, then shifting to the left all the time).

The above (admittedly specific) usecase demonstrates that there are many possible things that you could mean when doing something as simple as centering the display of something. My mandatory verbosity proposal makes that slightly more clear to a code reader. But is it worth it? Again, I don't feel comfortable making a judgement call until I subject myself to the pain to see how it feels.

[thejoshwolfe]

Fun fact: @divFloor(a, b) can be more efficient than @divTrunc(a, b) when b is known at compile time and is a power of 2. @divFloor(a, 2^n) == a >> n. This means that the most concise syntax in the above example would actually be score_left + (score_width >> 1) - (score_label_width >> 1) rather than specifying any @div*() function. I'm not sure how that affects the situation, but it's worth keeping in mind.

[andrewrk]

To recap, here are the changes going forward:

• remove % binary operator and %= binary operator for signed integers. Unsigned integers and floats can still use %, or the below functions.
• add: @rem(a, b): assert(b > 0). Return @sign(a) * @mod(@abs(a), b).
• add: @mod(a, b): assert(b > 0). Return an integer n such that (0 <= n) && (n < b) && (k * b + n == a) for some integer k.
• remove / binary operator and /= binary operator for signed integers. Unsigned integers and floats can still use /, or the below functions.
• add: @divTrunc(-5, 3) == -1: this is llvm's sdiv (or udiv). Which is what / for signed integers used to do.
• add: @divFloor(-5, 3) == -2: a little more complicated to implement, but pairs nicely with @mod.
• no change / already exists: @divExact(-6, 3) == -2: asserts there is no remainder. this is llvm's sdiv exact.

[andrewrk]

@thejoshwolfe

@divFloor(-0x40000001, 0x40000000): overflow, even though -0x80000000 is mathematically correct.

Did you mean -2 should be the correct answer?

[thejoshwolfe]

yes. i still think that case hits the overflow i intended though. there's an intermediate result of 0x80000001 in there i think.

[andrewrk]

Here's my divFloor implementation. I believe it does not have the overflow problems:

fn divFloor(comptime T: type, a: T, b: T) -> T {
    const result = @divTrunc(a, b);
    if (result >= 0 or result * b == a)
        return result;
    else
        return result - 1;
}