表示具有 2000 个或更多数字的整数

Question

我想写一个程序，它可以计算超过 2000 或 20000 位的整数（对于 Pi 的小数）。我想用 C++ 做，没有任何库！（没有大整数，boost，...）。任何人都可以建议一种方法吗？以下是我的想法：

使用const char*，用于保存整数的数字；
表示喜欢的数字

( (1 * 10 + x) * 10  + x )...

Answer 1

显而易见的答案是这样的：

class integer {
    bool negative;
    std::vector<std::uint64_t> data;
};

其中数字表示为符号位和（无符号）基数 2**64 值。

这意味着你的数字的绝对值是：

数据[0] + (数据[1] << 64) + (数据[2] << 128) + ....

或者，换句话说，您将您的数字表示为一个小字节序的位串，其中的字与您的目标机器可以合理使用的一样大。我选择了 64 位整数，因为您可以通过这种方式（在 x64 机器上）最大限度地减少单个单词操作的数量。

要实现加法，您需要使用您在小学学到的概念：

  a           b
+ x           y
------------------
 (a+x+carry) (b+y reduced to one digit length)

缩减（模 2**64）自动发生，进位只能是零或一。剩下的就是检测进位了，很简单：

bool next_carry = false;
if(x += y < y) next_carry = true;
if(prev_carry && !++x) next_carry = true;

减法可以类似地使用借位来实现。请注意，获得接近例如性能的任何地方。 libgmp 是......不太可能。

Answer 2

一个长整数通常由一个数字序列表示（参见positional notation). For convenience, use little endian约定：A[0]是最低位，A [n-1] 是最高的。在一般情况下，对于 [= 的某些值，您的数字等于 sum(A[i] * base^i) 26=]基础.

base 的最简单值是十，但效率不高。如果你想经常打印你的答案给用户，你最好使用 10 的幂作为 base。例如，您可以使用 base = 10^9 并将所有数字存储在 int32 类型中。如果你想要最大速度，那么最好使用两个基数的幂。例如，base = 2^32 是 32 位编译器的最佳基数（但是，您需要汇编才能使其以最佳方式工作）。

负整数有两种表示方式，第一种是将整数存储为符号+数字序列。在这种情况下，您必须自己处理所有具有不同标志的情况。另一种选择是使用 complement form。它可以用于二的幂和十的幂。

由于序列的长度可能不同，这种情况下最好将数字序列存储在std::vector. Do not forget to remove leading zeroes中。另一种解决方案是始终存储固定数量的数字（固定大小的数组）。

操作以非常简单的方式实现：就像你在学校做的一样=)

P.S. 另外，由于 CRT.这种表示仅支持有限的操作集，如果要打印它，则需要进行非平凡的转换。

表示具有 2000 个或更多数字的整数

Represent Integers with 2000 or more digits

c++

integer