Integer div and mod together?

[Howard]

Hi,

I know I can do integer division with the / operator, and get the
modulus with the % operator, but is there any function that calculates both
values in one shot? It seems quite wasteful in time to do the division
twice in order to get both of those values, when it would be quite easy to
return them both from a single function.

I saw someone's code implementing a divmod() function using assembler.
But it doesn't look like there is a built-in function for doing that in C++,
correct? Seeing as how I do a lot of mathematical calculations, I'm
thinking of writing one myself, but writing one in assembler is
platform-specific, and writing one in C++ doesn't seem logical. It seems to
me that it ought to part of the C++ standard, and implemented by compiler
vendors to target the specific platform(s) they support.

Any thoughts? (Or perhaps I should take this to comp.std.c++?)

-Howard

 

[Alf P. Steinbach]

* Howard:

I know I can do integer division with the / operator, and get the
modulus with the % operator, but is there any function that calculates both
values in one shot? It seems quite wasteful in time to do the division
twice in order to get both of those values, when it would be quite easy to
return them both from a single function.

I saw someone's code implementing a divmod() function using assembler.
But it doesn't look like there is a built-in function for doing that in C++,
correct? Seeing as how I do a lot of mathematical calculations, I'm
thinking of writing one myself, but writing one in assembler is
platform-specific, and writing one in C++ doesn't seem logical. It seems to
me that it ought to part of the C++ standard, and implemented by compiler
vendors to target the specific platform(s) they support.

Any thoughts? (Or perhaps I should take this to comp.std.c++?)

Measure before you optimize.

You might be surprized.

 

[Victor Bazarov]

I know I can do integer division with the / operator, and get the
modulus with the % operator, but is there any function that calculates both
values in one shot? It seems quite wasteful in time to do the division
twice in order to get both of those values, when it would be quite easy to
return them both from a single function.

You might try doing it in two consecutive statements and see if the
compiler manages to optimise them properly.

I saw someone's code implementing a divmod() function using assembler.
But it doesn't look like there is a built-in function for doing that in C++,
correct? Seeing as how I do a lot of mathematical calculations, I'm
thinking of writing one myself, but writing one in assembler is
platform-specific,

And why is *that* stopping you? The Standard library, for example, is all
platform- and implementation-specific. No big deal. Just do it on every
platform where you need it.

and writing one in C++ doesn't seem logical. It seems to
me that it ought to part of the C++ standard, and implemented by compiler
vendors to target the specific platform(s) they support.

Any thoughts? (Or perhaps I should take this to comp.std.c++?)

If you propose to have such function added, I'd rather to to 'comp.std.c'.
But I am not sure all CPUs can do that, although IIRC, all I every wrote
an assembly program for, did.

There are three incarnations of 'remquo' functions in C99, but they are
for floating point numbers.

V

 

[E. Robert Tisdale]

I know [that] I can do integer division with operator/
and get the [remainder] with operator%
but is there any function that calculates both values in one shot?

It seems quite wasteful in time to do the division twice
in order to get both of those values
when it would be quite easy to return them both from a single function.

I saw someone's code implementing a divmod() function using assembler.
But it doesn't look like there is a built-in function for doing that in C++,
correct? Seeing as how I do a lot of mathematical calculations,
I'm thinking of writing one myself
but writing one in assembler is platform-specific
and writing one in C++ doesn't seem logical.
It seems to me that it ought to part of the C++ standard
and implemented by compiler vendors
to target the specific platform(s) they support.

DIV(3) Linux Programmer’s Manual DIV(3)


NAME
div, ldiv, lldiv, imaxdiv -
compute quotient and remainder of an integer division


SYNOPSIS
#include <stdlib.h>


div_t div(int numerator, int denominator);
ldiv_t ldiv(long numerator, long denominator);
lldiv_t lldiv(long long numerator, long long denominator);


#include <inttypes.h>


imaxdiv_t imaxdiv(intmax_t numerator, intmax_t denominator);


DESCRIPTION
The div() function computes the value numerator/denominator and
returns the quotient and remainder in a structure named div_t
that contains two integer members (in unspecified order)
named quot and rem. The quotient is rounded towards zero.
The result satisfies quot*denominator+rem = numerator.


The ldiv() and lldiv() and imaxdiv() functions do the same,
dividing numbers of the indicated type and returning the result
in a structure of the indicated name, in all cases with fields
quot and rem of the same type as the function arguments.


RETURN VALUE
The div_t (etc.) structure.


EXAMPLE
After
div_t q = div(-5, 3);
the values q.quot and q.rem are -1 and -2, respectively.


CONFORMING TO
SVID 3, BSD 4.3, ISO 9899.
The functions lldiv() and imaxdiv() were added in ISO C99.


SEE ALSO
abs(3)


