如何确定Int是否是Haskell中的完美正方形？

Question

我需要一个简单的函数

is_square :: Int -> Bool 

，其确定一个Int N A完美的正方形（是否有一个整数x，使得x * X = N）。

当然我可以只写类似

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

，但它看起来很可怕！也许有一个简单的方法来实现这样的谓词？

Answer 1

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

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

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

很简单。我认为，我需要使用树来进行更快速的查找，但现在我会尝试这种解决方案，也许它对我的任务来说足够快。如果没有，我会适当的数据结构

Answer 2

维基百科的article on Integer Square Roots算法可以适应您的需要。牛顿的方法很好，因为它以二次方式收敛，即每一步你得到两倍的正确数字。

如果输入可能大于2^53，那么我建议您远离Double，在这之后不是所有整数都可以精确地表示为Double。

Answer 3

我想您所提供的代码是最快的，你会得到：

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

的这段代码的复杂性：一个平方根，一个双乘法，一个投（dbl-> INT）和一个比较。您可以尝试使用其他计算方法来替换sqrt和乘法，只用整数算术和移位，但有可能它不会比一个sqrt和一个乘法更快。

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

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

Answer 4

这不是特别漂亮或快，但这里是基于牛顿法的作品（慢）的自由铸造，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 

它也许可以用加速一些额外的数字理论欺骗。

Answer 5

有时编辑答案你不应该划分问题转化成过小零件（如检查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 

Answer 6

有一个很简单的方法来测试完美正方形 - 从字面上看，你检查数字的平方根是否在其小数部分不是零。
我假设平方根函数返回一个浮点，在这种情况下，你可以做的（伪代码）：

func IsSquare(N) 
    sq = sqrt(N) 
    return (sq modulus 1.0) equals 0.0 

Answer 7

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

你没有给我们您输入的分布的概念，所以考虑采用了优秀的criterion包快速基准：

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 
       ] 

这个工作量可能会或可能不会是一个公平代表什么你正在做，但写的，高速缓存未命中率显得过高：

Answer 8

认为它这样，如果你有一个积极INT n，那么你基本上干什么g在1 .. n的数字范围上进行二进制搜索，找到第一个数字n'，其中n' * n' = n。

我不知道哈斯克尔，但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 9

有一个精彩库包含在arithmoi包中包含的Haskell中的大多数数论相关问题。使用Math.NumberTheory.Powers.Squares库。

具体为isSquare'函数。

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

图书馆作为图书馆的演进优化，深受人们更专注于效率的审核，那么你或I.虽然目前没有this kind of shenanigans引擎盖下的机制，它可以在未来，获得更多优化。 View the source code了解它是如何工作的！

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