/ and %
Author
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;
Quote:Original post by snootySome processors will do it in one step. If the processor is capable of it, the compiler will make that optimization for you.
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?
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.
#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 */
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:
[Edited by - ivarbug on October 20, 2006 5:08:24 AM]
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]
this function:
compiled with gcc and optimisations turned on yields:
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.
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 retAs 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.
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.
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.
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.ccBy 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 retThere is no division anymore! The compiler multiplies by 0.1 instead, then adjusts some bits.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
