necesito una función simple¿Cuál es la forma de determinar si un Int es un cuadrado perfecto en Haskell?
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 sólo puede escribir algo como
is_square n = sq * sq == n
where sq = floor $ sqrt $ (fromIntegral n::Double)
pero parece terrible! Tal vez hay una forma simple común de implementar dicho predicado?
Oh, hoy necesitaba determinar si un número es el cubo perfecto, y una solución similar era MUY lenta.
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 usar un árbol para realizar búsquedas más rápidas, pero ahora intentaré con esta solución, tal vez sea lo suficientemente rápida para mi tarea.Si no es así, voy a editar la respuesta con estructura de datos adecuada
No sé si esto será más rápido que el original. Requiere muchas más instrucciones para ser ejecutado. Puede ser más rápido dependiendo de cómo Haskell hace 'head' /' dropWhile' y qué tan grandes son tus números. – earlNameless
Es más rápido en la práctica. –
Usar una estructura de datos diferente ('Seq',' Vector') y una búsqueda binaria probablemente será un orden de magintude más rápido –
Wikipedia article on Integer Square Roots tiene algoritmos que se pueden adaptar a sus necesidades. El método de Newton es agradable porque converge cuadráticamente, es decir, obtienes el doble de dígitos correctos en cada paso.
Le aconsejo que se mantenga alejado de Double si la entrada puede ser mayor que 2^53, después de lo cual no todos los números enteros se pueden representar exactamente como Double.
No necesito un algoritmo muy complejo, solo pensé que había una solución simple y hermosa sin dos conversiones de tipo :) –
@valya: Escribir una función 'isqrt' eliminaría las conversiones de tipo. –
creo que el código que ya ha proporcionado es el más rápido que se va a obtener:
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 Podría intentar usar otros métodos de cálculo para reemplazar el sqrt y la multiplicación con aritmética y cambios enteros, pero es probable que no vaya a ser más rápido que un sqrt y una multiplicación.
El único lugar donde podría valer la pena utilizar otro método es si la CPU en la que se está ejecutando no es compatible con la aritmética de coma flotante. En este caso, el compilador probablemente tendrá que generar sqrt y multiplicación doble en el software, y podría obtener ventajas en la optimización para su aplicación específica.
Como se señala en otra respuesta, todavía hay una limitación de enteros grandes, pero a menos que vaya a encontrar esos números, probablemente sea mejor aprovechar el soporte de hardware de punto flotante que escribir su propio algoritmo.
Solo pensé que hay una solución simple y hermosa sin dos conversiones de tipo :) Ok, gracias! –
perfilando mi aplicación muestra qué se usa el 57% del tiempo en la función is_square :( –
Es posible que tenga que hacer un poco de almacenamiento en caché (no calcule el mismo número entero dos veces), o calcular previamente todos los números enteros. bool [] isSquare = nuevos bool [100000]; for (int i = 1; i
No es especialmente bonita o rápido, pero aquí es una versión libre de fundido FPA-libre basado en el método de Newton que funciona (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
Probablemente podría ser acelerado con algún truco de teoría de números adicional.
¡Gracias! pero es lo opuesto a mi tarea –
A veces usted no debe dividir los problemas en partes más pequeñas también (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
¡oh, muy interesante! Pensaré en cómo hacer que esto sea más adecuado para mí –
Hay una manera muy simple para probar una perfecta cuadrado: literalmente, se comprueba si la raíz cuadrada del número tiene algo distinto de cero en la parte fraccionaria del mismo.
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
isSquare b n = (mod '(logBase b n) 1.0) == 0.0 - mod' de Data.Fixed – JayJay
En un comentario en otra respuesta a esta pregunta, se le explicara memoization . Tenga en cuenta que esta técnica ayuda cuando los patrones de su sonda exhiben buena densidad. En este caso, eso significaría probar los mismos enteros una y otra vez. ¿Cuán probable es que su código repita el mismo trabajo y, por lo tanto, se beneficie de las respuestas de almacenamiento en caché?
Usted no nos ha dado una idea de la distribución de sus entradas, por lo que considera un punto de referencia rápida que utiliza la excelente criterion 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 un representante de lo justo que está haciendo, pero como está escrita, la tasa de error de caché parece demasiado alto:
creo que de esta manera, si usted tiene un efecto positivo int n, a continuación, que está básicamente haces g una búsqueda binaria en el rango de números de 1 .. n para encontrar el primer número n' donde n' * n' = n.
no sé Haskell, pero esto F # debería 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
garantiza que sea O (log n). Fácil de modificar cubos perfectos y mayores poderes.
Me gusta mucho esta solución. Sigo sorprendiéndome de lo útil que es la búsqueda binaria para diferentes cosas. Sin embargo, O (log n) es engañoso. Preformas las iteraciones O (log n), sin embargo, en cada iteración tienes un mid * mid oculto. Cuadrar un número toma aproximadamente O (mlogm). m se acerca a sqrt (n), así que supongamos m = sqrt (n). La eficacia final de esto es en realidad O (log n) * O (m log m) para m = sqrt (n). Aún así, +1 para la búsqueda binaria: P – Rubys
La pregunta especifica 'Int' que en Haskell es de precisión fija (típicamente de 32 bits), por lo que preferiría el método de coma flotante tal como se usa en la pregunta. Si 'N' era un' Integer' (precisión arbitraria) usaría su método. – finnw
Existe una biblioteca maravillosa para la mayoría de los problemas relacionados con la teoría de números en Haskell incluidos en el paquete arithmoi.
Utilice la biblioteca Math.NumberTheory.Powers.Squares.
Específicamente la función isSquare'.
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 this kind of shenanigans pasando bajo el capó, que podría en el futuro a medida que evoluciona biblioteca y se optimiza más View the source code para entender cómo funciona!
No reinventar la rueda, siempre use una biblioteca cuando esté disponible.
Estoy escribiendo algo así como mi propia biblioteca de teoría de números para divertirme. Mi punto es entender cómo funcionan las funciones que tengo en él. El peor escenario para la función de esa biblioteca es: – Sean
posible duplicar de [La forma más rápida de determinar si la raíz cuadrada de un entero es un número entero] (http: // stackoverflow.com/questions/295579/fastest-way-to-determination-if-an-integers-square-root-is-an-integer) – finnw