¿Cuál es la manera de determinar si un Int es un cuadrado perfecto en Haskell?

StackOverflow https://stackoverflow.com/questions/2807686

  •  25-09-2019
  •  | 
  •  

Pregunta

necesito una función simple 

is_square :: Int -> Bool

que determina si un Int N un cuadrado perfecto (¿hay un número entero x tal que x * x = N).

Por supuesto que es posible que algo acaba de escribir como 

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

pero se ve terrible! Tal vez hay una manera sencilla común para poner en práctica tal predicado?

¿Fue útil?

Solución 5

Oh, hoy en día lo que necesitaba para determinar si un número es cubo perfecto, y la solución similar fue muy lento.

Por lo tanto, se me ocurrió una alternativa muy inteligente 

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

Muy simple. Creo, que necesito utilizar un árbol para búsquedas más rápidas, pero ahora voy a intentar esta solución, tal vez va a ser lo suficientemente rápido para mi tarea. Si no es así, voy a editar la respuesta correcta con la estructura de datos

Otros consejos

Piénsalo de esta manera, si usted tiene un n int positivo, entonces básicamente está haciendo una búsqueda binaria en el rango de números del 1 .. N para encontrar el primer número donde n' n' * n' = n.

No sé Haskell, pero esto F # debe ser fácil de 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

Garantizado para ser O (log n). Fácil de modificar cubos perfectos y poderes superiores.

Hay un maravillosa Biblioteca para la mayoría de los problemas relacionados con la teoría de números en Haskell incluidos en el arithmoi paquete .

Utilice el Math.NumberTheory.Powers.Squares biblioteca .

Específicamente, la isSquare' función . 

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

La biblioteca está optimizado y bien examinada por la gente mucho más dedicado a la eficiencia, entonces o I. Si bien en la actualidad no tiene este tipo de chanchullos pasando bajo el capó, que podría en el futuro a medida que evoluciona biblioteca y se hace más optimizado. Ver la fuente código para entender cómo funciona!

No reinventar la rueda, utilice siempre una biblioteca cuando esté disponible.

Creo que el código que ya ha proporcionado es el más rápido que se van a poner: 

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

La complejidad de este código es: una raíz cuadrada, una multiplicación doble, un molde (dbl-> int), y una comparación. Se podría intentar utilizar otros métodos de cálculo para reemplazar la raíz cuadrada y la multiplicación con sólo aritmética de enteros y los cambios, pero lo más probable es que no va a ser más rápido que una raíz cuadrada y una multiplicación.

El único lugar donde podría ser digno de usar otro método es que si la CPU en el que está ejecutando no soporta la aritmética de coma flotante. En este caso, el compilador probablemente tendrá que generar sqrt y multiplicación doble en el software, y se podía obtener ventaja en la optimización para su aplicación específica.

Como se ha señalado por otra respuesta, todavía hay una limitación de enteros grandes, pero a menos que se va a ejecutar en esos números, es probablemente mejor para aprovechar el soporte de hardware de punto flotante que escribir su propio algoritmo.

de Wikipedia sobre raíces cuadradas de enteros tiene algoritmos pueden ser adaptado a sus necesidades. El método de Newton es agradable porque converge cuadráticamente, es decir, se obtiene el doble de dígitos correctos cada paso.

Le aconsejo que se mantenga alejado de Double si la entrada podría ser más grande que 2^53, después de lo cual no todos los números enteros se pueden representar exactamente como Double.

A veces uno no debe dividir los problemas en partes demasiado pequeña (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

Hay una manera muy simple de prueba para un cuadrado perfecto - literalmente, que compruebe si la raíz cuadrada del número tiene nada que no sea cero en la parte fraccionaria de la misma
. Estoy asumiendo una función de raíz cuadrada que devuelve un punto flotante, en cuyo caso se puede hacer (psuedocode): 

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

En un comentario en otra respuesta a esta pregunta, se discutió memoization . Tenga en cuenta que esta técnica ayuda cuando sus patrones de sondas presentan una buena densidad. En este caso, eso significaría probar los mismos números enteros y otra vez. ¿Qué tan probable es que su código para repetir el mismo trabajo y por lo tanto beneficiarse de almacenamiento en caché de respuestas?

No nos dan una idea de la distribución de sus entradas, por lo que considera un punto de referencia rápida que utiliza el excelente criterio paquete: 

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
              ]

Esta carga de trabajo puede o no ser una feria representativa de lo que está haciendo, pero como está escrita, la tasa de error de caché parece demasiado alto:

tiempo de densidad de probabilidad

No es especialmente bonita o rápido, pero aquí es una versión FPA-libre Sin fundido basado en el método de Newton que las obras (lentamente) para arbitrariamente grandes números enteros: 

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

Se podría probablemente ser acelerado con algún truco adicional de la teoría de números.

Licenciado bajo: CC-BY-SA con atribución
No afiliado a StackOverflow
scroll top