SCALA：BigInt 的平方根函数

Question

我在互联网上搜索了一个使用 scala 编程语言查找 BigInt 的精确平方根的函数。我没有得到一个，但是看到了一个 Java 程序，我将该函数转换为 Scala 版本。它正在工作，但我不确定它是否可以处理非常大的 BigInt。但它 return 只是 BigInt。不是 BigDecimal 作为平方根。它表明在代码中进行了一些位操作，并对数字进行了一些硬编码，例如 shiftRight(5), BigInt("8") and shiftRight(1)。我可以清楚地理解逻辑，但不是这些移位数和数字 8 的硬编码。可能这些移位函数在 scala 中不可用，这就是为什么需要在少数地方转换为 java BigInteger .这些硬编码数字可能会影响 result.I 的精度，只是将 java 代码更改为 scala 代码，只是复制了确切的算法。这是我用 scala 编写的代码：

   def sqt(n:BigInt):BigInt = {
      var a = BigInt(1)
      var b = (n>>5)+BigInt(8)
      while((b-a) >= 0) {
          var mid:BigInt = (a+b)>>1
          if(mid*mid-n> 0) b = mid-1
          else a = mid+1
         }
      a-1
   }

我的积分是：

我们不能 return BigDecimal 而不是 BigInt 吗？我们该怎么做？
这些硬编码数字 shiftRight(5), shiftRight(1) and 8 是如何关联的结果的精度。

我在 scala REPL 中测试了一个数字：函数 sqt 给出平方数的精确平方根。但不是下面的实际数字：

scala> sqt(BigInt("19928937494873929279191794189"))
res9: BigInt = 141169888768369

scala> res9*res9
res10: scala.math.BigInt = 19928937494873675935734920161

scala> sqt(res10)
res11: BigInt = 141169888768369

scala>

我明白了shiftRight(5) means divide by 2^5 ie.by 32 in decimal等等..但是为什么在shift操作后这里加了8？为什么恰好是5班？作为第一个猜测？

Answer 1

Can't we return a BigDecimal instead of BigInt? How can we do that?

如果您想要精确根，这就没有意义：如果 BigInt 的平方根可以用 BigDecimal 精确表示，则可以用 BigInt 表示。如果您不想要精确根，则需要指定精度并修改算法（在大多数情况下，Double 就足够了，而且比 BigDecimal 快得多）。

I understand shiftRight(5) means divide by 2^5 ie.by 32 in decimal and so on..but why 8 is added here after shift operation? why exactly 5 shifts? as a first guess?

这些不是唯一的选择。重点是对于每个正数 n、n/32 + 8 >= sqrt(n)（其中 sqrt 是数学平方根）。这是最容易通过一些微积分来显示的（或者只是通过构建差异图）。所以一开始我们知道 a <= sqrt(n) <= b（除非 n == 0 可以单独检查），并且您可以验证这在每一步都保持正确。

Answer 2

你的问题1和问题3其实是同一个问题

How [do] these bitshifts impact [the] precision of the result?

他们没有。

How [are] these hardcoded numbers ... related to precision of the result?

他们不是。

对于estimating/calculating一个数的平方根有很多不同的methods/algorithms（可见here）。您发布的算法似乎是一种非常直接的二进制搜索。

选择一个保证小于目标（n 的平方根）的数字a。
选择一个保证大于目标（n 的平方根）的数字b。
计算mid，a和b之间的整数中点。
如果 mid 大于（或等于）目标，则将 b 移动到 mid（-1 因为我们知道它太大了）。
如果 mid 小于目标，则将 a 移动到 mid（+1 因为我们知道它太小了）。
重复 3,4,5 直到 a 不再小于 b.
Return a-1 作为 n 的平方根四舍五入为整数 .

移位和硬编码数字用于选择 b 的初始值。但是 b 只有大于目标。我们本可以完成 var b = n。为什么这么麻烦？

一切都与效率有关。 b 越接近目标，找到结果所需的迭代次数就越少。为什么要在移位后加8？因为 31>>5 为零，不大于目标。作者选择了 (n>>5)+8 但 he/she 可能选择了 (n>>7)+12。有取舍。

Can't we return a BigDecimal instead of BigInt? How can we do that?

这是一种方法。

def sqt(n:BigInt) :BigDecimal = {
  val d = BigDecimal(n)
  var a = BigDecimal(1.0)
  var b = d
  while(b-a >= 0) {
    val mid = (a+b)/2
    if (mid*mid-d > 0) b = mid-0.0001  //adjust down
    else               a = mid+0.0001  //adjust up
  }
  b
}

计算浮点平方根值有更好的算法。在这种情况下，您可以通过使用较小的调整值获得更好的精度，但效率会变得更差。

SCALA：BigInt 的平方根函数

SCALA: Function for Square root of BigInt

scala

square-root