修正递归指数法？

Question

我目前正在研究一种使用递归进行指数计算的方法。以下是我到目前为止所拥有的：

public static long exponentiation(long x, int n) {

    if (n == 0) {
        return 1;
    } else if (n == 1) {
        return x;
        // i know this doesn't work since im returning long
    } else if (n < 0) {
        return  (1 / exponentiation(x, -n));
    } else {
        //do if exponent is even
        if (n % 2 == 0) {
            return (exponentiation(x * x, n / 2));
        } else {
            // do if exponent is odd
            return x * exponentiation(x, n - 1);
        }
    }
}

我有两个问题。第一个问题是，我不能做负指数，这不是一个大问题，因为我不需要做负指数。第二个问题，是某些计算给了我错误的答案。例如，2^63给出了正确的值，但它给了我一个负数。2^64和on，给我0。不管怎么说我有办法解决这个问题吗？我知道我可以把long转换成double，我的方法会很好的工作。然而，我的教授要求我们使用long。谢谢你的帮助！

Answer 1

long可以表示的最大值是2^63 -1。所以，如果你计算出2^63，它会更大，那么一个长可以容纳和包裹什么。Long使用二补表示。

只是把长时间改为双倍并不完全有效。它改变了方法的语义。浮点数具有有限的精度。使用64位浮点数，您仍然只能表示与64位整数相同的数字数量。它们只是分布不同而已。长可以表示每一个整数-2^63和2^63-1.双数也可以表示数的分数，但在高数时，它甚至不能代表每一个数。

例如，在100000000000000000000000000000000000000000000000000之后可以表示的下一个双是100000000000000030000000000000000000000000000000000 --所以您是一个巨大的30000000000000000000000000000000000000000000000，您不能用一个双倍来表示。

你在试图修复一些你不应该费心去修理的东西。使用long，您的方法可能会返回一个固定的最大返回值。您的方法应该清楚地说明如果溢出会发生什么，并且您可能希望处理这种溢出(例如使用Math#multiplyExactly)，但是如果您应该返回的返回值很长，那么应该使用它。

Answer 2

您可以将结果保存在一个多头数组中，让我们将其称为result[]。首先，将逻辑应用于result[0]。但是，当这个值变为负值时，

1) result[1]增加值为超额值。2)现在，你的逻辑变得更加混乱，我正在打我的电话，所以这部分是留给读者的练习。3)当result[1]溢出时，从result[2]...开始

当你打印结果时，把结果组合起来，再一次，逻辑混乱。

我认为这就是BigInteger的工作方式(或多或少)？我从没看过那个代码，你可能会想看的。

但基本上，波利尼翁是正确的。如果没有相当大的解决办法，就会有一个上限。