HukkaHua

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

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

membership

Create a free account to see this answer

Signing up is free and takes 30 seconds.

**No credit card required.**SOLUTION

membership

Create a free account to see this answer

Signing up is free and takes 30 seconds.

**No credit card required.**
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.

(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.

Split between ozo and ozo?

ASKER

Thanks,

H