2003-11-01 DIV(3)


Bjarne Stroustrup, "The C++ Programming Language: Third Edition",
Chapter 22 Numerics, Section 3 Standard Mathematical Functions, page 661

"For historical reasons,
a few mathematical functions are found in the <cstdlib> header
rather than in <cmath>."

 

[Jerry Coffin]

Hi,

I know I can do integer division with the / operator, and get the

modulus with the % operator, but is there any function that calculates both
values in one shot?

The div function does both, but it's not (even close to) guaranteed
that it'll be any more efficient than using / and %.

 

[Andrey Tarasevich]

I know I can do integer division with the / operator, and get the
modulus with the % operator, but is there any function that calculates both
values in one shot?

Yes. It is called 'div' ('ldiv'). It is inherited from C standard
library. However, how exactly it calculates these values depends on the
concrete implementation.

It seems quite wasteful in time to do the division
twice in order to get both of those values, when it would be quite easy to
return them both from a single function.

Firstly, just because you write the division twice in your C++ code
doesn't mean that it will be performed twice in the compiled code. A
smart compiler can easily optimize away the extra division.

Secondly, a dedicated function might introduce extra overhead that will
defeat all the benefits (this applies to the aforementioned 'div'/'ldiv'
functions as well). Meanwhile, if the compiler is smart enough to
perform low-overhead inlining of such functions, then it is probably
smart enough to perform the optimization mentioned under "firstly".

I saw someone's code implementing a divmod() function using assembler.
But it doesn't look like there is a built-in function for doing that in C++,
correct?

There's a C library function (see above). Does this qualify as
"built-in" in your book?

 

[Howard]

I know [that] I can do integer division with operator/
and get the [remainder] with operator%
but is there any function that calculates both values in one shot?

Bjarne Stroustrup, "The C++ Programming Language: Third Edition",
Chapter 22 Numerics, Section 3 Standard Mathematical Functions, page 661

"For historical reasons,
a few mathematical functions are found in the <cstdlib> header
rather than in <cmath>."

You know, I had my book open to that page when I wrote this, and I never saw
those div functions. I must be going blind! (Probably all that, well, you
know...)

Thanks one and all!

-Howard

 

[Walter]

I know I can do integer division with the / operator, and get the
modulus with the % operator, but is there any function that calculates both
values in one shot? It seems quite wasteful in time to do the division
twice in order to get both of those values, when it would be quite easy to
return them both from a single function.

I'd just get a good optimizing compiler. Consider:

#include <stdio.h>
void foo(int a, int b)
{
int c;
int d;
c = a / b;
d = a % b;
printf("%d %d\n", c, d);
}

Compiling it with Digital Mars C++ gives:

_foo:
push EAX
mov EAX,8[ESP]
cdq
idiv dword ptr 0Ch[ESP]
push EDX
push EAX
push offset FLAT:_DATA
call near ptr _printf
add ESP,0Ch
pop EAX
ret

No need to muck about with special functions, inline assembler, etc.

-Walter
www.digitalmars.com C, C++, D compilers
"code of the nerds"

 

[Jack Klein]

Yes. It is called 'div' ('ldiv'). It is inherited from C standard
library. However, how exactly it calculates these values depends on the
concrete implementation.

No it doesn't. C++ inherits the C90 definition of 'div' and 'ldiv':

<quote>
4.10.6.2 The div function

Synopsis

#include <stdlib.h>
div_t div(int numer, int denom);

Description

The div function computes the quotient and remainder of the
division of the numerator numer by the denominator denom . If the
division is inexact, the sign of the resulting quotient is that of the
algebraic quotient, and the magnitude of the resulting quotient is the
largest integer less than the magnitude of the algebraic quotient. If
the result cannot be represented, the behavior is undefined;
otherwise, quot * denom + rem shall equal numer .

Returns

The div function returns a structure of type div_t , comprising
both the quotient and the remainder. The structure shall contain the
following members, in either order.

int quot; /* quotient */
int rem; /* remainder */
<unquote>

So how is this implementation-defined?

 

[E. Robert Tisdale]

I know [tht] I can do integer division with operator/
and get the modulus with operator%
but is there any function that calculates both values in one shot?

Yes. It is called 'div' ('ldiv').
It is inherited from C standard library. However,
how exactly it calculates these values
depends on the concrete implementation.

No it doesn't. C++ inherits the C90 definition of 'div' and 'ldiv':

<quote>
4.10.6.2 The div function

Synopsis

#include <stdlib.h>
div_t div(int numer, int denom);

Description

The div function computes the quotient and remainder of the
division of the numerator numer by the denominator denom . If the
division is inexact, the sign of the resulting quotient is that of the
algebraic quotient, and the magnitude of the resulting quotient is the
largest integer less than the magnitude of the algebraic quotient.
the result cannot be represented, the behavior is undefined;
If otherwise, quot * denom + rem shall equal numer .

