raíz cúbica fiable en Haskell

Question

que estoy haciendo question 62 a Euler proyecto y se le ocurrió la siguiente para probar si un número es cúbica:

isInt x = x == fromInteger (round x) 
isCube x= isInt $ x**(1/3) 

Pero debido a un error de punto flotante, devuelve resultados incorrectos:

*Main> isCube (384^3) 
False 

¿Existe alguna manera de implementar una prueba de cubo más confiable?

En una nota lateral, aquí está el resto de mi solución, que no funciona debido a un error de interfaz tipo de filter (isCube) (perms n):

cubes = [n^3|n<-[1..]] 
perms n = map read $ permutations $ show n :: [Integer] 
answer = head [n|n<-cubes,(length $ filter (isCube) (perms n)) == 5] 

¿Qué necesito hacer para corregir el error?

No instances for (Floating Integer, RealFrac Integer) 
    arising from a use of `isCube' at prob62.hs:10:44-49 

Cualquier optimizaciones también son bienvenidos ;-)

Answer 1

Trate de evitar el uso de números de coma flotante tanto como sea posible, especialmente cuando tenga un problema relacionado con valores enteros. Los números de coma flotante tienen problemas con el redondeo y ciertos valores (como 1/3) no se pueden representar exactamente. Entonces no es sorprendente que obtengas respuestas misteriosas.

En primer lugar, para corregir su error de tipo, debe redefinir isCube. Si comprueba que es el tipo de firma que tiene este aspecto:

isCube :: (RealFrac a, Floating a) => a -> Bool 

Nota que espera algo que es de la clase Floating como primer argumento. Su problema es que desea utilizar esta función en valores enteros y los enteros no son una instancia de Floating. Puede redefinir isCube de esta manera para que el tipo de función funcione.

isCube x = isInt $ (fromIntegral x) ** (1/3) 

Sin embargo, eso no hará que su programa sea correcto.

Una forma de hacer que su programa sea más correcto es hacer lo que Henrik sugirió. Se vería así:

isCube x = (round (fromIntegral x ** (1/3)))^3 == x 

¡Buena suerte!

Answer 2

no sabe mucho acerca de Haskell, pero me gustaría tomar la raíz cúbica, redondo al entero nearerst, tomar el cubo, y compare con el original valor.

Answer 3

perms tiene el tipo [Integer]. isCube tiene el tipo (RealFrac a, Floating a) => a -> Bool (como se puede comprobar en GHCI). La restricción RealFrac proviene de round x, la restricción Floating proviene de x**(1/3). Como Integer no es RealFrac ni Floating, isCubeno se puede usarse como . Entonces filter isCube (perms n) no tiene sentido.

por lo que necesita para fijar isCube para trabajar correctamente en Integer s:

isCube x = isInt $ (fromInteger x)**(1/3) 

De hecho, la razón isCube (384^3) siquiera se recopilan es que "realmente" significa isCube ((fromInteger 384)^(fromInteger 3)).

Por supuesto, esto seguirá funcionando mal debido a los errores de coma flotante. Básicamente, verificar números flotantes para la igualdad, como lo hace en isInt, es casi siempre una mala idea. Vea otras respuestas para una explicación sobre cómo hacer una mejor prueba.

Answer 4

Para otro enfoque útil para los valores Integer, eche un vistazo a la función integerCubeRoot en el arithmoi package.

Ejemplo:

ghci> import Math.NumberTheory.Powers.Cube 
ghci> let x = 12345^3333 
ghci> length $ show x 
13637 
ghci> isCube x 
True 
ghci> isCube (x+1) 
False 
ghci> length $ show $ integerCubeRoot x 
4546