F# Int 上的平方根

Question

我正在用 F# 构建一个程序，我需要在其中计算整数值的平方根。我搜索并找到了 none 函数，它允许在不使用强制转换的情况下执行此操作 int -> float.

是否有一个函数可以在不进行不必要的强制转换的情况下计算整数的平方根？

Answer 1

如果您只想要一个接受整数和 returns 其平方根作为浮点数的函数，则使用 float 函数将整数转换为浮点数，然后调用 sqrt 是要走的路：

sqrt (float n)

原则上，F# 可以隐式允许这种转换，但我认为它不会这样做，因为它不清楚整数的平方根应该是什么（如评论中所讨论的）。在 C# 中，您可以编写 Math.Sqrt(n)，但这是可行的，因为 C# 允许在程序的任何位置从 int 隐式转换为 float。

如果整数 returns 整数需要平方根，则没有标准的方法（如评论中所述），因此由您来实现所需的功能。

Answer 2

我很难理解为什么对 int 输入的限制，但如果这很重要，可以采用分而治之的算法。在任何具有硬件浮动的 CPU 架构上，这比 sqrt (float n) 慢很多。

let isqrt n =
  let rec loop b e =
    let i = (b + e) >>> 1
    let i2 = i*i
    if i2 = n then
      i
    else
      let nb, ne =
        if i2 > n then
          b, i
        else
          i, e
      if nb = b && ne = e then
        // Check i - 1 and i + 1 to see if either is a better fit than i
        let imin  = i - 1
        let imax  = i + 1
        let i2min = imin*imin
        let i2max = imax*imax
        let d     = n - i2    |> abs
        let dmin  = n - i2min |> abs
        let dmax  = n - i2max |> abs
        if d < dmin && d < dmax then
          i
        elif dmin < dmax then
          imin
        else
          imax

      else
        loop nb ne
  loop 1 n

open FsCheck

let isqrtProperty n =
  n > 1 ==> fun () ->
    let r     = isqrt n
    let rmin  = r - 1
    let rmax  = r + 1

    let r2    = r*r
    let rmin2 = rmin*rmin
    let rmax2 = rmax*rmax

    let d     = n - r2     |> abs
    let dmin  = n - rmin2  |> abs
    let dmax  = n - rmax2  |> abs

    r >= 0 && d <= dmin && d <= dmax

[<EntryPoint>]
let main argv =
  let config = { Config.Quick with MaxTest = 10000; MaxFail = 100000 }
  Check.One ("isqrt property", config, isqrtProperty)
  0

F# Int 上的平方根

F# Square Root on Int

floating-point

int

f#

types

sqrt