simplify expression k/m%n

Question

hello.

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

I suppose that it depends. A right arithmetic shift would give you division by 2 and with some additional arithmetic you could make that into a division by any number. Similarly I would think that you could do the same with the modulo operator. In reality, unless your processor is lacking the necessary hardware, I wouldn't have thought that you would gain anything.

edit Actually thinking about it, more thought is needed here as strictly speaking, for a negative number a signed shift wouldn't work as a divide by 2.

If I remember rightly the behaviour of an arithmetic shift right is undefined in the C standard for negative numbers (it talks about powers of 2) and so is compiler dependent.

If we're just thinking about the logic of number theory then that's a different matter. Let me think on it.

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

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 5

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);