algorithm - 确定 Int 是否为 Haskell 中的完美正方形的方法是什么？

Question

我需要一个简单的函数

is_square :: Int -> Bool

它确定 Int N 是否为完全平方(是否存在满足 x*x = N 的整数 x)。

当然我也可以这样写

is_square n = sq * sq == n
    where sq = floor $ sqrt $ (fromIntegral n::Double)

但看起来很糟糕!也许有一种通用的简单方法来实现这样的谓词？

Answer 1

这样想，如果您有一个正整数 n，那么您基本上是在从 1 到 n 的数字范围内进行二进制搜索以找到第一个数字 n' 其中 n' * n' = n。

我不懂 Haskell，但是这个 F# 应该很容易转换:

let is_perfect_square n =
    let rec binary_search low high =
        let mid = (high + low) / 2
        let midSquare = mid * mid

        if low > high then false
        elif n = midSquare then true
        else if n < midSquare then binary_search low (mid - 1)
        else binary_search (mid + 1) high

    binary_search 1 n

保证为 O(log n)。易于修改完美的立方体和更高的功率。