Qual è il modo per determinare se un int è un quadrato perfetto in Haskell?

Question

Ho bisogno di una semplice funzione

is_square :: Int -> Bool

che determina se un Int N un quadrato perfetto (c'è un numero intero x tale che x * x = N).

Certo che posso qualcosa solo scrivere come

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

ma sembra terribile! Forse c'è un modo semplice comune per attuare tale predicato?

Answer 1

Oh, oggi avevo bisogno di determinare se un numero è cubo perfetto, e la soluzione simile era molto lento.

Quindi, mi si avvicinò con una bella alternativa intelligente

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

Molto semplice. Penso, ho bisogno di usare un albero per le ricerche più veloci, ma ora cercherò questa soluzione, forse sarà abbastanza veloce per il mio compito. In caso contrario, Io modificare la risposta con una corretta datastructure

Answer 2

Pensare in questo modo, se si dispone di un int n positiva, allora si sta praticamente facendo una ricerca binaria sulla gamma di numeri da 1 .. n per trovare il primo numero n' dove n' * n' = n.

Non so Haskell, ma questo F # dovrebbe essere facile da convertire:

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

Garantito per essere O (log n). Facile da modificare cubi perfetti e potenze superiori.

Answer 3

C'è un meraviglioso libreria per la maggior parte dei problemi legati teoria dei numeri a Haskell inclusi nel arithmoi pacchetto .

Utilizza la Math.NumberTheory.Powers.Squares libreria .

In particolare il isSquare' la funzione .

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

La biblioteca è ottimizzato e ben controllati da persone molto più dedicato all'efficienza allora o I. Anche se al momento non ha questo tipo di imbrogli succedendo sotto il cofano, potrebbe in futuro come evolve biblioteca e viene più ottimizzato. Visualizza i sorgenti codice per capire come funziona!

Non reinventare la ruota, sempre utilizzare una libreria quando disponibile.

Answer 4

Credo che il codice che hai fornito è il più veloce che si sta per ottenere:

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

La complessità di questo codice è: uno sqrt, una doppia moltiplicazione, un getto (dbl-> int), ed un comparatore. Si potrebbe provare a utilizzare altri metodi di calcolo per sostituire lo sqrt e la moltiplicazione con un solo aritmetica intera e si sposta, ma è probabile che non sta per essere più veloce di uno sqrt ed una moltiplicazione.

L'unico posto dove potrebbe essere utile utilizzare un altro metodo è se la CPU su cui è in esecuzione non supporta aritmetica in virgola mobile. In questo caso il compilatore probabilmente per generare sqrt e doppia moltiplicazione in software, e si potrebbe ottenere vantaggio per ottimizzare per la vostra applicazione specifica.

Come sottolineato da altra risposta, c'è ancora una limitazione di grandi numeri interi, ma a meno che non si sta andando a correre in quei numeri, è probabilmente meglio per sfruttare il supporto punto di hardware di floating di scrivere il proprio algoritmo.

Answer 5

di Wikipedia su radici intere quadrati ha algoritmi possono essere adattata per soddisfare le vostre esigenze. il metodo di Newton è bello perché converge al quadrato, vale a dire, si ottiene il doppio delle cifre corrette ogni passo.

Vi consiglio di stare lontano da Double se l'ingresso potrebbe essere più grande di 2^53, dopo di che non tutti i numeri interi possono essere rappresentati come esattamente Double.

Answer 6

A volte non si deve dividere i problemi in troppo piccole parti (come assegni 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

C'è un modo molto semplice per test per un quadrato perfetto - letteralmente, è verificare se la radice quadrata del numero ha qualcosa di diverso da zero nella parte frazionaria di esso
. Sto assumendo una funzione di radice quadrata che restituisce una virgola mobile, nel qual caso si può fare (psuedocodarlo):

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

Answer 8

In un commento su un'altra risposta a questa domanda, è discusso Memoizzazione . Tenete a mente che questa tecnica aiuta quando i modelli di sonde presentano una buona densità. In questo caso, ciò significherebbe testare gli stessi numeri interi più e più volte. Come probabile è il codice per ripetere lo stesso lavoro e quindi beneficiare di caching risposte?

Non hai darci un'idea della distribuzione di ingressi, in modo da considerare un punto di riferimento rapido che usi l'eccellente criterio pacchetto:

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
              ]

Questo carico di lavoro può o non può essere un giusto rappresentativo di quello che stai facendo, ma come scritto, il tasso di cache miss appare troppo alta:

Answer 9

Non è particolarmente bella o veloce, ma ecco una versione priva di fusione FPA-libero basato sul metodo di Newton che le opere (lentamente) per arbitrariamente grandi numeri interi:

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

Si potrebbe probabilmente essere accelerato con qualche ulteriore inganno teoria dei numeri.