Divide and Get Remainder at the same time?

Question

Apparently, x86 (and probably a lot of other instruction sets) put both the quotient and the remainder of a divide operation in separate registers.

Now, we can probably trust compilers to optimize a code such as this to use only one call to divide:

( X / 6 )
( x % 6 )

And they probably do. Still, do any languages (or libraries, but mainly looking for languages) support giving both the divide and modulo results at the same time? If so, what are they, and What does the syntax look like?

Answer 1

Python does.

>>> divmod(9, 4)
(2, 1)

Which is odd, becuase Python is such a high level language.

So does Ruby:

11.divmod(3) #=> [3, 2]

* EDIT *

It should be noted that the purpose of these operators is probably not to do the work as efficiently as possible, it is more likely the functions exist for correctness/portability reasons.

For those interested, I believe this is the code of the Python implementation for integer divmod:

static enum divmod_result
i_divmod(register long x, register long y,
     long *p_xdivy, long *p_xmody)
{
long xdivy, xmody;

if (y == 0) {
    PyErr_SetString(PyExc_ZeroDivisionError,
                    "integer division or modulo by zero");
    return DIVMOD_ERROR;
}
/* (-sys.maxint-1)/-1 is the only overflow case. */
if (y == -1 && UNARY_NEG_WOULD_OVERFLOW(x))
    return DIVMOD_OVERFLOW;
xdivy = x / y;
/* xdiv*y can overflow on platforms where x/y gives floor(x/y)
 * for x and y with differing signs. (This is unusual
 * behaviour, and C99 prohibits it, but it's allowed by C89;
 * for an example of overflow, take x = LONG_MIN, y = 5 or x =
 * LONG_MAX, y = -5.)  However, x - xdivy*y is always
 * representable as a long, since it lies strictly between
 * -abs(y) and abs(y).  We add casts to avoid intermediate
 * overflow.
 */
xmody = (long)(x - (unsigned long)xdivy * y);
/* If the signs of x and y differ, and the remainder is non-0,
 * C89 doesn't define whether xdivy is now the floor or the
 * ceiling of the infinitely precise quotient.  We want the floor,
 * and we have it iff the remainder's sign matches y's.
 */
if (xmody && ((y ^ xmody) < 0) /* i.e. and signs differ */) {
    xmody += y;
    --xdivy;
    assert(xmody && ((y ^ xmody) >= 0));
}
*p_xdivy = xdivy;
*p_xmody = xmody;
return DIVMOD_OK;
}

Answer 2

In C#/.NET you've got Math.DivRem: http://msdn.microsoft.com/en-us/library/system.math.divrem.aspx

But according to this thread this isn't that much an optimization.

Answer 3

The .NET framework has Math.DivRem:

int mod, div = Math.DivRem(11, 3, out mod);
// mod = 2, div = 3

Although, DivRem is just a wrapper around something like this:

int div = x / y;
int mod = x % y;

(I have no idea whether or not the jitter can/does optimise that sort of thing into a single instruction.)

Answer 4

Common Lisp does: http://www.lispworks.com/documentation/HyperSpec/Body/f_floorc.htm

Answer 5

As Stringer Bell mentioned there is DivRem which is not optimized up to .NET 3.5.

On .NET 4.0 it uses NGen.

The results I got with Math.DivRem (debug; release = ~11000ms)

11863
11820
11881
11859
11854

Results I got with MyDivRem (debug; release = ~11000ms)

29177
29214
29472
29277
29196

Project targeted for x86.

---

Math.DivRem Usage example

int mod1;
int div1 = Math.DivRem(4, 2, out mod1);

Method signatures

DivRem(Int32, Int32, Int32&) : Int32
DivRem(Int64, Int64, Int64&) : Int64

.NET 4.0 Code

[TargetedPatchingOptOut("Performance critical to inline across NGen image boundaries")]
public static int DivRem(int a, int b, out int result)
{
    result = a % b;
    return (a / b);
}

.NET 4.0 IL

.custom instance void System.Runtime.TargetedPatchingOptOutAttribute::.ctor(string) = { string('Performance critical to inline across NGen image boundaries') }
.maxstack 8
L_0000: ldarg.2 
L_0001: ldarg.0 
L_0002: ldarg.1 
L_0003: rem 
L_0004: stind.i4 
L_0005: ldarg.0 
L_0006: ldarg.1 
L_0007: div 
L_0008: ret 

MSDN Reference

Answer 6

C has div and ldiv. Whether these generate separate instructions for the quotient and remainder will depend on your particular compiler and optimization settings.

Answer 7

Haskell has divMod