java - 计算大根：bigdecimal / java

Question

我尝试使用标准迭代算法来计算第 n 个根。

例如 (111^123)^(1/123)。

标准算法计算基数的高次幂（在本例中为 111^123），这需要大量时间。该算法在这里给出http://en.wikipedia.org/wiki/Nth_root_algorithm

但是，我注意到使用双精度的同一件事不到一毫秒。所以很明显他们使用了一些聪明的想法。对此有任何提示吗？

Answer 1

但是，我注意到使用双精度的同一件事不到一毫秒。所以很明显他们使用了一些聪明的想法。

并不真地。double只是精度有限，所以它基本上只需要计算结果的最高有效 52 位，并且可以跳过其余的计算。当然，在硬件中实现这一点也有帮助。

Answer 2

尝试使用二进制求幂。我的意思是做：

111 * 111 = 111^2，现在你知道 111^2 是什么，你现在可以通过 (111^2) * (111^2) 来计算 111^4。这是整个序列（请注意，这可能不是最有效的方法）。

111 * 111 = 111^2
111^2 * 111^2 = 111^4
111^4 * 111^4 = 111^8
111^8 * 111^8 = 111^16
111^16 * 111^16 = 111^32
111^32 * 111^32 = 111^64
111^64 * 111^32 = 111^96
111^96 * 111^16 = 111^112
111^112 * 111^8 = 111^120
111^120 * 111^2 * 111^1 = 111^123.