如何处理任意大的整数

Question

我正在研究一种编程语言，今天我得到了可以编译阶乘函数（递归）的点，但是由于整数的最大大小，我可以获得的最大阶乘（12）。 有哪些技术可以处理任意最大大小的整数。 该语言目前的工作方式是将代码翻译为 C++。

Answer 1

如果您需要大于 32 位的数据，您可以考虑使用 64 位整数（long long），或者使用或编写任意精度的数学库，例如 GNU MP。

Answer 2

如果您想推出自己的任意精度库，请参阅 Knuth 的半数值算法，其代表作的第 2 卷。

Answer 3

如果您正在使用当今巨大的内存空间将无限大小的十进制数学构建到一种语言中（我猜是为了学习目的），您应该只使用一个字节数组，其中每个字节只保存一个数字（0-9）。 然后，您可以编写自己的例程来对字节数组进行加、减、乘和除操作。

如果您自己实现它，您使用的算法可以简单地呼应您作为人类进行数学计算的方式。 对于加法，只需从右侧开始，添加每个位置以生成一个新数字并处理进位等。

我可以给您一些类似 Java 的伪代码，但此时不能真正从头开始执行 C++：

class BigAssNumber {
    private byte[] value;

    // This constructor can handle numbers where 
    // overflows have occurred. for instance:
    // add [5][7] and [8] to come up with [5][15]
    // then let this constructor change that to [6][5]
    public BigAssNumber(byte[] value) {
        this.value=normalize(value);
    }

    // Adds two numbers and returns the sum.  Originals not changed.
    public BigAssNumber add(BigAssNumber other) {
        // This needs to be a byte by byte copy in newly allocated space, not pointer copy!
        byte[] dest = value.length > other.length ? value : other.value;         

        // Just add each pair of numbers, like in a pencil and paper addition problem.
        for(int i=0; i<min(value.length, other.value.length); i++)
            dest[i]=value[i]+other.value[i];

        // constructor will fix overflows.
        return new BigAssNumber(dest);
    }

    // Fix things that might have overflowed  0,17,22 will turn into 1,9,2        
    private byte[] normalize(byte [] value) {
        if (most significant digit of value is not zero)
            extend the byte array by a few zero bytes in the front (MSB) position.

        // Simple cheap adjust.  Could lose inner loop easily if It mattered.
        for(int i=0;i<value.length;i++)
            while(value[i] > 9) {
                value[i] -=10;
                value[i+1] +=1;
            }
        }
    }
}

我使用事实上，我们在一个字节中有很多额外的空间来帮助以通用方式处理加法溢出。 也可以用于减法（您的字节可以进行签名，以便 [4][3] - [7] = [4][-4]，并将其标准化为 [3][6]。

我不处理负数BigAssIntegers 在这里，但您可以在类中存储符号标志，您也可以存储小数点位置，但此时您完全复制了 BCD 样式库，这会提高性能。

Answer 4

在 C++ 中没有简单的方法可以做到这一点。 您必须使用外部库，例如 GNU Multi precision，或者使用本机支持任意大整数的其他语言例如Python。

Answer 5

其他海报提供了可以为您执行此操作的库的链接，但您似乎正在尝试将其构建到您的语言中。 我的第一个想法是：你确定需要这样做吗？ 正如其他人所建议的那样，大多数语言都会使用附加库。

假设您正在编写一个编译器并且确实需要此功能，您可以为汇编中的任意大值实现整数算术函数。

例如，一个简单（但非最佳）的实现会将数字表示为二进制编码的十进制。 算术函数可以使用与使用铅笔和纸进行数学运算时所使用的相同算法。

另外，请考虑对这些大整数使用专门的数据类型。 这样“普通”整数就可以使用标准 32 位算术。

Answer 6

我更喜欢的方法是使用我当前的 int 类型作为 32 位整数（或者可能将其在内部更改为 long long 或类似的类型，只要它可以继续使用相同的算法），然后当它溢出时，将其更改为存储为 bignum，无论是我自己创建的还是使用外部库的。 但是，我觉得我需要检查每个算术运算的溢出情况，大约是算术运算的 2 倍开销。 我该如何解决这个问题？

Answer 7

如果我要实现自己的语言并希望支持任意长度的数字，我将使用具有进位/借位概念的目标语言。 但由于没有 HLL 可以在没有严重性能影响（如异常）的情况下实现这一点，所以我肯定会在汇编中实现它。 它可能需要一条指令（如 x86 中的 JC）来检查溢出并处理它（如 x86 中的 ADC），这对于实现任意精度的语言来说是可接受的折衷方案。 然后，我将使用一些用汇编语言编写的函数，而不是常规运算符，如果您可以利用重载来获得更优雅的输出，那就更好了。 但我不期望生成的 C++ 作为目标语言是可维护的（或意味着可维护的）。

或者，只需使用一个比您需要的更多功能的库，并将其用于您的所有数字。

作为一种混合方法，检测汇编中的溢出并在溢出时调用库函数，而不是滚动自己的迷你库。