# Round To Multiple

## Intro

Rounding is one of the recurring tasks.
While there are standard solutions (`std::round`

and friends) to “rounding floating-point to whole number”,
there is a more general class of rounding problems:

**Round integer N to multiple of integer M.**

For example, given `N = 17`

and `M = 10`

:

- Rounding up:
`20`

- Rounding down:
`10`

- Rounding to closest:
`20`

These “round-to-multiple” problems arise in many fields. For example, finance: the price of a security must be multiple of “tick size”.

## Problem

Our goal is to implement the following:

`int round_up(int n, int m)`

- Return the smallest multiple of
`m`

that is greater than or equal to`n`

- Return the smallest multiple of

Constraints:

`m > 0`

- The result is representable by the type
`int`

Once we have `round_up`

, we can implement the following as well:

`int round_dn(int n, int m)`

- Return the largest multiple of
`m`

that is less than or equal to`n`

- Return the largest multiple of
`int round_closest(int n, int m)`

- Return the multiple of
`m`

that is the closest to`n`

- Return the multiple of

## Solution

Let’s look at some existing solutions.

### The StackOverflow Solution 1

The top answer of this question
gives two versions. We’ll look at the simpler one that works for positive `numToRound`

only:

```
int roundUp(int numToRound, int multiple)
{
if (multiple == 0)
return numToRound;
int remainder = numToRound % multiple;
if (remainder == 0)
return numToRound;
return numToRound + multiple - remainder;
}
```

The last expression

```
numToRound + multiple - remainder
```

does the rounding up. It mostly works, but …

Consider `roundUp(2147483644, 5)`

(assuming `int`

is 32-bit).

Note that maximum value of signed 32-bit integer is `2147483647`

.
When we add `5`

to `2147483644`

, it overflows. In other words, we have undefined behavior.

The fix is simple - we subtract `remainder`

first:

```
numToRound - remainder + multiple
```

Now let’s look at the 2nd version, where `numToRound`

can be negative:

```
int roundUp(int numToRound, int multiple)
{
if (multiple == 0)
return numToRound;
int remainder = abs(numToRound) % multiple;
if (remainder == 0)
return numToRound;
if (numToRound < 0)
return -(abs(numToRound) - remainder);
else
return numToRound + multiple - remainder;
}
```

Unfortunately, even after the fix, it still overflows.

Consider `roundUp(-2147483648, 5)`

.
Applying `abs`

to `-2147483648`

overflows.

On my machine, this is even “worse” than the first case:

```
roundUp(2147483644, 5) = 2147483645 # while UB, the answer seems "correct"?
roundUp(-2147483648, 5) = 2147483645 # UB and wrong answer!
```

### The StackOverflow Solution 2+

Next, let’s took at the second answer:

```
int roundUp(int numToRound, int multiple)
{
assert(multiple);
int isPositive = (int)(numToRound >= 0);
return ((numToRound + isPositive * (multiple - 1)) / multiple) * multiple;
}
```

This is more concise and performant (`if`

branches are eliminated; potentially branchless).

However, it also overflows in the `roundUp(2147483644, 5)`

case.

On the other hand, this solution handle all negative `numToRound`

cases correctly.

There are many solutions of the form:

```
(numToRound + multiple - 1) / multiple * multiple
```

Sufficiently large `multiple`

will overflow `(numToRound + multiple - 1)`

.

### Alternative Approaches

Let’s try “reductionism” - reducing an unsolved problem to a solved problem:

```
int round_up(int n, int m) {
return std::ceil(double(n) / double(m)) * m;
}
```

I’ve seen solutions like this in production as well.

Set aside for efficiency considerations (floating conversion and floating math), this solution will run into different issues when we try to generalize it:

```
int64_t round_up(int64_t n, int64_t m) {
return std::ceil(double(n) / double(m)) * m;
}
```

Since `double`

cannot represent all `int64_t`

accurately,
when you feed it a sufficiently large `n`

, the result will be wrong.

### Can We Do Better?

A quick revision of integer division in C++ (and C):

Signed integer division truncates towards zero

Example:

`7 / 3 -> 2`

`-7 / 3 -> -2`

Note in the negative case - divide-then-multiply (`n / m * m`

) gives us exactly what we want!

When `n > 0`

, if `n`

is already a multiple of `m`

, the result is simply `n`

.

Otherwise, `n / m`

gets truncate down (per integer division rule),
and we need to compensate by adding *something* *somewhere*.

The previous solutions add `m - 1`

(or `m - remainder`

) to `n`

,
which triggers overflow when `n`

is close to maximum.

Therefore, instead we add `1`

to `n / m`

. And we’re done!

```
int round_up(int n, int m) {
if (n < 0) {
return n / m * m;
} else {
if (n % m == 0) {
return n;
} else {
return (n / m + 1) * m;
}
}
}
```

The above can be simplified into:

```
int round_up(int n, int m) {
return (n / m + ((n > 0) & bool(n % m))) * m;
}
```

### Rounding Down

Rounding down is symmetrical to rounding up:

- If
`n > 0`

, divide-then-multiply gives us what we want - If
`n < 0`

, we subtract 1 from the quotient if`n`

is not a multiple of`m`

```
int round_dn(int n, int m) {
return (n / m - ((n < 0) & bool(n % m))) * m;
}
```

### Rounding to Closest

What about `round_closest`

?

The answer in this StackOverflow Question:

```
((number + multiple/2) / multiple) * multiple;
```

shares similar overflowing issues, and the author pointed it out.

Let’s try reductionism again.

We know that the result is one of `round_up`

and `round_dn`

, whichever is closer to `n`

.
So, we can do it this way:

```
int round_closest(int n, int m) {
auto lo = round_dn(n, m);
auto hi = round_up(n, m);
// guaranteed that n is between [lo, hi]
return (n - lo < hi - n) ? lo : hi;
}
```

This works, with the added benefits that we can control precisely the behavior half-way cases. The above code rounds the halfway cases up. We can easily tweak it to “round down”, “towards zero”, or “away from zero”.

## Summary

Putting everything together:

```
template<class T>
T round_up(T n, T m) {
assert(m > T{0});
return (n / m + ((n > T{0}) & bool(n % m))) * m;
}
template<class T>
T round_dn(T n, T m) {
assert(m > T{0});
return (n / m - ((n < T{0}) & bool(n % m))) * m;
}
template<class T>
T round_closest(T n, T m) {
auto lo = round_dn(n, m);
auto hi = round_up(n, m);
return (n - lo < hi - n) ? lo : hi;
}
```