如何处理任意大的整数

Question

我正在开发一种编程语言，今天我成功地实现了阶乘函数的编译（递归），但是由于整数类型的最大值限制，最大只能计算到12的阶乘。请问有哪些方法可以处理任意大小的整数？当前这个语言的运行方式是将代码转化为C++。

- Alex Gaynor

---

你所寻找的通常被称为“大数”，基本上是一种处理任意大整数的类。 - Kendall Helmstetter Gelner

你无法处理任意最大尺寸的整数，因为最大尺寸受可用存储空间限制，而且没有计算机拥有无限的存储空间。你可以编写库来处理你可能需要的大数，但是需要注意这些方法存在技术限制。 - Dominic Rodger

话虽如此，如果你真的想要，4GB的内存（和1TB的硬盘）足以存储一个非常大的数字，所以这只是一个哲学上的异议。 - Dominic Rodger

Answer 1

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

- Barry Kelly

Answer 2

如果你希望自己创建一个任意精度库，请参考Knuth的《计算机程序设计艺术》第2卷，其中有详细介绍。

- John D. Cook

---

+1 给 Knuth -- 否则你可能会错过除法的罕见边界情况。 - Steve Gilham

Answer 3

如果你正在开发这个项目（我猜是为了学习目的），我认为最好写一个小的BCD库。只需将BCD数字存储在字节数组中即可。

事实上，由于今天存储能力巨大，你可以使用一个字节数组，每个字节仅包含一个数字（0-9）。然后编写自己的例程来添加、减去、乘以和除以字节数组。

（除法是困难的，但我敢打赌你可以在某个地方找到一些代码。）

我可以给你一些类似Java的伪代码，但现在无法从头开始做C++。

class BigAssNumber {
    private byte[] value;

    // This constructor can handle numbers where overflows have occurred.
    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;
            }
        }
    }
}

我利用字节中的额外空间，以通用方式处理加法溢出问题。这种方法也适用于减法，并且在某些乘法上有所帮助。

- Bill K

---

如果你不是为学校做，那就去找一些BigInteger代码来使用吧。 - Bill K

Answer 4

在C++中没有简单的方法来实现。你需要使用外部库，例如GNU Multiprecision，或者使用本地支持任意大整数的不同语言，例如Python。

- Adam Rosenfield

---

我认为这很容易。GMP附带了一个不错的C++头文件。 - sellibitze

Answer 5

其他人已经给出了可以为您完成此操作的库的链接，但似乎您正在尝试将其构建到您的语言中。我的第一个想法是：您确定需要这样做吗？大多数语言都会使用其他人建议的附加库。

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

例如，简单（但非最优）的实现将数字表示为二进制编码十进制。算术函数可以使用与您在纸上进行数学运算时使用的相同算法。

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

- Clayton

---

人们对BCD的痴迷是什么？这里没有人要求它。 - sellibitze

Answer 6

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

- Alex Gaynor

---

不要过于担心性能问题。先编写代码，不必考虑性能，然后如果无法达到某个基准，请进行重构。 - Bill K

是的，你甚至可以将冒泡排序重构为归并排序……而且你肯定希望相比其他人拥有一个好的营销形象，以便向大公司销售你的通用面向对象语言的收缩包装盒。什么？它不是通用的吗？ - artificialidiot

您所描述的问题正是我建议创建新的数据类型的原因。C ++，Java等不会自动将16位int转换为32位，如果乘法溢出，那么您也不应该。另一方面，如果这是一个记录下来的需求，您就必须接受性能损失。 - Clayton

Answer 7

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

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

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

- artificialidiot