C 中的多字加法

Question

我有一个使用 GCC__uint128_t的 C 程序，这很棒，但现在我的需求已经超出了它。

196 位或 256 位的快速算术有哪些选择？

我唯一需要的操作是加法(我不需要进位，即我将工作 mod 2¹⁹²或^{2 256})。

速度很重要，所以如果可能的话，我不想转向一般的多精度。(事实上，我的代码确实在某些地方使用了多精度，但这是在关键循环中，将运行数百亿次。到目前为止，多精度只需要运行数万次。

也许这很简单，可以直接编码，或者我需要找到一些合适的库。

你的建议是什么，哦，伟大的堆栈溢出？

澄清：GMP对于我的需求来说太慢了。虽然我实际上在我的代码中使用了多精度，但它不在内部循环中，并且运行次数少于 10^{5 次}。热回路运行更像 10¹²次。当我更改代码(增加大小参数)以使多精度部分比单精度部分更频繁地运行时，我的速度降低了 100 倍(我认为主要是由于内存管理问题，而不是额外的 μops)。我想把它降低到 4 倍或更好的速度。

Answer 1

256 位版本

__uint128_t a[2], b[2], c[2];        // c = a + b
c[0] = a[0] + b[0];                  // add low part
c[1] = a[1] + b[1] + (c[0] < a[0]);  // add high part and carry

编辑：192 位版本。通过这种方式，您可以消除 128 位比较，如@harold所述：

struct uint192_t {
__uint128_t H;
uint64_t L;
} a, b, c;  // c = a + b
c.L = a.L + b.L;
c.H = a.H + b.H + (c.L < a.L);

或者，您可以使用整数溢出内置或检查算术内置

bool carry = __builtin_uaddl_overflow(a.L, b.L, &c.L);
c.H = a.H + b.H + carry;

关于 Godbolt 的演示

---

如果您在循环中执行大量添加操作，则应考虑使用 SIMD 和/或与多线程并行运行它们。对于 SIMD，您可能需要更改类型的布局，以便一次添加所有低电平部件，一次添加所有高电平部件。一旦可能的解决方案是这里建议的数组结构数组 BigNum AVX/SSE 可能吗？

SSE2:   llhhllhhllhhllhh
AVX2:   llllhhhhllllhhhh
AVX512: llllllllhhhhhhhh

使用 AVX-512，您可以一次添加八个 64 位值。因此，您可以在 3 条指令中添加 8 个 192 位值，外加一些用于进位的值。有关更多信息，请阅读是否可以使用 SSE 和 SSE2 制作 128 位宽整数？

使用 AVX-2 或 AVX-512，您可能还具有非常快的水平添加，因此即使您没有并行添加链，也值得尝试 256 位。但是对于 192 位加法，3 个加法/adc 指令会快得多

---

还有许多具有固定宽度整数类型的库。例如 Boost.Multiprecision

#include <boost/multiprecision/cpp_int.hpp>
using namespace boost::multiprecision;
uint256_t myUnsignedInt256 = 1;

其他一些库：

• TTMATH：ttmath:UInt<3>(具有 3 个肢体的 int 类型，在 64 位计算机上为 192 位)
• uint256_t

参见

• C++ 128/256 位固定大小整数类型

Answer 2

你可以测试这个答案中的"添加(low < oldlow)来模拟携带"技术是否足够快。由于low在这里是一个__uint128_t，这可能会损害代码生成，因此稍微复杂一些。你也可以用 4 个uint64_t尝试一下，我不知道这会更好还是更糟。

如果这还不够好，请转到内联程序集，并直接使用 carry 标志 - 没有比这更好的了，但你会有使用内联程序集的常见缺点。