c++ - 使用 gmp 固定大小的整数...？

Question

几天来我一直在尝试在 MINGW 下安装 GMP 库。我在 linux64 位环境下使用 gcc 已经使用了数周 __uint128_t，然后在 GMP 和 mingw(32 位版本)下移植了相同的程序。我使用了 mpz_class 整数而不是 __uint128_t。然后我开始了我的新程序并且......!使用 __uint128_t 和 64 位需要 16 分钟才能完成，使用 GMP 和 MINGW 需要 91 小时!!!

我应该怎么做才能加快速度？有没有更快的方法在 32 位环境下进行 128 位整数数学运算？我不需要超过 128 位，那么有什么方法可以告诉 GMP“好的，我只需要 128 位，保持精度不变，但请加快速度”？

Answer 1

不，当您使用 mpz_t 时，您不能将 GMP 限制为固定长度的整数。 mpz_t 是一个具有 limbs 数组长度(已分配；已使用)的结构和一个指向实际值的指针，该实际值存储为 int 数组(limbs；int32 或 int64 数组)。 GMP 准备在任何值变大时扩展其长度。

您可以在初始化时为每个 mpz_t 分配 128 位，使用 mpz_init2:

 mpz_init2(mpz_t*, bit_number);

但是由此带来的加速很小，仍然存在数据间接和长度处理。

切换到 mpn_ 低级函数，您可以直接使用肢体:

http://www.gnu.org/software/gmp/manual/html_node/Low-level-Functions.html#Low-level%20Functions

不会有指向肢体的指针(这有利于缓存)，没有简单的输入/输出代码；并且没有自动肢体大小处理(也没有自动扩展；也没有分配)。你应该自己做所有的存储；甚至可能有些进位必须手动处理，但会有GMP的快速*、/和%操作；您可以使用 mpz_t t;t._mp_size = t._mp_alloc=limb_number;t._mp_d=pointer_to_limb_array 重构 mpz_t 以便于输入/输出。

此外，如果您要切换到 64 位 mingw，则可以使用 uint128_t。