What is the best way to perform a division and a modulo for the processor?

Question

How to perform a division AND a modulo at the same time. Is it possible for the processor ?

Like :

int a, b = 8 / 3; //a = 2, b = 2

Or is there an operation which is better than :

int a = 8 / 3;
int b = 8 % 3;

Maybe this is better ?

int a = 8 / 3;
int b = 8 - a * 3;

Thanks.

http://stackoverflow.com/questions/5608559/division-and-modulus-using-single-divl-instruction-i386-amd64 might be of interest. — Maciej Stachowski, Sep 21 '14 at 16:10
Your optimizing compiler should know better than you, so don't bother (and I guess it does not matter that much in practice: cache misses cost much more than divisions) — Basile Starynkevitch, Sep 21 '14 at 16:10
It's possible for the processor if it has an instruction that does it. There are many different processors, all with different capabilities. The 6502 doesn't even have division (or multiplication, for that matter). — molbdnilo, Sep 21 '14 at 16:30
@Basile Starynkevitch: I am not sure all compilers can apply this trick. For compute-intensive code, it really matters to try and avoid divisions. — , Sep 21 '14 at 16:42
possible duplicate of [Divide and Get Remainder at the same time?](http://stackoverflow.com/questions/3895081/divide-and-get-remainder-at-the-same-time) — Jongware, Sep 21 '14 at 21:32

score 6 · Accepted Answer · answered Sep 21 '14 at 16:34

6

Consider the following function:

std::pair<int, int> divmod(int x, int y)
{
    return { x / y, x % y };
}

Compiling this with g++ -std=c++11 -O1 -S spits out the following assembly code:

movl    %edi, %eax
cltd
idivl   %esi
salq    $32, %rdx
movl    %eax, %eax
orq     %rdx, %rax
ret

As you can see, it only contains a single division on line 3. Optimizers are very good at this stuff.

answered Sep 21 '14 at 16:34

fredoverflow

256,549
94
388
662

Great stuff! Moreoever, a compiler will also replace `% y` -> `& (y-1)` and `/ y` with `<< log2(y)` if `y` is a power of two. No need to worry about such micro-optimizations and just write the most expressive code. – TemplateRex Sep 25 '14 at 06:58

score 5 · Answer 2 · answered Sep 21 '14 at 16:09

Maybe this is better?

Why would it be? It’s obscure, both to the programmer and the compiler/optimiser. Without having looked at the compiler output, I’d imagine that any decent optimiser sees your first code and says “ah, a div and a mod being performed, I’d better emit the divmod¹ opcode”. Whereas in the second case the optimiser is well within its right to shrug and leave it at that.

As a general rule (with many exceptions though), the cleanest code which has its semantics stated directly is also the code that is easiest to optimise.

¹ For a given processor, the opcode name may differ.

+1. The most common optimizers are peephole optimizers, because they're so simple. That's just a set of rules in the form "If you see pattern `XYZ`, replace by instructions sequence `AB`". In particular, there's a finite set of common patterns `XYZ`. `a/b,a%b` is a common pattern, `a/b, a - (a/b)*b` is not. — MSalters, Sep 22 '14 at 07:54

score 1 · Answer 3 · answered Sep 21 '14 at 21:20

Perhaps you are creating a solution to a problem that <cstdlib>'s std::div is provided to solve?

namespace std
{

struct div_t
{
    int quot;
    int rem;
};
struct ldiv_t
{
    long int quot;
    long int rem;
};
struct lldiv_t
{
    long long int quot;
    long long int rem;
};

  div_t div ( int numer, int denom );
 ldiv_t div ( long int numer, long int denom );
lldiv_t div ( long long int numer, long long int denom );

}; // namespace std

http://www.cplusplus.com/reference/cstdlib/div/

What is the best way to perform a division and a modulo for the processor?

3 Answers3