Jump to content
  • Advertisement
Sign in to follow this  
Lode

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.

If you intended to correct an error in the post then please contact us.

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?

Share this post


Link to post
Share on other sites
Advertisement
Quote:
Original post by Nice Coder
Neither and yes.

from,
Nice coder


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

Share this post


Link to post
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 this post


Link to post
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.

I'll think about it.

From,
Nice coder

Share this post


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


int x = 19;
int y = 7;

int div = x / y; // integer division
int mod = x - (x*div); // remainder


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

Share this post


Link to post
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 this post


Link to post
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 this post


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

I believe you meant shift to the left.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!