Sign in to follow this  
snooty

/ and %

Recommended Posts

When dividing an int by another int, does the computer get the quotient and remainder in one step? If so, is there a way to get both in one step other than in two? ie. Turning the following: int i; int quotient = i / 10; int remainder = i % 10; into something like: int i; int (quotient, remainder) = i / 10;

Share this post


Link to post
Share on other sites
Quote:
Original post by snooty
When dividing an int by another int, does the computer get the quotient and remainder in one step? If so, is there a way to get both in one step other than in two?
Some processors will do it in one step. If the processor is capable of it, the compiler will make that optimization for you.

Share this post


Link to post
Share on other sites
What promit said, and if you're doing it a lot, you could always write a function... But it's a very small amount of extra code anyway and besides which if you are worrying about a simple two step vs one step on that level a function call is probably going to defeat the purpose.

Share this post


Link to post
Share on other sites
#include <cstdlib> /* or <stdlib.h> in case of C */

div_t q = div(7,3);
int quotient = q.quot, remainder = q.rem; /* 2 and 1, respectively */

Share this post


Link to post
Share on other sites
Intel processors do it always in one step(div/idiv). Maybe there's more instructions for integer divisions I don't know. Compilers are usually very smart. I'm pretty sure that int "quotient = i / 10;int remainder = i % 10;" will be done in one step.

Or you can try:
int a,b;
int quotient,reminder;
__asm
{
mov edx,0
mov eax,a
idiv b
mov quotient,eax
mov reminder,edx
}






[Edited by - ivarbug on October 20, 2006 5:08:24 AM]

Share this post


Link to post
Share on other sites
this function:

void divmod(int p, int q, int& d, int& r)
{
d = p / q;
r = p % q;
}

compiled with gcc and optimisations turned on yields:

00000000 <divmod(int, int, int&, int&)>:
0: 8b 44 24 04 mov 0x4(%esp),%eax
4: 99 cltd
5: f7 7c 24 08 idivl 0x8(%esp)
9: 89 d1 mov %edx,%ecx
b: 8b 54 24 0c mov 0xc(%esp),%edx
f: 89 02 mov %eax,(%edx)
11: 8b 44 24 10 mov 0x10(%esp),%eax
15: 89 08 mov %ecx,(%eax)
17: c3 ret

As you can see, there is just one div instruction generated. If you make it inline, you can use it anywhere where you would use / and % without any overhead or additional code generated.

Share this post


Link to post
Share on other sites
The VC2005 generated code is essentially the same with slightly better optimization. For some reason gcc is feeling the need to shuffle edx around a bit while VC just writes it out directly.

I actually had a slightly difficult time getting VC to not automatically inline the function. And even when that was done it still wanted to generate an out-of-line version specialized to my test case (q==10) until I beat up on it some more.

Share this post


Link to post
Share on other sites
Quote:
Original post by Anon Mike
The VC2005 generated code is essentially the same with slightly better optimization. For some reason gcc is feeling the need to shuffle edx around a bit while VC just writes it out directly.

I was using "gcc version 3.4.4 (mingw special)". A current version of gcc like 4.1 and above would probably generate better code.

Quote:

I actually had a slightly difficult time getting VC to not automatically inline the function. And even when that was done it still wanted to generate an out-of-line version specialized to my test case (q==10) until I beat up on it some more.

I compiled it with:

g++ -c -O3 -fomit-frame-pointer divmod.cc

By just creating an object file (without linking), the compiler is forced to generate the functions.

If you create a specialized function, you may start to wonder. The compiler is very smart sometimes and creates an even faster (although longer version). Consider this:

void divmod2(int p, int& d, int& r)
{
d = p / 10;
r = p % 10;
}

and look at the generated code:

00000020 <divmod2(int, int&, int&)>:
20: 8b 4c 24 04 mov 0x4(%esp),%ecx
24: ba 67 66 66 66 mov $0x66666667,%edx
29: 89 c8 mov %ecx,%eax
2b: f7 ea imul %edx
2d: 89 c8 mov %ecx,%eax
2f: c1 f8 1f sar $0x1f,%eax
32: c1 fa 02 sar $0x2,%edx
35: 29 c2 sub %eax,%edx
37: 8b 44 24 08 mov 0x8(%esp),%eax
3b: 89 10 mov %edx,(%eax)
3d: 8d 14 92 lea (%edx,%edx,4),%edx
40: 8b 44 24 0c mov 0xc(%esp),%eax
44: 01 d2 add %edx,%edx
46: 29 d1 sub %edx,%ecx
48: 89 08 mov %ecx,(%eax)
4a: c3 ret


There is no division anymore! The compiler multiplies by 0.1 instead, then adjusts some bits.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this