有什么方式来确定，如果一个Int是一个完全平方在Haskell?

StackOverflow https://stackoverflow.com/questions/2807686

  •  25-09-2019
  •  | 
  •  

题

我需要一个简单的功能

is_square :: Int -> Bool

它决定如果一个Int N一个完全平方(是否有一个整数x x*x=N)。

我当然可以只是写点东西喜欢

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

但是它看起来太可怕了！也许有一个共同的简单的方法来实现这样的一个判断?

有帮助吗？

解决方案 5

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

所以，我想出了一个相当聪明替代

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

很简单。我想，我需要使用一个树更快的查找速度，但现在我会尝试这种解决方案，也许这将是速度不够快我的任务。如果没有，我会编辑与适当的数据结构的答案

其他提示

想想这样说，如果你有一个积极的INT n，那么你基本上做的数字从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）的。易于修改完善立方体和更高的权力。

还有一个 美妙的 图书馆为多数一些理论相关问题包括在Haskell arithmoi 包。

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

具体地说的 isSquare' 功能。

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

库进行了优化，以及审查人员更多专门的效率，那么你或I虽然目前没有 这种恶作剧 会上的发动机罩下，它可能在未来作为图书馆的发展并得到更加优化。 看源代码 要了解它是如何工作的！

不要重新发明轮子，始终使用一个图书馆。

我觉得你提供的代码是最快的，你会得到：

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

在此代码的复杂性是：一个SQRT，一个双乘法，一个铸造（dbl-> INT），和一个比较。你可以尝试使用其他的计算方法，以取代开方，并只整数运算和班次倍增，但机会是它不会是快于一个开方和一个乘法。

在那里它可能是值得使用另一种方法唯一的地方是，如果CPU在其上运行的不支持浮点运算。在这种情况下，编译器可能要生成软件开方和双乘法，你可以在你的特定应用优化得到的优势。

正如所指出的其他答案，但仍有大整数的限制，但除非你要碰上这些数字，它可能是更好地利用浮点硬件支持的不是写自己的算法。

Wikipedia的整型平方根文章具有算法可以是调整以适应您的需求。牛顿的方法是好的，因为它收敛平方，即，你尽可能多的正确的数字得到两倍的每一步。

我会建议你从Double远离如果输入可能比2^53更大，之后不是所有的整数可以准确地表示为Double。

有时你不应该划分成问题太小的部件（例如检查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

有一个非常简单的方法来测试一个完美的正方形 - 毫不夸张地说，你检查数的平方根比在它的小数部分零以外的任何结果。 我假设平方根函数返回一个浮点，在这种情况下，可以做（伪码）：

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

在另一个回答这个问题评论，您讨论记忆化。请记住，这种技术有助于在探头模式具有良好的密度。在这种情况下，这将意味着遍地测试相同的整数。怎么可能是你的代码重复相同的工作，从而受益于缓存的答案？

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

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
              ]

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

“定时概率密度”

这不是特别漂亮或快，但这里是基于牛顿法无铸，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

它也许可以具有一些附加的数论诡计加快。

许可以下： CC-BY-SA 和 归因
不隶属于 StackOverflow
scroll top