4

在 x86 上实现 bignums 时，显然最有效的数字大小选择是 32 位。但是，您需要最多两倍于数字大小的算术（即 32+32=33、32*32=64、64/32=32）。幸运的是，x86 不仅提供了这一点，而且还可以从可移植的 C ( uint64_t) 中访问它。

同样，在 x64 上，最好使用 64 位数字。这将需要 128 位算术（即 64+64=65、64*64=128、128/64=64）。幸运的是，x64 提供了这一点。不幸的是，它不能从便携式 C 中访问，尽管显然可以使用汇编。

所以我的问题是它是否可以从不可移植的 C 中访问。x64 上的任何 C 编译器是否提供对此的访问，如果是，语法是什么？

（请注意，我不是在谈论被严格视为 32 或 64 位字的集合的 128 位向量，它们之间没有进位传播，而是关于实际的 128 位整数运算。）

4

2 回答 2

3

GCC 4.1 引入了初始的 128 位整数支持__int128_t和__uint128_t内置类型，但 128 位类型自GCC 4.6正式发布为__int128/unsigned __int128

Clang 也支持这些类型，虽然我不知道从什么时候开始。Godbolt（3.0.0）上的第一个版本__int128_t确实支持

ICC 自 13.0.0 版以来获得了相同的支持：在英特尔 C 编译器中支持 +、-、*、/ 和 % 的 128 位整数？

也可以看看

如果您在 MSVC 上，则不直接支持 128 位类型，但有许多内在函数可帮助您执行 128 位操作：

  • 64*64=128: _mul128(), _umul128(), __mulh(),__umulh()

  • 128/64=64: _div128(),_udiv128()

  • 64+64=65：加法中的进位可以很容易地通过将和的低部分与任何操作数进行比较来获得：

    struct uint128 {
    uint64_t H, L;
};

inline uint128 add(uint128 a, uint128 b)
{
    uint128 c;
    c.L = a.L + b.L;                // add low parts
    c.H = a.H + b.H + (c.L < a.L);  // add high parts and carry
    return c;
}

    同样的东西可以用于128位减法

尽管实现这些是微不足道的，但也有用于转移的内在函数__shiftleft128()：__shiftright128()

如果您使用的是不受支持的编译器，那么只需使用许多可用库中的一些固定宽度类型，这会快得多。例如ttmath:UInt<4>（具有四个 32 位肢体的 128 位 int 类型），或(u)int128_t在Boost.Multiprecision和calccrypto/uint128_t中。像 GMP 这样的任意精度算术库对于这个来说成本太高了。一个例子：优化故事：从 GMP 切换到 gcc__int128将运行时间减少了 95%

于 2020-10-27T15:26:19.553 回答
1

您可能需要检查 GNU 多精度算术库：

http://gmplib.org/

于 2011-03-13T10:56:57.070 回答