c++ - Bigint（大比特）库

Question

我正在寻找一个 c++ 类/库，它提供 1024 位和更大的整数和位操作，例如： - 位移， - 按位 OR/AND， - 定位第一个零位

速度至关重要，因此必须使用一些 SIMD 程序集来实现。

Answer 1

有几个，包括GMP，但对于速度，最好的可能是TTmath。TTmath 在编译时使用模板化固定长度的设计决定让它变得非常快。

Answer 2

试试gmp 库。它是一个 C 库。从 GMP 4.0 开始，C++ 包装器与发行版捆绑在一起。

Answer 3

只考虑大整数乘法，TTmath 库使用 Karatsuba 算法，其时间复杂度为 $O(n^{1.585})$。最快的算法是 $O(n log n log log n)$，使用 FFT。