SCALA：BigInt 平方根的函数

Question

我在互联网上搜索了一个函数来使用 Scala 编程语言找到 BigInt 的精确平方根。我没有得到，但看到了一个 Java 程序，我将该函数转换为 Scala 版本。它正在工作，但我不确定它是否可以处理非常大的 BigInt。但它只返回 BigInt。不是 BigDecimal 作为平方根。它表明在代码中进行了一些位操作，并使用了一些数字的硬编码，例如shiftRight(5), BigInt("8") and shiftRight(1). 我可以清楚地理解逻辑，但不是这些位移数字和数字 8 的硬编码。可能是这些位移功能在 Scala 中不可用，这就是为什么需要在少数地方转换为 java BigInteger 的原因。这些硬编码的数字可能会影响结果的精度。我只是将 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
   }

我的要点是：

1. 我们不能返回 BigDecimal 而不是 BigInt 吗？我们怎么做？
2. 这些硬编码数字如何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等等..但是为什么在移位操作后在这里添加 8？为什么正好是 5 个班次？作为第一个猜测？

Answer 1

你的问题1和问题3实际上是同一个问题。

1. 这些位移如何影响结果的精度？

他们没有。

3. 这些硬编码数字如何……与结果的精度有关？

他们不是。

有用于估计/计算数的平方根（如可以看到的许多不同的方法/算法在这里）。您发布的算法似乎是一个非常简单的二分搜索。

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

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

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

2. 我们不能返回 BigDecimal 而不是 BigInt 吗？我们怎么做？

这是一种方法。

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
}

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