uint64_t 与 int64_t 的开方

Question

我注意到计算 uint64_t 的平方根的整数部分比 int64_t 复杂得多。拜托，有人对此有解释吗？为什么处理多出的一位似乎要困难得多？

以下：

int64_t sqrt_int(int64_t a) {
    return sqrt(a);
}

使用 clang 5.0 和 -mfpmath=sse -msse3 -Wall -O3 编译为

sqrt_int(long):                           # @sqrt_int(long)
        cvtsi2sd        xmm0, rdi
        sqrtsd  xmm0, xmm0
        cvttsd2si       rax, xmm0
        ret

但以下内容：

uint64_t sqrt_int(uint64_t a) {
    return sqrt(a);
}

编译为：

.LCPI0_0:
        .long   1127219200              # 0x43300000
        .long   1160773632              # 0x45300000
        .long   0                       # 0x0
        .long   0                       # 0x0
.LCPI0_1:
        .quad   4841369599423283200     # double 4503599627370496
        .quad   4985484787499139072     # double 1.9342813113834067E+25
.LCPI0_2:
        .quad   4890909195324358656     # double 9.2233720368547758E+18
sqrt_int(unsigned long):                           # @sqrt_int(unsigned long)
        movq    xmm0, rdi
        punpckldq       xmm0, xmmword ptr [rip + .LCPI0_0] # xmm0 = xmm0[0],mem[0],xmm0[1],mem[1]
        subpd   xmm0, xmmword ptr [rip + .LCPI0_1]
        haddpd  xmm0, xmm0
        sqrtsd  xmm0, xmm0
        movsd   xmm1, qword ptr [rip + .LCPI0_2] # xmm1 = mem[0],zero
        movapd  xmm2, xmm0
        subsd   xmm2, xmm1
        cvttsd2si       rax, xmm2
        movabs  rcx, -9223372036854775808
        xor     rcx, rax
        cvttsd2si       rax, xmm0
        ucomisd xmm0, xmm1
        cmovae  rax, rcx
        ret

Answer 1

首先，您需要清楚这段代码将 64 位整数（有符号或无符号）转换为双精度浮点数，取平方根，然后将结果转换回有符号或无符号整数.

你的问题的答案是因为英特尔在你正在编译的指令集中提供了 64 位有符号整数到双精度浮点转换（和相反），但没有为无符号的情况这样做。他们在 AVX-512 中添加了无符号转换指令，但在此之前它并不存在。所以对于带符号的情况，转换为双精度和转换回来各是一条指令。对于无符号的情况，编译器必须从可用指令中合成转换操作。

您可以在此处获取有关哪些指令适用于哪些版本的 SSE2/AVX/AVX-512 等信息： https://software.intel.com/sites/landingpage/IntrinsicsGuide/

您可以在此处查看用于合成转换的方法的讨论： Are there unsigned equivalents of the x87 FILD and SSE CVTSI2SD instructions?

Answer 2

除了Zalman的优秀：sqrt的结果总是小于INT64_MAX因为sqrt的输入在uint64_t 范围。因此，单个 cvttsd2si 足以将双精度转换回 uint64_t。换句话说：对于所有输入值 a 函数

uint64_t sqrt_int(uint64_t a) {
    return sqrt(a);
}

与修改后的代码具有完全相同的行为

uint64_t sqrt_int(uint64_t a) {
    return (int64_t)sqrt(a);
}

后一个函数编译为

.LCPI0_0:
  .long 1127219200 # 0x43300000
  .long 1160773632 # 0x45300000
  .long 0 # 0x0
  .long 0 # 0x0
.LCPI0_1:
  .quad 4841369599423283200 # double 4503599627370496
  .quad 4985484787499139072 # double 1.9342813113834067E+25
sqrt_int(unsigned long): # @sqrt_int(unsigned long)
  movq xmm0, rdi
  punpckldq xmm0, xmmword ptr [rip + .LCPI0_0] # xmm0 = xmm0[0],mem[0],xmm0[1],mem[1]
  subpd xmm0, xmmword ptr [rip + .LCPI0_1]
  haddpd xmm0, xmm0
  sqrtsd xmm0, xmm0
  cvttsd2si rax, xmm0
  ret

比原始代码少了很多指令。

uint64_t 与 int64_t 的开方

sqrt of uint64_t vs. int64_t

x86

assembly

sse

compilation

square-root