Was ist der Weg, um zu bestimmen, ob ein Int ein perfektes Quadrat in Haskell ist?

Question

Ich brauche eine einfache Funktion

is_square :: Int -> Bool

, die, wenn ein Int N eine Quadratzahl bestimmt (es ist eine solche ganze Zahl x, das x * x = N).

Natürlich kann ich einfach etwas schreiben wie

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

, aber es sieht schrecklich aus! Vielleicht gibt es eine gemeinsame einfache Art und Weise ein solches Prädikat zu implementieren?

Answer 1

Oh, heute ich brauchte, um zu bestimmen, ob eine Zahl ist perfekt Würfel und ähnliche Lösung war sehr langsam.

So kam ich mit einem ziemlich clevere Alternative

nach oben

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

Sehr einfach. Ich denke, ich brauche einen Baum für schnellere Lookups zu verwenden, aber jetzt werde ich diese Lösung versuchen, vielleicht wird es schnell genug für meine Aufgabe sein. Wenn nicht, werde ich die Antwort mit dem richtigen Datenstruktur bearbeiten

Answer 2

Denken Sie an es auf diese Weise, wenn Sie eine positive int n haben, dann sind Sie im Grunde eine binäre Suche auf den Bereich der Zahlen von 1 zu tun .. n die erste Nummer n' zu finden, wo n' * n' = n.

Ich weiß nicht, Haskell, aber das F # sollte einfach zu konvertieren sein:

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

Garantierte O (log n) sein. Leicht zu ändern perfekte Würfel und höhere Leistungen.

Answer 3

Es gibt eine wunderbar Bibliothek für die meisten Zahlentheorie Probleme im Zusammenhang mit in Haskell, die in der arithmoi Paket.

Mit dem Math.NumberTheory.Powers.Squares Bibliothek.

Insbesondere die isSquare' Funktion.

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

Die Bibliothek wird optimiert und auch von den Menschen viel mehr gewidmet Effizienz überprüfte dann Sie oder I. Während es im Moment keine diese Art von Spielchen unter der Haube geht auf, als die Bibliothek entwickelt sich in der Zukunft könnte und optimiert wird. die Quelle anzeigen Code zu verstehen, wie es funktioniert!

Setzen Sie das Rad nicht neu erfinden, immer eine Bibliothek verwenden, wenn verfügbar.

Answer 4

Ich denke, der Code, den Sie zur Verfügung gestellt ist der schnellste, den Sie bekommen werden:

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

Die Komplexität dieses Codes ist: ein sqrt, ein Doppel Multiplikation, ein Guss (dbl-> int) und ein Vergleich. Sie könnten versuchen, andere Berechnungsmethoden zu verwenden, um die sqrt und die Multiplikation mit nur Integer-Arithmetik und Verschiebungen zu ersetzen, aber die Chancen sind es nicht schneller als ein sqrt und eine Multiplikation sein wird.

Der einzige Ort, wo es sich lohnen könnte andere Methode verwendet, ist, wenn die CPU auf dem Sie laufen nicht unterstützt Gleitkomma-Arithmetik. In diesem Fall wird der Compiler muss wahrscheinlich sqrt und doppelte Multiplikation in der Software erzeugen, und man kann Vorteil bei der Optimierung für Ihre spezifische Anwendung bekommen.

Wie bereits durch andere Antwort, gibt es noch eine Begrenzung der großen ganze Zahlen, aber wenn man in diese Zahlen gehen laufen, ist es wahrscheinlich besser, die Vorteile der Floating-Point-Hardware-Unterstützung zu nehmen, als Sie Ihren eigenen Algorithmus zu schreiben.

Answer 5

Wikipedia Artikel auf Integer Quadratwurzeln hat, kann Algorithmen sein angepasst an Ihre Bedürfnisse anzupassen. Newton-Verfahren ist schön, weil es quadratisch konvergiert, das heißt, Sie jeden Schritt doppelt so viele korrekten Ziffern erhalten.

Ich würde Ihnen raten, von Double zu bleiben weg, wenn der Eingang größer als 2^53 sein könnte, nach denen nicht alle Zahlen genau wie Double dargestellt werden.

Answer 6

Manchmal sollten Sie keine Probleme in zu kleine Teile teilen (wie Schecks 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

Es gibt eine sehr einfache Art und Weise zu Test für einen perfekten Platz - ganz wörtlich, Sie überprüfen, ob die Quadratwurzel der Zahl etwas anderes als Null in dem Bruchteil davon hat
. Ich gehe davon aus einer Quadratwurzelfunktion, dass die Renditen eine Gleitkomma, in dem Fall, dass Sie tun können (Psuedocode):

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

Answer 8

In einem Kommentar zu einer anderen Antwort auf diese Frage diskutiert memoization . Beachten Sie, dass diese Technik hilft, wenn Ihre Sonde Muster gute Dichte aufweisen. In diesem Fall bedeutet, dass würde die gleichen ganzen Zahlen immer und immer wieder zu testen. Wie wahrscheinlich ist Ihr Code die gleiche Arbeit zu wiederholen und damit profitieren Antworten Cachen?

Sie hat uns nicht eine Vorstellung von der Verteilung Ihrer Eingaben, so eine schnelle Benchmark berücksichtigen, dass die ausgezeichnete verwendet Kriterium Paket:

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
              ]

Diese Arbeitsbelastung kann oder auch nicht eine faire repräsentativ sein, was man tut, sondern wie geschrieben, wird die Cache-Miss-Rate zu hoch:

Answer 9

Es ist nicht besonders schön oder schnell, aber hier ist eine gegossenes frei, FPA-freie Version basierend auf dem Newton-Verfahren, das funktioniert (langsam) für beliebig große Zahlen:

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

Es könnte wahrscheinlich mit einiger zusätzlichen Zahlentheorie Betrügerei beschleunigt werden.