4

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

对于 196 位或 256 位的快速算术，我有哪些选择？

我需要的唯一操作是加法（我不需要进位，即我将使用 mod 2 192或 2 256）。

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

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

你有什么建议，哦，Stack Overflow 很棒？

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

4

2 回答 2

4

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 位版本。这样您就可以消除像@harold 所说的那样的 128 位比较：

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，您可以一次添加 8 个 64 位值。因此，您可以在 3 条指令中添加 8 个 192 位值，再加上一些用于进位。有关更多信息，请阅读是否可以使用 SSE 和 SSE2 生成 128 位宽的整数？

使用 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

也可以看看

于 2014-03-02T09:58:58.310 回答
2

您可以测试此答案(low < oldlow)中的“添加到模拟进位”技术是否足够快。这里的事实稍微复杂一点，这可能会损害代码生成。你也可以用 4 试试，不知道是好是坏。low__uint128_tuint64_t

如果这还不够好，请使用内联汇编，并直接使用进位标志 - 没有比这更好的了，但使用内联汇编通常会有缺点。

于 2014-03-02T09:59:04.730 回答