在 64 位 x 64 位乘法中使用 Karatsuba 算法真的很高效吗？
Is it really efficient to use Karatsuba algorithm in 64-bit x 64-bit multiplication?
我在 AVX2 上工作，需要计算 64 位 x64 位 -> 128 位加宽乘法，并以最快的方式得到 64 位高位部分。既然AVX2没有这样的指令，我用Karatsuba算法来提高效率和速度是否合理？
如果不尝试就很难判断，但仅使用 AMD64 MUL 指令可能会更快，它支持 64x64=128，吞吐量与大多数 AVX2 指令（但未矢量化）相同。缺点是如果操作数在 YMM 寄存器中，则需要加载到常规寄存器。这将为单个 64x64=128 提供类似于 LOAD + MUL + STORE 的内容。
如果您可以在 AVX2 中矢量化 Karatsuba，请同时尝试 AVX2 和 MUL，看看哪个更快。如果您不能矢量化，单个 MUL 可能会更快。如果你能去除加载和存储到常规寄存器，单个 MUL 肯定会更快。
MUL 和 AVX2 指令都可以在内存中有一个具有相同吞吐量的操作数，这可能有助于为 MUL.
移除一个负载
which does 64bx64b to 128b in one instruction. There is one exception I'm aware of large multiplications using floating point FFT.
但是，如果您不需要 64bx64b 到 128b，您可以考虑
53bx53b 到 106b 使用 double-double arithmetic.
将四个53位数字a和b相乘得到四个106位数字只需要两条指令：
__m256 p = _mm256_mul_pd(a,b);
__m256 e = _mm256_fmsub_pd(a,b,p);
与使用 mulx.
的一条指令中的一个 128 位数字相比，这在两条指令中给出了四个 106 位数字
没有。在现代架构上，Karatsuba 击败教科书乘法的交叉点通常介于 8 到 24 个机器字之间（例如 x86_64 上的 512 到 1536 位之间）。对于固定大小，阈值位于该范围的较小端，新的 ADCX/ADOX 指令可能会使其在标量代码中更进一步，但 64x64 仍然太小，无法从 Karatsuba 中受益。
我在 AVX2 上工作，需要计算 64 位 x64 位 -> 128 位加宽乘法，并以最快的方式得到 64 位高位部分。既然AVX2没有这样的指令，我用Karatsuba算法来提高效率和速度是否合理？
如果不尝试就很难判断，但仅使用 AMD64 MUL 指令可能会更快，它支持 64x64=128，吞吐量与大多数 AVX2 指令（但未矢量化）相同。缺点是如果操作数在 YMM 寄存器中，则需要加载到常规寄存器。这将为单个 64x64=128 提供类似于 LOAD + MUL + STORE 的内容。
如果您可以在 AVX2 中矢量化 Karatsuba，请同时尝试 AVX2 和 MUL，看看哪个更快。如果您不能矢量化，单个 MUL 可能会更快。如果你能去除加载和存储到常规寄存器，单个 MUL 肯定会更快。
MUL 和 AVX2 指令都可以在内存中有一个具有相同吞吐量的操作数，这可能有助于为 MUL.
但是，如果您不需要 64bx64b 到 128b，您可以考虑 53bx53b 到 106b 使用 double-double arithmetic.
将四个53位数字a和b相乘得到四个106位数字只需要两条指令：
__m256 p = _mm256_mul_pd(a,b);
__m256 e = _mm256_fmsub_pd(a,b,p);
与使用 mulx.
没有。在现代架构上，Karatsuba 击败教科书乘法的交叉点通常介于 8 到 24 个机器字之间（例如 x86_64 上的 512 到 1536 位之间）。对于固定大小，阈值位于该范围的较小端，新的 ADCX/ADOX 指令可能会使其在标量代码中更进一步，但 64x64 仍然太小，无法从 Karatsuba 中受益。