simplify expression k/m%n

Question

Simple question, is it possible to simplify (or replace division or modulo by less-expensive operation)

(k/m)%n

where variables are integers and operators are C style division and modulo operators.

let me rephrase question slightly, except for case where variables are base2, under what conditions (e.g. some variable may be constant) can expression be simplified (or rephrased partially using base2 operations) to remove the division or modulo?

this is way for me to learn number theory, especially base2 tricks, rather than exercise in performance optimization

Thank you

Answer 1

For division with small constant denominator, you can use something like this.

k/m=k*(1/m)
x=(1<<16)/m
k/m=(k*x)>>16

The answer may not be precise depending on the inputs.

For division with small odd constant denominator, you can use the multiplicative inverse. The following constants apply to 32 bit division.

3   2863311531      11  3123612579
5   3435973837      13  3303820997
7   3067833783      15  4008636143
9    954437177      17  4042322161

x/11 == x*3123612579 % 2^32

The % 2^32 is of course free on 32 bit integers. To adopt this to even numbers factor out the twos and apply them later.

x/44 == (x*3123612579 % 2^32) >> 2

Hackers Delight has a chapter on integer division.

The simple modulus and division for powers of two.

x%m == x&(m-1)
x/m == x>>log2(m) // assumes log2(m) is known, not calculated

Answer 2

For arbitrary-precision integers, I recommend looking at http://documents.epfl.ch/users/k/ka/kaihara/www/papers/ModMulDiv_Binary.pdf

It presents a hardware approach, but it gives pseudocode that you can adapt.

Answer 3

Obvious optimisations:

1. m == 1 : The answer will just be k % m.
2. n == 1 : The answer is always 0.
3. m is a power of 2 : e.g. if m is 4, you can use (k >> 2) % n;
4. n is a power of 2 : expression becomes (k / m) & (n - 1);

Checking for #1 and #2 is trivial.

Checking for powers of two is done using:

void isPowerOfTwo(unsigned int x)
{
    return x & (x - 1) == 0;
}

Answer 4

Adding to Peter Alexander's answer

0) Of course m != 0 && n != 0 are pre-conditions...

1) k < m : The answer is always 0

2) k == m : The answer is always 1 (unless n is also 1, see 5.)

3) k / m < n: The answer is k / m

4) k < ( m * n ): The answer is always k / m. This particular condition is not very conducive to optimization since m*n would not be reused and it should not be much faster than modulo unless m and/or n are powers of 2 in which case you'd still be better using 7. and/or 8.

For reference adding Peter Alexander's:

5) m == 1 : The answer will just be k % n.

6) n == 1 : The answer is always 0.

7) m is a power of 2 : e.g. if m is 4, you can use (k >> 2) % n;

8) n is a power of 2 : expression becomes (k / m) & (n - 1);