Quelle est la façon de déterminer si un Int est un carré parfait en Haskell?

Question

J'ai besoin d'une fonction simple

is_square :: Int -> Bool

qui détermine si une Int N un carré parfait (y est un nombre entier x tel que x * x = N).

Bien sûr, je peux écrire quelque chose comme

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

mais il a l'air terrible! Peut-être il y a un moyen simple commune de mettre en œuvre un tel prédicat?

Answer 1

Oh, je avais besoin aujourd'hui pour déterminer si un nombre est cube parfait, et une solution similaire a été très lent.

Alors, je suis venu avec une alternative assez intelligent

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

Très simple. Je pense, je dois utiliser un arbre pour des recherches plus rapides, mais maintenant je vais essayer cette solution, ce sera peut-être assez rapide pour ma tâche. Sinon, je vais modifier la réponse avec une bonne structure de données

Answer 2

Pensez-y de cette façon, si vous avez un n int positif, alors que vous faites essentiellement une recherche binaire sur la plage de nombres de 1 .. n pour trouver le premier numéro n' où n' * n' = n.

Je ne sais pas Haskell, mais F # devrait être facile à convertir:

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

Garanti pour être O (log n). Facile à modifier des cubes parfaits et des puissances plus élevées.

Answer 3

Il y a un merveilleux bibliothèque pour la plupart la théorie des nombres problèmes liés à Haskell inclus dans le arithmoi package .

Utilisez le Math.NumberTheory.Powers.Squares bibliothèque .

Plus précisément, le isSquare' fonction.

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

La bibliothèque est optimisée et bien des gens beaucoup Info brute plus en termes d'économie vous ou I. Bien qu'il ne dispose pas actuellement ce genre de manigances passe sous le capot, il pourrait à l'avenir que la bibliothèque évolue et devient plus optimisés. Voir la source Code pour comprendre comment il fonctionne!

Ne pas réinventer la roue, utilisez toujours une bibliothèque lorsqu'ils sont disponibles.

Answer 4

Je pense que le code que vous avez fourni est le plus rapide que vous allez obtenir:

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

La complexité de ce code est: une sqrt, une double multiplication, une coulée (dbl-> int), et une comparaison. Vous pouvez essayer d'utiliser d'autres méthodes de calcul pour remplacer la racine carrée et la multiplication avec l'arithmétique tout entier et des changements, mais il est probable qu'il ne va pas être plus rapide que l'un et sqrt une multiplication.

Le seul endroit où il pourrait être intéressant d'utiliser une autre méthode est si le processeur sur lequel vous utilisez ne supporte pas l'arithmétique en virgule flottante. Dans ce cas, le compilateur devra probablement générer sqrt et double multiplication dans le logiciel, et vous pourriez obtenir un avantage dans l'optimisation pour votre application.

Comme l'a souligné d'autre réponse, il y a encore une limitation des grands entiers, mais à moins que vous allez courir dans ces chiffres, il est sans doute préférable de profiter du point flottant support matériel que d'écrire votre propre algorithme.

Answer 5

Wikipedia Entier place Roots a des algorithmes peuvent être adapté à vos besoins. La méthode de Newton est agréable car elle converge quadratiquement, à savoir, vous obtenez deux fois plus de chiffres corrects chaque étape.

Je vous conseille de rester loin de Double si l'entrée est peut-être plus grand que 2^53, après quoi pas tous les entiers peuvent être exactement représentés comme Double.

Answer 6

Parfois, vous ne devriez pas diviser les problèmes en pièces trop petites (comme les chèques 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 7

Il y a un moyen très simple pour tester un carré parfait - littéralement, vous vérifiez si la racine carrée du nombre a rien d'autre que zéro dans la partie décimale de celui-ci
. Je suppose une fonction de racine carrée qui retourne un point flottant, auquel cas vous pouvez faire (psuedocode):

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

Answer 8

Dans un commentaire sur une autre réponse à cette question, vous avez discuté memoization . Gardez à l'esprit que cette technique aide lorsque vos modèles de sondes présentent une bonne densité. Dans ce cas, cela voudrait dire tester les mêmes entiers à plusieurs reprises. Quelle est la probabilité de votre code de répéter le même travail et ainsi bénéficier de réponses de mise en cache?

Vous ne nous avez pas une idée de la distribution de vos entrées, donc envisager une référence rapide qui utilise l'excellent critère package:

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
              ]

Cette charge de travail peut ou ne peut pas être un représentant juste de ce que vous faites, mais comme il est écrit, le taux de défaut de cache apparaît trop élevé:

Answer 9

Il est pas particulièrement jolie ou rapide, mais voici un sans casting, la version FPA-libre basé sur la méthode de Newton qui fonctionne (lentement) pour les entiers arbitrairement grands:

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

Il pourrait probablement être accéléré avec une supercherie de la théorie des nombres supplémentaires.