java - java中最快的分解过程

Question

我正在用 java 编写一个程序，该程序可以计算给定值的 sqrt 高达 10^100 。为此，我知道我必须使用 BigInteger，但我正在处理的过程效率不高，因为它需要很多时间。分解一个数字以处理程序的最快过程是什么？更快的算法是什么？

提前致谢。

Answer 1

首先，我希望您意识到大多数输入值不会有平方根的精确整数答案！您确定要使用 BigInteger 而不是 BigDecimal 执行此操作吗？

你肯定不想遍历每个值直到 n。您需要一种方法来更快地改进您的答案。一个简单的方法是对平方根的值进行初始猜测（我推荐 n/2），然后找到它的协因数（n/guess）。如果它们相等，您就完成了，如果它们不相等，则将您的猜测更新为猜测及其辅因子的平均值——其中一个将大于实际平方根，另一个将是更小，因此平均将产生更接近实际平方根的值。起泡，冲洗，重复。如果没有精确的平方根，当因子和辅因子彼此相差 1 时停止。

附录：这里是伪代码（实际上是 Ruby，但这几乎是一回事）：

def sqrt(n)
  guess = n / 2
  cofactor = 2
  loop do
    cofactor = n / guess
    break if (guess - cofactor).abs <= 1
    guess = (guess + cofactor) / 2
  end
  return [guess, cofactor].min
end

翻译成 Java 应该很简单。