Divide and Get Remainder at the same time?

问题:

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?

回答1:

C has div and ldiv. Whether these generate separate instructions for the quotient and remainder will depend on your particular standard library implementation and compiler and optimization settings. Starting with C99, you also have lldiv for larger numbers.

回答2:

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;
}

回答3:

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.

回答4:

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

回答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

回答6:

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.)

回答7:

FWIW, Haskell has both divMod and quotRem that latter of which corresponds directly to the machine instruction (according to Integral operators quot vs. div) while divMod may not.

回答8:

    int result,rest;
    _asm
    {
        xor edx, edx // pone edx a cero; edx = 0
        mov eax, result// eax = 2AF0
        mov ecx, radix // ecx = 4
        div ecx
        mov val, eax
        mov rest, edx
    }

回答9:

This return the result an de remainder

        int result,rest;
    _asm
    {
        xor edx, edx // pone edx a cero; edx = 0
        mov eax, result// eax = 2AF0
        mov ecx, radix // ecx = 4
        div ecx
        mov val, eax
        mov rest, edx
    }

回答10:

In Java the class BigDecimal has the operation divideAndRemainder returning an array of 2 elements with the result and de remainder of the division.

BigDecimal bDecimal = ...
BigDecimal[] result = bDecimal.divideAndRemainder(new BigDecimal(60));

Javadoc: https://docs.oracle.com/javase/7/docs/api/java/math/BigDecimal.html#divideAndRemainder(java.math.BigDecimal)