在哈斯克尔,怎样确定一个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(对数N)。易于修改完美的立方体和更高的功率。

有一个 精彩的 哈斯凯尔大多数数论相关问题的图书馆 arithmoi 包裹。

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

特别是 isSquare' 功能。

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

图书馆是经过优化和审查的,比你或我更加注重效率。虽然它目前还没有 this kind of shenanigans 在这种情况下,随着图书馆的发展,它将来可能会变得更加优化。 View the source code 了解它是如何工作的!

不要重新发明轮子,只要有图书馆就一定要用。

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

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

此代码的复杂性是:一个sqrt、一个双乘法、一个cast(dbl->int)和一个比较。您可以尝试使用其他计算方法来用整数算术和移位替换sqrt和乘法,但很可能它不会比一个sqrt和一个乘法更快。

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

正如其他答案所指出的,大整数仍然有一个限制,但是除非你要碰到这些数字,否则利用浮点硬件支持可能比编写自己的算法更好。

维基百科 article on Integer Square Roots HAS算法可以根据您的需要进行调整。牛顿的方法很好,因为它是四次收敛的,也就是说,每一步得到两倍的正确数字。

我建议你远离 Double 如果输入可能大于 2^53 ,之后不是所有整数都可以精确表示为 双重的 .

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

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

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

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

有时候你不应该把问题分成太小的部分(比如支票) 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

有一个非常简单的方法来测试一个完美的平方-相当准确地说,你要检查这个数字的平方根在小数部分是否有除零以外的任何东西。
我假设一个平方根函数返回一个浮点,在这种情况下,您可以这样做(psuedocode):

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

在对这个问题的另一个答案的评论中,您讨论了memoization。请记住,这项技术有助于当您的探针模式显示出良好的密度。在这种情况下,这意味着反复测试相同的整数。您的代码重复相同的工作从而从缓存答案中获益的可能性有多大?

您没有告诉我们您输入的分布情况,因此考虑使用卓越的快速基准 criteria package:。

您没有告诉我们您输入的分布情况,因此请考虑使用 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
              ]

此工作负载可能代表您正在做的工作,也可能不代表您正在做的工作,但正如所写,缓存未命中率似乎过高:

它不是特别漂亮,也不是很快,但是这里有一个基于牛顿方法的无铸,无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

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