13

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

4

7 回答 7

18

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

于 2008-11-21T21:41:18.900 回答
5

如果您想推出自己的任意精度库，请参阅 Knuth 的半数字算法，他的巨著第 2 卷。

于 2008-11-21T23:03:11.137 回答
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;
            }
        }
    }
}

我利用我们在一个字节中有很多额外空间的事实来帮助以通用方式处理加法溢出。也可以用于减法，并有助于一些乘法。

于 2008-11-21T22:46:14.180 回答
1

There's no easy way to do it in C++. You'll have to use an external library such as GNU Multiprecision, or use a different language which natively supports arbitrarily large integers such as Python.

于 2008-11-21T21:42:31.597 回答
0

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

或者，只需使用比您需要的更多花里胡哨的库，并将其用于您的所有数字。

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

于 2008-11-21T23:46:04.653 回答
0

Other posters have given links to libraries that will do this for you, but it seem like you're trying to build this into your language. My first thought is: are you sure you need to do that? Most languages would use an add-on library as others have suggested.

Assuming you're writing a compiler and you do need this feature, you could implement integer arithmetic functions for arbitrarily large values in assembly.

For example, a simple (but non-optimal) implementation would represent the numbers as Binary Coded Decimal. The arithmetic functions could use the same algorithms as you'd use if you were doing the math with pencil and paper.

Also, consider using a specialized data type for these large integers. That way "normal" integers can use the standard 32 bit arithmetic.

于 2008-11-21T21:53:35.253 回答
0

My prefered approach would be to use my current int type for 32-bit ints(or maybe change it to internally to be a long long or some such, so long as it can continue to use the same algorithms), then when it overflows, have it change to storing as a bignum, whether of my own creation, or using an external library. However, I feel like I'd need to be checking for overflow on every single arithmetic operation, roughly 2x overhead on arithmetic ops. How could I solve that?

于 2008-11-21T22:11:21.413 回答