rfcs Integer division method or operator that rounds up

Sometimes we want do divide an integer by another integer and round up the result to next integer. For example we might want to know how many write operations of a specific size are required to fully write a file of a specific size.

Regular integer division in such scenarios will result in a value that is 1 below the desired result for all operations that involve a remainder and correct for those that don't. There are typically three methods used to calculate such a value:

cast to a floating point and subsequently round up
do the integer division, then check if the modulo produces a remainder and add one in that case
and finally (dividend + divisor - 1) / divisor

The final method while being efficient is not the most readable. Not only can it get very long if we use long and descriptive variable names like:

(data_file_size + max_write_length - 1) / max_write_length

but it's not quite so obvious what we are doing. For this reason I suggest adding the operator +/ so the same operation can be written as such:

data_file_size +/ max_write_length or dividend +/ divisor

Although such operations almost always only make sense for positive integers. One might consider also adding additional operators -/, /- and -/- to deal with situations where it is known before hand that, respectively, the dividend, divisor or both are negative to avoid unnecessary calls to the absolute value function.

Jan 06 '20 14:01 kaan-atakan

Such an operator would, at minimum, need an RFC, however, I'd guess that it's not infeasible to add the basic idea (though not the extension operators) as a method to the integer primitives (in an unstable fashion). Such an addition should go through a normal PR, though.

I've moved this over to the RFCs repository as an issue.

Jan 06 '20 15:01 Mark-Simulacrum

Yeah I'd suggest just naming this u32::ceiling_div or so. That would nicely extend the already existing saturating_, wrapping_, checked_ variants of the normal operators.

Jan 06 '20 15:01 CryZe

Considering how there are an infinite number of ways to round division, I'd strongly recommend against adding another because we already have truncating and Euclidean division.

If we were to add a version of this, it'd definitely make the most sense to do round-away-from-zero rather than ceiling division. We decided upon Euclidean instead of flooring division, and offering ceiling division begs the ability to add flooring, and...

I hate slippery slope arguments, but it sure seems slippery around here

Feb 02 '20 23:02 clarfonthey

I'm not so sure. You described maybe 4 options. It seems like there isn't actually much to do here. There is round up, round down, round even, round to zero and round away from zero. We have two of these already and adding flooring and ceiling sound like obvious wins.

These are things that are not as effective as implemented outside of the standard library, will cause minimal if any maintenance burden and are beneficial to use a common language across all projects.

May 14 '20 19:05 kevincox

You'd implement this with either (x+d-1) / d or x / d + u32::from(x % d == 0) I guess, not sure if the second optimizes into the first. Meh

We need better literate programming tools for std that produce collapsible subdivisions with local introductory text, so when you say open up the saturating section you get some broader explanation.

May 14 '20 20:05 burdges

yeah docs could be way better

May 14 '20 20:05 Lokathor

Yeah, you would implement it like that. But the point is that it isn't obvious what you are doing.

Real world example:

I wanted to write:

target_x.saturating_sub(self.x()).ceiling_div(Self::max_speed() as u32) as u16

Instead I had to write:

let distance = target_x.saturating_sub(self.x());
// Ceiling division.
((distance + Self::max_speed() as u32 - 1) / Self::max_speed() as u32) as u16

Which would you rather read? I would say that the intent of the top one is much more clear. Even though I tried to make it more clear by separating the distance calculation into it's own line and added a comment.

May 14 '20 23:05 kevincox

cool suggestion

Jul 02 '20 08:07 badkk

As stated, we definitely should be adding a round-toward-infinity function instead of a ceiling function, if we were to do so at all. Maybe call it expanding division.

Jul 02 '20 19:07 clarfonthey

Note that this is available in the ecosystem with Integer::div_ceil.

(Marking libs because it's highly unlikely that a new operator would be added for this, just new methods.)

Nov 10 '20 21:11 scottmcm

This is a very common operation when implementing allocation routines. For example, in a language runtime, often you can only allocate words, but you still want to provide an API that takes bytes as argument. The conversion is then done with (bytes + WORD_SIZE - 1) / WORD_SIZE (or (bytes - 1) / WORD_SIZE + 1 to avoid overflow, but this overflow would often be checked before this operation).

I've seen this operation in three different code bases so far.

One of them was method (1) in the original post. When you see this code it's obvious what it's doing, but it's not ideal because it potentially suffers from floating point inaccuracies.
Two of them were method (3). This method warrants a comment because unless you're already familiar with it, it's not clear what the code is doing.
(I've never seen method (2) used in practice)

So I think having a method for this with would be really helpful because (1) it's a common operation in some domains (2) all existing solutions have problems that having a method for this would solve.

I think this is not common enough to require an operator. A method would be fine.

Mar 12 '21 09:03 osa1

An operator seems like substantial overkill to me. Usually I've seen method (2) in practice, and it's always pretty obvious what's being done (but usually not obvious why it's necessary, which this RFC doesn't solve anyway). Write a helper method if your codebase uses this with any substantial frequency like upper_int_div.