分而治之?
显然,x86(也可能是很多其他的指令集)把分频操作的商和余数都放在单独的寄存器中。
现在,我们可以信任编译器来优化这样的代码,只使用一个调用来划分:
( x / 6 ) ( x % 6 )
他们可能会这样做。 尽pipe如此,做任何语言 (或图书馆,但主要是寻找语言)都支持同时提供分而治之的模式结果吗? 如果是这样,它们是什么,语法是什么样子?
C有div
和ldiv
。 这些是否为商和余数生成单独的指令将取决于您特定的标准库实现以及编译器和优化设置。 从C99开始,你也有更大的数字lldiv
。
Python呢。
>>> divmod(9, 4) (2, 1)
这很奇怪,因为Python是如此高级的语言。
Ruby:
11.divmod(3) #=> [3, 2]
*编辑*
应该指出的是,这些操作员的目的可能不是尽可能高效地完成工作,更可能是出于正确性/便携性的原因而存在的function。
对于那些感兴趣的,我相信这是整数divmod的Python实现的代码 :
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) /* ie and signs differ */) { xmody += y; --xdivy; assert(xmody && ((y ^ xmody) >= 0)); } *p_xdivy = xdivy; *p_xmody = xmody; return DIVMOD_OK; }
在C#/。NET你有Math.DivRem
: http : //msdn.microsoft.com/en-us/library/system.math.divrem.aspx
但根据这个线程,这不是一个优化。
Common Lisp可以: http : //www.lispworks.com/documentation/HyperSpec/Body/f_floorc.htm
正如Stringer Bell所提到的那样, DivRem
并没有被优化到.NET 3.5。
在.NET 4.0上, 它使用NGen 。
我用Math.DivRem
得到的结果(debug; release =〜11000ms)
11863 11820 11881 11859 11854
结果我用MyDivRem
(debugging;释放=〜11000毫秒)
29177 29214 29472 29277 29196
针对x86的项目。
Math.DivRem
用法示例
int mod1; int div1 = Math.DivRem(4, 2, out mod1);
方法签名
DivRem(Int32, Int32, Int32&) : Int32 DivRem(Int64, Int64, Int64&) : Int64
.NET 4.0代码
[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参考
.NET框架有Math.DivRem
:
int mod, div = Math.DivRem(11, 3, out mod); // mod = 2, div = 3
虽然, DivRem
只是一个这样的包装:
int div = x / y; int mod = x % y;
(我不知道抖动是否可以将这种事情优化为一条指令。)
FWIW,Haskell同时具有divMod
和quotRem
,后者直接对应于机器指令(根据积分操作符与div ),而divMod
可能不会。
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 }
这将返回结果的余数
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 }
在Java中,类BigDecimal
具有divideAndRemainder
操作,返回2个元素的数组,其结果和除法的其余部分。
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)