在C语言中进行多词加法

Question

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

对于196位或256位的快速算术，我的选择是什么？

我唯一需要的操作是加法（我不需要进位位，即，我将使用模2¹⁹²或2²⁵⁶进行计算）。

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

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

你有什么建议，哦伟大的Stack Overflow？

澄清： GMP对我的需求来说太慢了。虽然我实际上在我的代码中使用了多精度，但它不在内部循环中，并且运行次数不到10⁵次。热循环运行次数更像是10¹²次。当我更改我的代码（增加大小参数），以便多精度部分运行更多次，而单精度部分运行更少时，我遇到了100倍的减速（主要是由于内存管理问题，我认为，而不是额外的µops）。我希望将其降至4倍或更低。

- Charles

---

我会使用GMPlib - 并进行性能分析和基准测试。 - Basile Starynkevitch

@BasileStarynkevitch：对于我的需求来说，GMP太慢了。当我需要更复杂的操作时，它非常好用，但对于简单的加法来说，开销太大了。特别是在内存中移动数据需要花费太长时间，以至于我会花费比实际计算更多的时间来移动位。 - Charles

@Charles，你应该在问题中提及你的性能测试结果，这样别人在回答你的问题时就不会建议使用第三方库了。 - Lee Duhem

@leeduhem：好建议，我已经做了。（尽管有时候我希望我不必向SO证明自己。） - Charles

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;

Demo on Godbolt: 实用的BigNum AVX/SSE。

SSE2:   llhhllhhllhhllhh
AVX2:   llllhhhhllllhhhh
AVX512: llllllllhhhhhhhh

使用AVX-512，您可以一次添加八个64位值。因此，您可以在3条指令中添加八个192位值，再加上一些进位。欲了解更多信息，请阅读Is it possible to use SSE and SSE2 to make a 128-bit wide integer? 使用AVX-2或AVX-512，您还可以拥有非常快的水平相加，因此即使没有并行相加链，对于256位也可能值得一试。但是对于192位的加法，那么3个add/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位固定大小整数类型

- phuclv

---

我可能因为忽视了这个简单的解决方案而感到惭愧。它的效果非常好，比我预期的要好得多。谢谢。 - Charles

Answer 2

您可以尝试测试“添加(low < oldlow)以模拟进位”的技巧，该技巧来自这个答案，看看它的速度是否足够快。由于在此处low是__uint128_t，因此稍微有些复杂，可能会影响代码生成。您也可以尝试使用4个uint64_t，但我不知道那样会更好还是更差。

如果这还不够好，可以降低到内联汇编，并直接使用进位标志——没有比这更好的了，但您将面临使用内联汇编的常规缺点。

- harold