修复递归求幂法？

我目前正在研究使用递归进行指数计算的方法。这是我到目前为止：修复递归求幂法？

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然后就给我0.有没有办法解决这个问题？我知道我可以将long改为double，而且我的方法可以很好地工作。但是，我的教授要求我们使用long。感谢您的帮助！

来源

2016-04-13 name

[Long.MAX_VALUE]（http://docs.oracle.com/javase/8/docs/api/java/lang/Long.html#MAX_VALUE）。 – rgettman

@rgettman我明白这一点。我想知道是否有一种方法可以解决这个问题。我知道这可能听起来像一个愚蠢的问题，但由于我是编程新手，我以为我应该问问并看看。 – name

@ug_哦，好的。但为什么当我把长变成双倍时，它会对更大的价值起作用？ – name

long可以表示的最大值是2^63 -1。所以，如果你计算2^63，那么它就会更大，那么一个长期可以持有和包装的东西就会变大。 Long表示使用twos-complement。

只要将长变为两倍并不完全正常。它改变了方法的语义。浮点数的精度非常有限。对于64位浮点数，您仍然只能表示与64位整数相同数量的数字。他们只是分布不同。一个long可以代表-2^63和2^63-1中的每个整数。双数也可以表示数字的小数部分，但数量很高时，它甚至不能代表每个数字。

例如，下一双可以代表后100000000000000000000000000000000000000000000000000是100000000000000030000000000000000000000000000000000 - 所以你missiong高达30000000000000000000000000000000000你不能用双重代表。

您正试图解决您不应该打扰修复的问题。使用很长时间，您的方法可能会返回一个固定的最大返回值。你的方法应该清楚地说明如果它溢出会发生什么，你可能想要处理这种溢出（例如使用Math#multiplyExactly），但如果long是你应该返回的返回值，那么这就是你应该使用的。

来源

2016-04-13 18:07:49 Polygnome

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

1）增量result[1]超过。 2）现在，你的逻辑变得更加混乱，我正在打电话给我的手机，所以这部分留给读者作为练习。 3）当result[1]溢出时，在result[2]...上启动

当您打印结果时，再次合并结果，逻辑混乱。

我认为这是BigInteger的工作原理（或多或少）？我从来没有看过那个代码，你可能会想。

但是，基本上，Polygnone是正确的。没有相当多的解决方法，就有一个上限。

来源

2016-04-13 18:23:55 user949300

修复递归求幂法？

回答

相关问题