Integer division that rounds up: Difference between revisions
(→Proof) |
(→Proof) |
||
| Line 11: | Line 11: | ||
'''Part 1'''. If <math>y</math> divides <math>x</math> we have <math>x=ay</math> for some <math>a\in\mathbb N_+</math>. Thus we have | '''Part 1'''. If <math>y</math> divides <math>x</math> we have <math>x=ay</math> for some <math>a\in\mathbb N_+</math>. Thus we have | ||
<math> | <math> | ||
\begin{align} | \begin{align} | ||
\left \lceil \frac{x+y-1}{y} \right \rceil | \left \lceil \frac{x+y-1}{y} \right \rceil | ||
= | &= | ||
\left \lceil \frac{x}{y} + \frac{y-1}y \right \rceil \\ | \left \lceil \frac{x}{y} + \frac{y-1}y \right \rceil \\ | ||
= | &= | ||
\left \lceil \frac{ay}{y} + \frac{y-1}y \right \rceil \\ | \left \lceil \frac{ay}{y} + \frac{y-1}y \right \rceil \\ | ||
= | &= | ||
\frac{ay}{y} \\ | \frac{ay}{y} \\ | ||
= | &= | ||
\frac{x}{y} | \frac{x}{y} | ||
\end{align} | \end{align} | ||
</math> | </math> | ||
because <math>0 \leq \frac{y-1}y < 1</math>. This is ok. | because <math>0 \leq \frac{y-1}y < 1</math>. This is ok. | ||
Revision as of 10:08, 8 July 2024
Introduction
Usual integer division rounds down: for . To round up (if overflow is not an issue), you can use following algorithm with the usual roundig down division: Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle q = \frac{x+y-1}{y} = \left \lceil \frac xy \right \rceil }
Proof
Proof is in two parts; 1st if Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle y} divides Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x} , and if not. Note that usual integer division rounds down.
Part 1. If Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle y} divides Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x} we have Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x=ay} for some Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle a\in\mathbb N_+} . Thus we have
Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \begin{align} \left \lceil \frac{x+y-1}{y} \right \rceil &= \left \lceil \frac{x}{y} + \frac{y-1}y \right \rceil \\ &= \left \lceil \frac{ay}{y} + \frac{y-1}y \right \rceil \\ &= \frac{ay}{y} \\ &= \frac{x}{y} \end{align} } because Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 0 \leq \frac{y-1}y < 1} . This is ok.
