Alternative approaches to ceil()

Правка en1, от jeqcho, 2020-06-15 13:00:46

Sometimes we need to compute the division of an integer rounded up (ie by ceiling, not by rounding those with remainder $$$r \geq 0.5$$$). For example, $$$\lceil 3/2 \rceil = \lceil 1.5 \rceil = 2$$$ and $$$\lceil 13/3 \rceil = \lceil 4.333 \rceil = 5$$$.

TLDR, use (a+b-1) / b or other approaches below.

Typical approach

If we want to do this in C++, we can call the ceil() function, but with caution. For the example above,

int a = 3;
int b = 2;
cout << ceil(a/b) << endl;
>>>> 1

Note that it prints out 1, not 2! This is because a and b are int data types, so that their quotient a/b is in int and the decimal values are discarded (floored). a/b = 1 so ceil(a/b) = ceil(1) = 1. We can simply overcome this by casting the double data type so that the decimal values are kept during intermediate calculations.

cout << ceil( (double) a / (double) b) << endl;
>>>> 2

But wait! Some people think that using double is a risky approach because floating-point numbers cannot be reliably represented by computer, especially when you do more complex calculations than the simple a/b example. You can read more on this Stack Exchange question. Alternatively, there are many ways to use int only and still get the correct results.

Approach 1

Credit: zwliew, khoya_musafir

This is the most popular approach.

int ceil2(int a, int b) {
    return (a + b - 1) / b;
}

Approach 2

Credit: Flower08, BT21tata

(a - 1)/b + 1 is used instead of (a + b - 1) / b to prevent integer overflow when a and b is large. However, it does not work if $$$a = 0$$$, so we add an if statement.

int ceil2(int a, int b) {
    if (a == 0) return 0;
    return (a - 1)/b + 1;
}

Approach 3

Credit: KB_05

int ceil2(int a, int b) {
    int c=a/b;
    if(a % b ! =0) c++;
    return c;
}

Approach 4

int ceil2(int a, int b){
    int c = a / b;
    if (c * b < a) c++;
    return c;
}

I hope that you find this useful. Feel free to add more approaches in the comments.

Thank you and stay safe.

Теги ceil, ceiling, divisibility, floor, double, floating-point, quotient

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en1 Английский jeqcho 2020-06-15 13:00:46 2388 Deleted first blog and organised the new approaches (published)