Modulo Division

This topic is 4863 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

Recommended Posts

How is modulo division done by the processor? Is it done like this:
//calculate 19 % 7
int i = 19;
while(i > 6) i -= 7;
result = i;

Or like this:
//calculate 19 % 7
result = 19 - 7 * (int)(19 / 7.0);

Or something else? Also are modulo divisions through powers of 2 done the quick way by taking the LBS's?

Neither and yes.

from,
Nice coder

Share on other sites
Quote:
 Original post by Nice CoderNeither and yes.from,Nice coder

If it's neither, then how is it done?

Share on other sites
ok, now for the long answer.

x % 2^y = x & (2^y - 1)

Always.

Why?

Assume you want x % 8 and you've got an 8 bit number.

log2 8 = 3

Lets say we have the number

a * 2^7 + b * 2^6 + c * 2^5 + d * 2^4 + e * 2^3 + f * 2^2 + g * 2^1 + h * 2^0

What we want are the last four bits. (f, g and h).

Why?

Look at the modulo number as a torus with numbers written on the outside of it. (or a circule, if yoru more comfy with 2d geo).

2^4 = 16.
Thats exactly double 8 (the number we need).

So, no matter what that bit is, we end up in the same spot. (either its 0 and we don't go anyware, or its 1, and we go around the torus twice and you end up in the same spot).

The same logic applies for the rest of the bits. 2^5 makes you go around 4 times before ending up in the same spot, 2^6 8, 2^7 16, ect.

Post 1 of 2.

From,
Nice coder

Share on other sites
Post 2 of 2.

How its done by the processer is different depending on how its implemented.

I've done it in software, (along with a sf div), but i don't know how they do it in hardware.

It wouldn't be cost effective to do a multiply and division as well as a subtraction, because theres an instruction which gives you both x / y and x % y.

And there are no loops in the processor.

From,
Nice coder

Share on other sites
Quote:
 How is modulo division done by the processor?

int x = 19;int y = 7;int div = x / y;       // integer divisionint mod = x - (x*div); // remainder

Typically the result is computed as part of the division algorithm. (example)

Share on other sites
I think when you do DIV in asm the remainder goes into a register so it's probably a:

mov ax, num1
mov bl, num2
div bl

return would be (if I remember correctly... correct me if I'm wrong )

al = quotient
ah = remainder

so it's just a matter of returning ah to your function.

Share on other sites
assume you have x % y = z

in order to get z, you must remove all multiples of y in x.

In hardware, this is what i'd do.

Starting with mssb x - mssb y as tmp

shift y tmp bits to the right.if the newly shifted number is greater then x then     tmp = tmp - 1     if tmp = 0 then you have your remainder in x.else     x = x - the shifted y     tmp = tmp - 1     if tmp = 0 then we have the remainder.end if

Thats at most you have 31 iterations.

you could probably make it in hw running at 32 iterations.

Also, you can modify it to give you division as well. (so you'd make a divmod instruction instead of both. just saves time)

From,
Nice coder

Share on other sites
Quote:
 Original post by Nice Codershift y tmp bits to the right.

I believe you meant shift to the left.

1. 1
2. 2
3. 3
4. 4
frob
15
5. 5

• 9
• 12
• 20
• 12
• 13
• Forum Statistics

• Total Topics
632146
• Total Posts
3004439

×