计算阶乘的递归函数在 20 之后失败

Question

我编写了下面的 Java 代码来递归计算从 1 到 30 的数字的阶乘。出于某种原因，对于大于 20 的数字，输出与 results here 不匹配。我也很惊讶地看到负数。

代码

class Test {

    public static Long factorial(Long number) {
        if(number == 1){
            return 1L;
        }else{
            return number*factorial(number-1);
        }
    }

    public static void main(final String... arguments){
        for(Long number=1L;number<=30;number++){
            System.out.println("Factorial of " + number + "  : " + factorial(number));
        }
    }
}

输出

Factorial of 1  : 1
Factorial of 2  : 2
Factorial of 3  : 6
Factorial of 4  : 24
Factorial of 5  : 120
Factorial of 6  : 720
Factorial of 7  : 5040
Factorial of 8  : 40320
Factorial of 9  : 362880
Factorial of 10  : 3628800
Factorial of 11  : 39916800
Factorial of 12  : 479001600
Factorial of 13  : 6227020800
Factorial of 14  : 87178291200
Factorial of 15  : 1307674368000
Factorial of 16  : 20922789888000
Factorial of 17  : 355687428096000
Factorial of 18  : 6402373705728000
Factorial of 19  : 121645100408832000
Factorial of 20  : 2432902008176640000
Factorial of 21  : -4249290049419214848
Factorial of 22  : -1250660718674968576
Factorial of 23  : 8128291617894825984
Factorial of 24  : -7835185981329244160
Factorial of 25  : 7034535277573963776
Factorial of 26  : -1569523520172457984
Factorial of 27  : -5483646897237262336
Factorial of 28  : -5968160532966932480
Factorial of 29  : -7055958792655077376
Factorial of 30  : -8764578968847253504

有人可以帮我正确计算 30 以内的阶乘吗？

Answer 1

它不起作用，因为您超出了 long 可以表示的最大数量。最小值为-9,223,372,036,854,775,808，最大值为9,223,372,036,854,775,807（含）。出现负数是因为 java 超过最大值时会转为负数。找到表示数字的不同方式。

Answer 2

这就是所谓的 "overflow"。 Long 以 64 位存储；它们的最大值是 2^63 - 1，即 9,223,372,036,854,775,807。而是尝试使用 BigInteger。使用 BigInteger 有点棘手，因为实例化和操作不同于正常 int/longs。这是为 BigInteger 重新编写的代码：

public class BigIntFactorial {

    public static BigInteger factorial(BigInteger number) {
        if(number.equals(BigInteger.ONE)) {
            return BigInteger.valueOf(1);
        } else {
            return number.multiply(factorial(number.subtract(BigInteger.ONE)));
        }
    }

    public static void main(final String... arguments){
        for(Long number=1L;number<=30;number++){

            System.out.println("Factorial of " + number + "  : " + factorial(BigInteger.valueOf(number)));
        }
    }
}

输出为：

Factorial of 1  : 1
Factorial of 2  : 2
Factorial of 3  : 6
Factorial of 4  : 24
Factorial of 5  : 120
Factorial of 6  : 720
Factorial of 7  : 5040
Factorial of 8  : 40320
Factorial of 9  : 362880
Factorial of 10  : 3628800
Factorial of 11  : 39916800
Factorial of 12  : 479001600
Factorial of 13  : 6227020800
Factorial of 14  : 87178291200
Factorial of 15  : 1307674368000
Factorial of 16  : 20922789888000
Factorial of 17  : 355687428096000
Factorial of 18  : 6402373705728000
Factorial of 19  : 121645100408832000
Factorial of 20  : 2432902008176640000
Factorial of 21  : 51090942171709440000
Factorial of 22  : 1124000727777607680000
Factorial of 23  : 25852016738884976640000
Factorial of 24  : 620448401733239439360000
Factorial of 25  : 15511210043330985984000000
Factorial of 26  : 403291461126605635584000000
Factorial of 27  : 10888869450418352160768000000
Factorial of 28  : 304888344611713860501504000000
Factorial of 29  : 8841761993739701954543616000000
Factorial of 30  : 265252859812191058636308480000000

Answer 3

您似乎运行解决了阶乘变得非常快的问题。大于可以用 long 表示的最大数字。在 java 中，这意味着值 "rolls over" 并变为负数。

一种解决方案是使用 BigInteger。它具有可变的位数，因此您几乎可以在其中表示任何大小的数字，并且不会运行出现溢出问题。请注意，当我说差不多时，我的意思是 biginteger 在某些实现中被限制为 Integer.MAX_VALUE 位，并且您永远不应该运行达到该限制。

另一种解决方案是用双精度表示数字。它们比多头有更高的限制，但代价是失去了一些精度。我没有运行数字，但你应该可以计算 30！

当你真的想突破极限时，你可以做的另一件很酷的事情是使用 fft 来计算精度非常高的数字的乘法。此处有更多信息：http://numbers.computation.free.fr/Constants/Algorithms/fft.html

编辑：运行数字，双精度就可以了

计算阶乘的递归函数在 20 之后失败

Recursive function to compute factorial fails after 20

java

recursion

factorial