asked on

How to compute the modulus of a number without a division operator ?

Hi Folks,

This is another of the ones which I am not being able to understand :

Compute modulus division by (1 << s) - 1 without a division operator

unsigned int n; // numerator
const unsigned int s; // s > 0
const unsigned int d = (1 << s) - 1; // so d is either 1, 3, 7, 15, 31, ...).
unsigned int m; // n % d goes here.

for (m = n; n > d; n = m)
{
for (m = 0; n; n >>= s)
{
m += n & d;
}
}
// Now m is a value from 0 to d, but since with modulus division
// we want m to be 0 when it is d.
m = m == d ? 0 : m;

Any help is greatly appreciated.

Thanks,
H

ASKER CERTIFIED SOLUTION

ozo

membership

Create a free account to see this answer

Signing up is free and takes 30 seconds. No credit card required.

See answer

HukkaHua

ASKER

ozo , that part I understood but did not get the loop part ....

Thanks,
H

SOLUTION

ozo

membership

Create a free account to see this answer

Signing up is free and takes 30 seconds. No credit card required.

See answer

NovaDenizen

for any a,b,m:
(a * b) mod m = ((a mod m) * b) mod m.
(a + b) mod m = ((a mod m) + b) mod m

For all s >= 0,
(1<<s) mod ((1<<s)-1) = 1

So if you break a number x into xhi and xlo such that
x = xhi * (1<<s) + xlo

then
x mod ((1<<s)-1) = (xhi * (1<<s) + xlo) mod ((1<<s)-1)
by the addition rule above,
= ((xhi * (1<<s)) mod ((1<<s)-1) + xlo) mod ((1<<s)-1)
then by the multiplication rule,
= ((xhi * ((1 << s) mod ((1<<s)-1)) mod ((1<<s)-1) + xlo) mod ((1<<s)-1)
Since ((1<<s) mod ((1<<s)-1) = 1,
= ((xhi * 1 ) mod ((1<<s)-1) + xlo) mod ((1<<s)-1)
x*1 = x
= (xhi mod ((1<<s)-1) + xlo) mod ((1<<s)-1)
reversing the addition rule
x mod ((1<<s)-1) = (xhi + xlo) mod ((1<<s)-1)
This is the recursive rule you need.

NovaDenizen

Split between ozo and ozo?