16

我需要一个简单的功能

is_square :: Int -> Bool

它确定 Int N 是否为完美正方形（是否存在整数 x 使得 x*x = N）。

当然我可以写一些像

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

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

4

9 回答 9

10

这样想，如果你有一个正的 int n，那么你基本上是在从 1 .. n 的数字范围上进行二进制搜索，以找到第一个数字n'where 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)。易于修改完美的立方体和更高的功率。

于 2010-05-11T19:46:26.123 回答
10

Haskell 中包含一个很棒的库，可以解决大多数与数论相关的问题arithmoi。

使用Math.NumberTheory.Powers.Squares图书馆。

具体isSquare'功能。

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

该库经过优化，并由比您或我更致力于效率的人进行了良好的审查。虽然它目前没有这种恶作剧在幕后进行，但随着图书馆的发展和更加优化，它可能会在未来发生。查看源代码以了解其工作原理！

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

于 2014-07-10T13:55:48.487 回答
6

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

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

这段代码的复杂度是：一次sqrt，一次双乘，一次强制转换（dbl->int），一次比较。您可以尝试使用其他计算方法来仅用整数算术和移位来替换 sqrt 和乘法，但它可能不会比一个 sqrt 和一个乘法更快。

唯一值得使用另一种方法的地方是，如果您正在运行的 CPU 不支持浮点运算。在这种情况下，编译器可能必须在软件中生成 sqrt 和双倍乘法，您可以在针对特定应用程序进行优化时获得优势。

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

于 2010-05-11T03:15:58.653 回答
2

在对此问题的另一个答案的评论中，您讨论了memoization。请记住，当您的探针图案表现出良好的密度时，此技术会有所帮助。在这种情况下，这意味着一遍又一遍地测试相同的整数。您的代码重复相同工作并因此受益于缓存答案的可能性有多大？

您没有向我们提供输入分布的概念，因此请考虑使用出色的标准包的快速基准测试：

module Main
where

import Criterion.Main
import Random

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

is_square_mem =
  let check n = sq * sq == n
        where sq = floor $ sqrt $ (fromIntegral n :: Double)
  in (map check [0..] !!)

main = do
  g <- newStdGen
  let rs = take 10000 $ randomRs (0,1000::Int) g
      direct = map is_square
      memo   = map is_square_mem
  defaultMain [ bench "direct" $ whnf direct rs
              , bench "memo"   $ whnf memo   rs
              ]

此工作负载可能代表也可能不代表您正在做的事情，但正如所写，缓存未命中率似乎太高：

时间概率密度

于 2010-05-11T19:17:33.677 回答
1

维基百科关于整数平方根的文章有算法可以适应您的需要。牛顿的方法很好，因为它是二次收敛的，即每一步你得到两倍的正确数字。

Double如果输入可能大于，我会建议您远离2^53，之后并非所有整数都可以精确表示为Double。

于 2010-05-11T02:39:40.783 回答
1

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

所以，我想出了一个非常聪明的选择

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

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

于 2010-05-11T18:09:17.207 回答
1

有时你不应该把问题分成太小的部分（比如检查is_square）：

intersectSorted [] _ = []
intersectSorted _ [] = []
intersectSorted xs (y:ys) | head xs > y = intersectSorted xs ys
intersectSorted (x:xs) ys | head ys > x = intersectSorted xs ys
intersectSorted (x:xs) (y:ys) | x == y = x : intersectSorted xs ys

squares = [x*x | x <- [ 1..]]
weird = [2*x+1 | x <- [ 1..]]

perfectSquareWeird = intersectSorted squares weird
于 2010-05-11T18:20:18.403 回答
1

有一种非常简单的方法可以测试一个完美的平方 - 从字面上看，你检查数字的平方根在它的小数部分是否有除零以外的任何东西。
我假设一个返回浮点的平方根函数，在这种情况下你可以这样做（Psuedocode）： 

func IsSquare(N)  
   sq = sqrt(N)
   return (sq modulus 1.0) equals 0.0
于 2010-05-11T18:59:31.380 回答
0

它不是特别漂亮或快速，但这是一个基于牛顿方法的无强制转换、无 FPA 版本，它（缓慢）适用于任意大的整数：

import Control.Applicative ((<*>))
import Control.Monad (join)
import Data.Ratio ((%))

isSquare = (==) =<< (^2) . floor . (join g <*> join f) . (%1)
  where
    f n x = (x + n / x) / 2
    g n x y | abs (x - y) > 1 = g n y $ f n y
            | otherwise       = y

它可能会通过一些额外的数论技巧来加速。

于 2010-05-11T14:46:51.320 回答