Is there a faster way to compute $\left\lfloor{(k + 1)m \over n}\right\rfloor - \left\lfloor {km\over n}\right\rfloor$?

Question

I'm looking to compute the integer difference between the $k$th and $(k+1)$th multiples of a fraction, i.e.

$$\left\lfloor{(k + 1)m \over n}\right\rfloor - \left\lfloor {km\over n}\right\rfloor$$

where all variables are positive integers (and they're not predetermined constants).

I'm already speeding this up by doing $km + m$ instead of $(k + 1)m$ so that I can factor out $km$, but unfortunately, this computation requires two integer divisions, and integer division is quite slow.

Is there a faster way to compute the same exact value?
I feel like the simplicity of the problem might admit a simple solution, but for some reason I'm not seeing one.

Answer 1

Provided the $\bmod$ operation is faster on whatever platform you'll be running your algorithm (it usually is), then $$\require{cancel} \frac{(\cancel{km}+m)-((km+m)\bmod n)-\cancel{km}+(km\bmod n)}{n} $$ matches your expression with just one integer division. In fact, the numerator must be a multiple of $n$. This is just an application of this formula $$ \left\lfloor \frac{x}{y} \right\rfloor y = x - (x \bmod y) $$ which is valid for positive $y$.

Answer 2

My method has the following set up:

1. Calculate $a=m\ mod\ n$
2. Check the sign of $\left(a(k+1) \ mod\ n -a\right)$
3. If its $\geq 0$, then $\frac{m-a}{n}$ is the answer
4. Otherwise, (if $<0$) its $\frac{m-a}{n}+1$

I hope it suits your needs.

Answer 3

Most processors have a command to compute div and mod at the same time (2 for the price of 1). Check your manual. For example: https://en.cppreference.com/w/cpp/numeric/math/div

So you can do

(a, b) = div_mod(k*m, n)
b += m
while b >= n {
    b -= n
    a += 1
}
return a

If you know the relation between m and n in advance, then you can do:

z = m/n*n
------------
(a, b) = div_mod(k*m, n)
b += (m - z)
a += (b >= n)
return a

But notice each line has a write-read dependency with the command before it. So it might actually be faster to just computer the result with 2 modulus since that can be done in parallel. You just have to test it.

But the best thing would be to know what you are actually doing, for example if you are looping over k, then the div_mod can probably be skipped altogether.