//calculate 19 % 7
int i = 19;
while(i > 6) i -= 7;
result = i;
//calculate 19 % 7
result = 19 - 7 * (int)(19 / 7.0);
Modulo Division
Author
How is modulo division done by the processor?
Is it done like this:
Author
Quote:Original post by Nice Coder
Neither and yes.
from,
Nice coder
If it's neither, then how is it done?
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
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
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
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
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); // remainderTypically the result is computed as part of the division algorithm. (example)
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.
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.
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
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
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 ifThats 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
Quote:Original post by Nice Coder
shift y tmp bits to the right.
I believe you meant shift to the left.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
