Qual é a maneira de determinar se um int é um quadrado perfeito em Haskell?

Question

Eu preciso de uma função simples

is_square :: Int -> Bool

que determina se um quadrado perfeito (existe um número inteiro x tal que x*x = n).

Claro que posso apenas escrever algo como

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

Mas parece terrível! Talvez exista uma maneira simples de implementar esse predicado?

Answer 1

Ah, hoje eu precisava determinar se um número é um cubo perfeito e uma solução semelhante era muito lenta.

Então, eu criei uma alternativa bastante inteligente

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

Muito simples. Acho que preciso usar uma árvore para pesquisas mais rápidas, mas agora vou tentar esta solução, talvez seja rápido o suficiente para minha tarefa. Caso contrário, editarei a resposta com dados adequados

Answer 2

Pense dessa maneira, se você tem um INT positivo n, então você está basicamente fazendo uma pesquisa binária na faixa de números de 1 .. n para encontrar o primeiro número n' Onde n' * n' = n.

Não conheço Haskell, mas esse F# deve ser fácil de converter:

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

Garantido para ser O (log n). Fácil de modificar cubos perfeitos e poderes mais altos.

Answer 3

Existe um Maravilhoso Biblioteca para a maioria dos problemas relacionados à teoria dos números em Haskell incluído no arithmoi pacote.

Use o Math.NumberTheory.Powers.Squares biblioteca.

Especificamente o isSquare' função.

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

A biblioteca é otimizada e bem examinada por pessoas muito mais dedicadas à eficiência do que você ou eu. Embora atualmente não tenha Este tipo de travessuras Continuando sob o capô, poderia no futuro à medida que a biblioteca evolui e fica mais otimizada. Veja o código -fonte Para entender como funciona!

Não reinvente a roda, sempre use uma biblioteca quando disponível.

Answer 4

Eu acho que o código que você forneceu é o mais rápido que você vai obter:

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

A complexidade deste código é: um SQRT, uma multiplicação dupla, um elenco (dbl-> int) e uma comparação. Você pode tentar usar outros métodos de computação para substituir o SQRT e a multiplicação apenas com aritmética inteira e mudanças, mas é provável que não seja mais rápido que um SQRT e uma multiplicação.

O único lugar onde pode valer a pena usar outro método é se a CPU na qual você está em execução não suporta aritmética de ponto flutuante. Nesse caso, o compilador provavelmente terá que gerar SQRT e multiplicação dupla no software, e você poderá obter vantagem ao otimizar o seu aplicativo específico.

Como apontado por outra resposta, ainda há uma limitação de grandes números inteiros, mas, a menos que você encontre esses números, provavelmente é melhor aproveitar o suporte de hardware de ponto flutuante do que escrever seu próprio algoritmo.

Answer 5

Wikipedia Artigo sobre raízes quadradas inteiras possui algoritmos pode ser adaptado para atender às suas necessidades. O método de Newton é bom porque converge quadraticamente, ou seja, você recebe o dobro de dígitos corretos a cada etapa.

Eu aconselho você a ficar longe de Double Se a entrada puder ser maior do que 2^53, após o que nem todos os números inteiros podem ser exatamente representados como Double.

Answer 6

Às vezes você não deve dividir problemas em partes muito pequenas (como cheques 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

Há uma maneira muito simples de testar um quadrado perfeito - literalmente, você verifica se a raiz quadrada do número tem algo além de zero na parte fracionária dela.
Estou assumindo uma função raiz quadrada que retorna um ponto flutuante; nesse caso, você pode fazer (psuedocode):

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

Answer 8

Em um comentário sobre outra resposta a esta pergunta, você discutiu memórias. Lembre -se de que essa técnica ajuda quando seus padrões de sonda exibem boa densidade. Nesse caso, isso significaria testar os mesmos números inteiros repetidamente. Qual a probabilidade de seu código repetir o mesmo trabalho e, assim, se beneficiar das respostas do cache?

Você não nos deu uma idéia da distribuição de suas entradas, então considere uma referência rápida que usa o excelente critério pacote:

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
              ]

Essa carga de trabalho pode ou não ser um representante justo do que você está fazendo, mas, como escrito, a taxa de falta de cache parece muito alta:

Answer 9

Não é particularmente bonito ou rápido, mas aqui está uma versão sem elenco, sem elenco, baseada no método de Newton que funciona (lentamente) para números inteiros arbitrariamente grandes:

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

Provavelmente poderia ser acelerado com alguns truques da teoria de números adicionais.