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

Question

我需要一个简单的功能

is_square :: Int -> Bool

它确定Int N是否是一个完美的正方形(是否存在整数x,使得x*x = N).

当然我可以写一些类似的东西

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

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

Answer 1

想想这样说,如果你有一个积极的INT 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).易于修改完美的立方体和更高的功率.

Answer 2

对于Haskell中包含的大多数数论相关问题,有一个很棒的库arithmoi.

使用该Math.NumberTheory.Powers.Squares库.

特别是isSquare'功能.

is_square :: Int -> Bool
is_square = isSquare' . fromIntegral

图书馆经过优化,并且受到人们更加专注于提高效率的人们的审查.虽然目前还没有这种恶作剧,但随着图书馆的发展和更加优化,它可能会在未来发生.查看源代码以了解其工作原理!

不要重新发明轮子,总是在可用时使用库.

Answer 3

我认为您提供的代码是您获得的最快的代码:

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

这段代码的复杂性是:一个sqrt,一个double乘法,一个cast(dbl-> int)和一个比较.您可以尝试使用其他计算方法将sqrt和乘法替换为仅整数算术和移位,但可能不会比一个sqrt和一个乘法更快.

唯一值得使用其他方法的地方是运行的CPU不支持浮点运算.在这种情况下,编译器可能必须在软件中生成sqrt和double乘法,并且您可以优化您的特定应用程序.

正如其他答案所指出的那样,仍然存在大整数的限制,但除非你要遇到这些数字,否则利用浮点硬件支持比编写自己的算法更好.

Answer 4

哦，今天我需要确定一个数字是否是完美的立方，类似的解决方案非常慢。

所以，我想出了一个非常聪明的替代方案

cubes = map (\x -> x*x*x) [1..]
is_cube n = n == (head $ dropWhile (<n) cubes)

很简单。我想，我需要使用树来更快地查找，但现在我将尝试这个解决方案，也许它对于我的任务来说足够快。如果没有，我将使用正确的数据结构编辑答案