用64位常量校验乘法参数
对于我的BigInteger代码来说，对于非常大的BigIntegers来说，输出速度很慢。因此，现在我使用递归的分而治之算法，它仍然需要2'30“来将目前已知的最大素数转换为超过2200万位数字的十进制字符串(但只有135 ms才能将其转换为十六进制字符串)。
我仍然希望缩短时间，所以我需要一个可以非常快地将NativeUInt ( 32位平台上的UInt32，64位平台上的UInt64 )除以100的例程。所以我用常量乘法。这在32位代码中很好，但我不能100%肯定64位。
那么，我的问题是:对于无符号64位值，是否有一种用常量检验乘法结果的可靠性的方法？我检查了32位值，只需尝试使用UInt32的所有值(0.$FFFFFFFF)。这需要大约。3分钟。检查所有的UInt64s将花费比我的一生更长的时间。是否有方法检查所使用的参数(常数，后移位)是否可靠？
我注意到，如果选择的参数是错误的(但关闭的)，DivMod100()对于$4000004B这样的值总是失败的。是否有特殊的值或范围来检查64位，所以我不必检查所有的值？
我现在的代码是：
const
{$IF DEFINED(WIN32)}
// Checked
Div100Const = UInt32(UInt64($1FFFFFFFFF) div 100 + 1);
Div100PostShift = 5;
{$ELSEIF DEFINED(WIN64)}
// Unchecked!!
Div100Const = $A3D70A3D70A3D71;
// UInt64(UInt128($3 FFFF FFFF FFFF FFFF) div 100 + 1);
// UInt128 is fictive type.
Div100PostShift = 2;
{$IFEND}
// Calculates X div 100 using multiplication by a constant, taking the
// high part of the 64 bit (or 128 bit) result and shifting
// right. The remainder is calculated as X - quotient * 100;
// This was tested to work safely and quickly for all values of UInt32.
function DivMod100(var X: NativeUInt): NativeUInt;
{$IFDEF WIN32}
asm
// EAX = address of X, X is UInt32 here.
PUSH EBX
MOV EDX,Div100Const
MOV ECX,EAX
MOV EAX,[ECX]
MOV EBX,EAX
MUL EDX
SHR EDX,Div100PostShift
MOV [ECX],EDX // Quotient
// Slightly faster than MUL
LEA EDX,[EDX + 4*EDX] // EDX := EDX * 5;
LEA EDX,[EDX + 4*EDX] // EDX := EDX * 5;
SHL EDX,2 // EDX := EDX * 4; 5*5*4 = 100.
MOV EAX,EBX
SUB EAX,EDX // Remainder
POP EBX
end;
{$ELSE WIN64}
asm
.NOFRAME
// RCX is address of X, X is UInt64 here.
MOV RAX,[RCX]
MOV R8,RAX
XOR RDX,RDX
MOV R9,Div100Const
MUL R9
SHR RDX,Div100PostShift
MOV [RCX],RDX // Quotient
// Faster than LEA and SHL
MOV RAX,RDX
MOV R9D,100
MUL R9
SUB R8,RAX
MOV RAX,R8 // Remainder
end;
{$ENDIF WIN32}回答 3
Stack Overflow用户
发布于 2016-01-31 23:25:43
与往常一样，在编写优化代码时，使用编译器输出作为提示/起点。在一般情况下，可以安全地假设所做的任何优化都是安全的。错误代码编译器错误是罕见的。
gcc用常量0x28f5c28f5c28f5c3实现了未签名的64位divmod。我还没有详细地研究为除法生成常量，但是有一些生成常量的算法可以给出很好的结果(所以不需要进行详尽的测试)。
实际上，代码有几个重要的区别:它使用常量与OP常量不同。
请参阅注释，以分析这实际上正在做的事情:先除以4，因此它可以使用一个常数，当股息足够小时，它只能用于除以25。这也完全避免了以后添加的问题。
#include <stdint.h>
// rem, quot ordering takes one extra instruction
struct divmod { uint64_t quotient, remainder; }
div_by_100(uint64_t x) {
struct divmod retval = { x%100, x/100 };
return retval;
})
movabs rdx, 2951479051793528259
mov rax, rdi ; Function arg starts in RDI (SysV ABI)
shr rax, 2
mul rdx
shr rdx, 2
lea rax, [rdx+rdx*4] ; multiply by 5
lea rax, [rax+rax*4] ; multiply by another 5
sal rax, 2 ; imul rax, rdx, 100 is better here (Intel SnB).
sub rdi, rax
mov rax, rdi
ret
; return values in rdx:rax使用“二进制”选项来查看十六进制中的常量，因为反汇编程序输出就是这样做的，与gcc的asm源输出不同。
乘以100的部分。
gcc使用以上的lea/lea/shl序列，与你的问题相同。您的答案是使用mov imm/mul序列。
你们每个人的评论都说他们选择的版本更快。如果是这样的话，这是因为一些微妙的指令对齐或其他次要效应:在Intel家族中，它是相同数量的uop (3)，并且具有相同的关键路径延迟(mov imm在关键路径之外，mul是3个周期)。
clang使用我认为是最好的选择(imul rax, rdx, 100)。在我看到clang选择它之前，我就想到了它，这并不重要。这是一个融合域uop (只能在p0上执行)，仍然有3c延迟。因此，如果您使用这个程序来实现多精度的延迟限制，这可能不会有帮助，但这是最好的选择。(如果您是延迟绑定的，那么将代码内联到一个循环中，而不是通过内存传递其中一个参数，可以节省很多周期。)
imul工作是因为你只使用低64b的结果。没有2或3个操作数形式的mul，因为结果的下半部分是相同的，而不管输入的有符号或无符号解释。
顺便说一句，clang with -march=native为64x64->128使用了mulx，而不是mul，但没有从中获得任何好处。根据阿格纳·福格的表格，它的延迟比mul差一个周期。
AMD的imul r,r,i潜伏期超过3c (尤指p)。( 64b版)，这也许就是gcc避免使用它的原因。要知道gcc维护人员花了多少精力来调整成本，所以像-mtune=haswell这样的设置运行得很好，但是很多代码都没有用任何-mtune设置来编译(即使是-march所暗示的)，所以当gcc做出对旧CPU或-march最优的选择时，我并不感到惊讶。
clang仍然使用带有imul r64, r64, imm的-mtune=bdver1 (Bulldozer)，它节省了多个操作系统，但比使用lea/lea/shl要花费1c延迟。(使用scale>1的lea是推土机上的2c延迟)。
Stack Overflow用户
发布于 2016-01-30 15:42:34
我用libdivide.h找到了解决方案。下面是Win64稍微复杂的部分：
{$ELSE WIN64}
asm
.NOFRAME
MOV RAX,[RCX]
MOV R8,RAX
XOR RDX,RDX
MOV R9,Div100Const // New: $47AE147AE147AE15
MUL R9 // Preliminary result Q in RDX
// Additional part: add/shift
ADD RDX,R8 // Q := Q + X shr 1;
RCR RDX,1
SHR RDX,Div100PostShift // Q := Q shr 6;
MOV [RCX],RDX // X := Q;
// Faster than LEA and SHL
MOV RAX,RDX
MOV R9D,100
MUL R9
SUB R8,RAX
MOV RAX,R8 // Remainder
end;
{$ENDIF WIN32}Stack Overflow用户
发布于 2016-01-30 18:15:01
@Rudy's答案中的代码来自以下步骤：
- 以二进制形式写1/100：
0.000000(10100011110101110000)； - 小数点后数前导零：
S = 6； - 72第一批重要双边投资条约是：
1010 0011 1101 0111 0000 1010 0011 1101 0111 0000 1010 0011 1101 0111 0000 1010 0011 1101
- 循环到65位；这种舍入的执行方式有某种魔力；通过反向工程，鲁迪的答案中的常数是正确的四舍五入：
1010 0011 1101 0111 0000 1010 0011 1101 0111 0000 1010 0011 1101 0111 0000 1010 1
- 移除前面的
1位：
0100 0111 1010 1110 0001 0100 0111 1010 1110 0001 0100 0111 1010 1110 0001 0101
- 用十六进制形式写(取回报复常数)：
A = 47 AE 14 7A E1 47 AE 15
X div 100 = (((uint128(X) * uint128(A)) shr 64) + X) shr 7(7 = 1 + S)
https://stackoverflow.com/questions/35100712
复制相似问题
腾讯云开发者