Returns

The div function returns a structure of type div_t , comprising
both the quotient and the remainder. The structure shall contain the
following members, in either order.

int quot; /* quotient */
int rem; /* remainder */
<unquote>

So how is this implementation-defined?

Bjarne Stroustrup, "The C++ Programming Language: Third Edition",
Chapter 22 Numerics, Section 3 Standard Mathematical Functions, page 661

struct div_t { implementation_defined quot, rem; };
struct ldiv_t { implementation_defined quot, rem; };

The data representation is implementation defined and, of course,
div(int, int), div(long int, long it) and ldiv(long int, long in)
could be implement in assembler
or as C or C++ external or inline functions
which may or may not invoke
any combination of operator/ and/or operator%.

 

[Christian Gollwitzer]

I'd just get a good optimizing compiler. Consider:

#include <stdio.h>
void foo(int a, int b)
{
int c;
int d;
c = a / b;
d = a % b;
printf("%d %d\n", c, d);
}

Compiling it with Digital Mars C++ gives:

GCC optimizes it away, too:
foo:
pushl %ebp
movl %esp, %ebp
subl $12, %esp
movl 8(%ebp), %edx
movl %edx, %eax
sarl $31, %edx
idivl 12(%ebp)
pushl %edx
pushl %eax
pushl $.LC0
call printf
leave
ret
.size foo, .-foo
.ident "GCC: (GNU) 3.3.1 (SuSE Linux)"

No need to muck about with special functions, inline assembler, etc.

-Walter
www.digitalmars.com C, C++, D compilers

No need to buy a compiler SCNR

Christian

 

[Martin Stettner]

GCC optimizes it away, too:

So does VC++ 2003:

void foo(int a, int b)
{
int c,d;
c = a / b;
d = a % b;
00401000 mov eax,dword ptr [esp+4]
00401004 cdq
00401005 idiv eax,dword ptr [esp+8]
00401009 push esi
printf("%d %d\n", c, d);
0040100A push edx
0040100B push eax
0040100C push offset string "%d %d\n" (406100h)
00401011 call printf (40105Bh)

It optimizes even if there are other statements between division and
remainder calculation:

int c,d,k,f;
c = a / b;
00401000 mov eax,dword ptr [esp+4]
00401004 cdq
00401005 idiv eax,dword ptr [esp+8]
00401009 push esi
k = c+2;
0040100A lea ecx,[eax+2]
f = 2*k;
0040100D lea esi,[ecx+ecx]
d = a % b;
printf("%d %d %d %d\n", c, d, k, f);
00401010 push esi
00401011 push ecx
00401012 push edx
00401013 push eax
00401014 push offset string "%d %d %d %d\n" (406100h)
00401019 call printf (40105Bh)

so there's no need at all for hand-made optimization.

cu
Martin

 

[Howard]

GCC optimizes it away, too:

So does VC++ 2003:

void foo(int a, int b)
{
int c,d;
c = a / b;
d = a % b;
00401000 mov eax,dword ptr [esp+4]
00401004 cdq
00401005 idiv eax,dword ptr [esp+8]
00401009 push esi
printf("%d %d\n", c, d);
0040100A push edx
0040100B push eax
0040100C push offset string "%d %d\n" (406100h)
00401011 call printf (40105Bh)

It optimizes even if there are other statements between division and
remainder calculation:

int c,d,k,f;
c = a / b;
00401000 mov eax,dword ptr [esp+4]
00401004 cdq
00401005 idiv eax,dword ptr [esp+8]
00401009 push esi
k = c+2;
0040100A lea ecx,[eax+2]
f = 2*k;
0040100D lea esi,[ecx+ecx]
d = a % b;
printf("%d %d %d %d\n", c, d, k, f);
00401010 push esi
00401011 push ecx
00401012 push edx
00401013 push eax
00401014 push offset string "%d %d %d %d\n" (406100h)
00401019 call printf (40105Bh)

so there's no need at all for hand-made optimization.

cu
Martin

That's pretty cool. When I started coding (back in the stone age), hand
optimizations were pretty much required. Glad to see that compilers have
come so far.

Thanks, everyone!

-Howard

 

[Andrey Tarasevich]

No it doesn't. C++ inherits the C90 definition of 'div' and 'ldiv':
...
So how is this implementation-defined?
...

I never said that specification of this function depends on the
implementation. By "depends on the concrete implementation" I meant that
there's no guarantee that the actual implementation if 'div'/'ldiv'
functions is different from a simple application of '/' and '%', i.e.
there is no guarantee that 'div'/'ldiv' is more efficient in OP's case
even if we assume that there's no function call overhead.