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.

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.

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.

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

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.

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.

yeah docs could be way better

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.

cool suggestion

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.

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.)

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.

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.

x / d + u32::from(x % d == 0)

Incorrect. It should be: x / d + u32::from(x % d != 0)

@kaan-atakan

I agree that this should be a method. @kaan-atakan are you ok with that and can you update the title of this request?

This will be fixed by rust-lang/rust#88581.

round-toward-infinity. expanding division.

Javascript has a "rounding mode" at Intl namespace called expand. More info here

rust-lang/rust#94455 probably closes this?

Navigation Menu

Repository navigation

Integer division method or operator that rounds up #2844

Metadata

Assignees

Labels

Type

Projects

Milestone

Relationships

Development

Integer division method or operator that rounds up #2844

Description

Activity

Mark-Simulacrum commented on Jan 6, 2020

CryZe commented on Jan 6, 2020

clarfonthey commented on Feb 2, 2020

kevincox commented on May 14, 2020

burdges commented on May 14, 2020

Lokathor commented on May 14, 2020

kevincox commented on May 14, 2020

badkk commented on Jul 2, 2020

clarfonthey commented on Jul 2, 2020

scottmcm commented on Nov 10, 2020

osa1 commented on Mar 12, 2021

JMurph2015 commented on Mar 17, 2021

usr345 commented on Apr 10, 2021

kevincox commented on Aug 28, 2021

osa1 commented on Sep 5, 2021

Rudxain commented on Jul 26, 2022

samsieber commented on Jan 24, 2024

Metadata

Metadata

Assignees

Labels

Type

Projects

Milestone

Relationships

Development

Issue actions