Integer division that rounds up

Introduction

Usual integer division rounds down: ${\frac {a}{b}}=\left\lfloor {\frac {a}{b}}\right\rfloor$ for $a,b\in \mathbb {N} ,b\neq 0$. To round up (if overflow is not an issue), you can use following algorithm with the usual roundig down division: $q={\frac {x+y-1}{y}}=\left\lceil {\frac {x}{y}}\right\rceil$

Proof

Proof is in two parts; 1st if $y$ divides $x$, and if not. Note that usual integer division rounds down.

Part 1. If $y$ divides $x$ we have $x=ay$ for some $a\in \mathbb {N} _{+}$. Thus we have

${\begin{aligned}\left\lfloor {\frac {x+y-1}{y}}\right\rfloor &=\left\lfloor {\frac {x}{y}}+{\frac {y-1}{y}}\right\rfloor \\&=\left\lfloor {\frac {ay}{y}}+{\frac {y-1}{y}}\right\rfloor \\&={\frac {ay}{y}}\\&={\frac {x}{y}}\end{aligned}}$

because $0\leq {\frac {y-1}{y}}<1$. This part is ok.

Part 2. If $y$ does not divide $x$ we have $x=by+r$ for some $b\in \mathbb {N} _{+}$ and $0<r<b$. Thus we have

${\begin{aligned}\left\lfloor {\frac {x+y-1}{y}}\right\rfloor &=\left\lfloor {\frac {x}{y}}+{\frac {y-1}{y}}\right\rfloor \\&=\left\lfloor {\frac {by+r}{y}}+{\frac {y-1}{y}}\right\rfloor \\&=\left\lfloor {\frac {by}{y}}+{\frac {r}{y}}+{\frac {y}{y}}-{\frac {1}{y}}\right\rfloor \\&=\left\lfloor {\frac {by+y}{y}}+{\frac {r-1}{y}}\right\rfloor \\&=\left\lfloor {\frac {(b+1)y}{y}}+{\frac {r-1}{y}}\right\rfloor \\&={\frac {(b+1)y}{y}}\\\end{aligned}}$

Which is one greater (the ceiling).

Combine the results, and we have $\left\lfloor {\frac {x+y-1}{y}}\right\rfloor =\left\lceil {\frac {x}{y}}\right\rceil$ which was the question.

References

https://math.stackexchange.com/questions/2591316/proof-for-integer-division-algorithm-that-rounds-up

For more details, see Algorithmic problem solving by R Backhouse 2011, Exercise 15.12 (following the definition 15.22).