15

In C, is it possible to divide a dividend by a constant and get the result and the remainder at the same time?

I want to avoid execution of 2 division instructions, as in this example:

val=num / 10;
mod=num % 10;
1
  • 6
    If you compile this exact code with an optimizing compiler (like GCC) on x86 or x86_64, you will find it already compiles into a single idiv instruction. In short, do not worry about micro-optimizations like this; at this level, modern compilers are much, much smarter than you probably think.
    – Nemo
    Commented Oct 30, 2011 at 3:41

4 Answers 4

15

I wouldn't worry about the instruction count because the x86 instruction set will provide a idivl instruction that computes the dividend and remainder in one instruction. Any decent compiler will make use of this instruction. The documenation here http://programminggroundup.blogspot.com/2007/01/appendix-b-common-x86-instructions.html describes the instruction as follows:

Performs unsigned division. Divides the contents of the double-word contained in the combined %edx:%eax registers by the value in the register or memory location specified. The %eax register contains the resulting quotient, and the %edx register contains the resulting remainder. If the quotient is too large to fit in %eax, it triggers a type 0 interrupt.

For example, compiling this sample program:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int main()
{
  int x = 39;
  int divisor = 1;
  int div = 0;
  int rem = 0;

  printf("Enter the divisor: ");
  scanf("%d", &divisor);
  div = x/divisor;
  rem = x%divisor;

  printf("div = %d, rem = %d\n", div, rem);
}

With gcc -S -O2 (-S saves the tempory file created that shows the asm listing), shows that the division and mod in the following lines

div = x/divisor;
rem = x%divisor;

is effectively reduced to the following instruction:

idivl   28(%esp)

As you can see theres one instruction to perform the division and mod calculation. The idivl instruction remains even if the mod calculation in the C program is removed. After the idivl there are calls to mov:

movl    $.LC2, (%esp)
movl    %edx, 8(%esp)
movl    %eax, 4(%esp)
call    printf

These calls copy the quotient and the remainder onto the stack for the call to printf.

Update

Interestingly the function div doesn't do anything special other than wrap the / and % operators in a function call. Therefore, from a performance perspective, it will not improve the performance by replacing the lines

 val=num / 10;       
 mod=num % 10;

with a single call to div.

5
  • +1 for actually demonstrating that at least one compiler does it :)
    – detly
    Commented Oct 30, 2011 at 5:59
  • 1
    While OP did want to avoid execution of two division instructions, I think div() has value for readability and maintainability. The division is done at one place in the source, not scattered at two or more places. The field names of div_t also make for readability, I believe.
    – Gauthier
    Commented Jun 23, 2015 at 8:16
  • I am genuinely confused as to why the division and modulus operations happen separately when there is a CPU instruction that already does it in one step.
    – Sammitch
    Commented Feb 8, 2018 at 23:49
  • 1
    @Sammitch I think the answer shows that they in fact don't happen separately. Even if you write them in two expressions, it will still compile to a single instruction. Unless you are referring to the language itself not assigning them both in the same expression. But that's a different matter.
    – devios1
    Commented Dec 10, 2018 at 20:35
  • MS Visual Studio 2017 won't use single idiv when pointer de-referencing like *ptr_to_10 is used even with all optimizations enabled:(
    – mlt
    Commented May 9, 2019 at 19:41
6

There's div():

div_t result = div(num, 10);
// quotient is result.quot
// remainder is result.rem
3
  • The question was more concerned about the operation count than whether you can wrap calls to % and / in a function.
    – sashang
    Commented Oct 30, 2011 at 3:55
  • 1
    @sashan: Often this type of functions are implemented as compiler intrinsics so it could have the optimal performance. Unfortunately it seems that at least in Visual c++ 10 the div call is not even inlined and it is slower than the original code.
    – Timo
    Commented Oct 30, 2011 at 4:07
  • 2
    See here: sourceware.org/git/?p=glibc.git;a=blob;f=stdlib/…. The implementation of div just wraps the calls to % and /.
    – sashang
    Commented Oct 30, 2011 at 4:31
5

Don't waste your time with div() Like Nemo said, the compiler will easily optimize the use of a division followed by the use of a modulus operation into one. Write code that makes optimal sense, and let the computer remove the cruft.

2
  • Exactly, but doesn't div() make quite much sense as well? The / followed by % is a well-known idiom, so everybody knows what it does, but using div() and div_t does not make less sense to me. Its fields are called quot and rem, pretty self-documenting.
    – Gauthier
    Commented Jun 23, 2015 at 8:19
  • But using div() will clearly tell the compiler that you want quotient and remainder, without having to rely on the compiler being good enough to recognize that by just looking at your code. Even when the compiler won't recognize that or is very bad at optimizing code, it will surely have an highly optimized div() implementation for every supported platform. And as the compiler knows what div() does, it's part of the ISO-C standard, it usually does not even call that function but just emits the function's code.
    – Mecki
    Commented Jan 4 at 15:22
3

You could always use the div function.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.