首页 文章

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

提问于
浏览 次
13

我需要一个简单的功能

is_square :: Int -> Bool

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

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

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

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

algorithm haskell sqrt

9 回答

  • 1

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

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

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

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

    回复于
  • 1

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

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

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

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

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

    回复于
  • 8

    可以这样想，如果你有一个正的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） . 易于修改完美的立方体和更高的功率 .

    回复于
  • 1

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

    使用Math.NumberTheory.Powers.Squares库 .

    具体是isSquare'函数 .

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

    图书馆经过了优化，并且受到了人们的高度评价，而后者则更加专注于提高效率 . 虽然它目前还没有发布，但随着图书馆的发展和更加优化，它可能会在未来发展 . View the source code了解它是如何工作的！

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

    回复于
  • 1

    维基百科的article on Integer Square Roots算法可以根据您的需求进行调整 . 牛顿的方法很好，因为它以二次方式收敛，即每步得到两倍的正确数字 .

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

    回复于
  • 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
    回复于
  • 0

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

    func IsSquare（N）
    sq = sqrt（N）
    return（sq modulus 1.0）等于0.0

    回复于
  • 9

    在对此问题的另一个答案的评论中，您讨论了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
              ]

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

    timing probability-density

    回复于
  • 1

    它不是特别漂亮或快速，但是这里是一个基于牛顿方法的无投射，无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

    它可能会加速一些额外的数论诡计 .

    回复于

相关问题