How to reduce division with uprounding to integer-arithmetic operations with downrounding if the denominator is not necessarily an integer?

18 Views Asked by At

Let ∈ℕ₀ be an unknown variable and ∈ℚ₊ be a known constant such that ≥2 and 100 ∈ ℕ₊. (So we can pre-compute anything regarding , e.g., represent 100 as a product of powers of primes.) We would like to compute $\left\lceil\frac{}{}\right\rceil$. At our disposal we have only operations on integers with downrounding: addition, subtraction, integer multiplication, integer division div ($(a\, \mathrm{div}\, b) = \left\lfloor\frac{a}{b}\right\rfloor$), and taking the remainder after integer division rem ($(a\,\mathrm{rem}\,b) = a - (a\,\mathrm{div}\,b)b$). If were an integer, we'd compute (+-1) div = $\left\lfloor\frac{+-1}{}\right\rfloor$. In our setup, is NOT known to be an integer — only 100 is. What to do?