3

我正在实现一个 BigInt 类，它必须支持对整数的任意精度操作。

引用 S.Skiena 的“算法设计手册”：

我应该在什么基础上做[编者注：任意精度]算术？- 以十进制实现您自己的高精度算术包可能是最简单的，因此将每个整数表示为以 10 为基数的字符串。然而，使用更高的基数要高效得多，理想情况下等于硬件算术完全支持的最大整数的平方根。

如何找到硬件算术完全支持的最大整数？如果我理解正确，作为我的机器是基于 x64 的 PC，支持的最大整数应该是 2^64（http://en.wikipedia.org/wiki/X86-64 - Architectural features: 64-bit integer capability），所以我应该使用base 2 ^ 32，但是在c ++中有没有办法以编程方式获得这个大小，所以我可以将我的base_type输入到它？

4

4 回答 4

5

您可能正在搜索std::uintmax_tand std::intmax_t。

于 2012-08-18T12:12:43.103 回答
2

static_cast<unsigned>(-1)是最大整数。例如，所有位都设置为1这就是您要查找的内容吗？

您也可以使用std::numeric_limits<unsigned>::max()or UINT_MAX，所有这些都会产生相同的结果。这些值说明的是unsigned类型的最大容量。例如，可以存储到无符号类型的最大值。

于 2012-08-18T12:14:12.993 回答
1

事情不是那么非黑即白。这里有 MAY 问题，你可能还有其他值得考虑的事情。我现在已经编写了两个精度可变的工具（在 MATLAB、VPI和HPF中），并且我在每个工具中都选择了不同的方法。编写整数形式还是高精度浮点形式也很重要。

不同之处在于，整数可以不受位数限制地增长。但是，如果您使用用户指定的位数进行浮点实现，您总是知道尾数中的位数。这是固定的。

首先，最简单的方法是为每个十进制数字使用一个整数。这使得很多事情都很好地工作，所以 I/O 很容易。但是在存储方面它有点低效。加法和减法虽然很容易。如果你对每个数字使用整数，那么乘法就更容易了。例如，在 MATLAB 中，conv 非常快，尽管它仍然是 O(n^2)。我认为 gmp 使用 fft 乘法，所以更快。

但是假设您使用基本的 conv 乘法，那么您需要担心具有大量数字的数字的溢出。例如，假设我将十进制数字存储为 8 位有符号整数。使用 conv，后跟进位，我可以进行乘法运算。例如，假设我有数字 9999。

N = repmat(9,1,4)
N =
     9     9     9     9

conv(N,N)
ans =
    81   162   243   324   243   162    81

因此，即使要形成乘积 9999*9999，我也需要小心，因为数字会溢出 8 位有符号整数。如果我使用 16 位整数来累积卷积乘积，那么一对 1000 位整数之间的乘法可能会导致溢出。

N = repmat(9,1,1000);
max(conv(N,N))
ans =
       81000

因此，如果您担心数百万位数的可能性，您需要小心。

一种替代方法是使用我称之为 migits 的东西，基本上工作在比 10 更高的基数上。因此，通过使用基数 1000000 和双精度数来存储元素，我可以为每个元素存储 6 个十进制数字。但是，卷积仍然会导致较大数字的溢出。

N = repmat(999999,1,10000);
log2(max(conv(N,N)))
ans =
       53.151

因此，在长度为 10000 migits（60000 个十进制数字）的两组基数为 1000000 migits 之间的卷积将溢出 double 不能精确表示整数的点。

同样，如果您要使用数百万位数的数字，请小心。使用基于卷积的乘法的更高的 migits 基数的一个好处是，因为 conv 操作是 O(n^2)，然后从基数 10 到基数 100 会给你 4-1 的加速。以 1000 为基数会在卷积中产生 9-1 的加速。

最后，使用 10 以外的基数作为 migits 使得实现保护数字（对于浮点数）是合乎逻辑的。在浮点运算中，您永远不应该信任计算的最低有效位，因此保留几个数字是有意义的隐藏在阴影中。因此，当我编写HPF工具时，我让用户可以控制携带多少位数。这当然不是整数的问题。

还有很多其他问题。我在这些工具附带的文档中讨论它们。

于 2012-08-18T14:01:59.980 回答
1

int（并且，通过扩展，unsigned int）是架构的“自然”大小。因此，具有一半 int 位的类型应该可以很好地工作。除此之外，您确实需要针对特定​​硬件进行配置；存储单元的类型和计算单元的类型应该是标头中的 typedef，并且选择它们的类型以匹配特定的处理器。通常，您会在运行一些速度测试后做出此选择。

INT_MAX 在这里没有帮助；它告诉您可以存储在 int 中的最大值，这可能是也可能不是硬件可以直接支持的最大值。同样， INTMAX_MAX 也无济于事；它告诉您可以存储为整数类型的最大值，但不会告诉您对此类值的操作是否可以在硬件中完成或需要软件仿真。

回到过去，经验法则是对 int 的操作直接在硬件中完成，而对 long 的操作是作为多个整数操作完成的，因此对 long 的操作比对 int 的操作慢得多。这不再是一个好的经验法则。

于 2012-08-18T16:47:25.727 回答