如何確定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瞭解它是如何工作的！

不要重新發明輪子，在可用時總是使用圖書館。