raíz cúbica fiable en Haskell

Question

pregunta 62 al proyecto Euler y se acercó con la siguiente para probar si un número es cúbico:

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

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

*Main> isCube (384^3)
False

¿Hay una manera de poner en práctica una prueba de cubo más fiable?

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 punto flotante, tanto como sea posible, especialmente cuando se tiene un problema que afecta a valores enteros. números de punto flotante tienen problemas con el redondeo y que ciertos valores (como 1/3) no se pueden representar con exactitud. Por lo tanto, no es sorprendente que se obtiene misteriosos respuestas.

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

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

Tenga en cuenta que se espera que algo que es de Floating clase como su primer argumento. Su problema es que desea utilizar esta función en valores enteros y enteros no son una instancia de Floating. Puede volver a definir isCube como este para hacer el registro de entrada de tipo de función.

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

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

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

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

Buena suerte!

Answer 2

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

Answer 3

Por otro enfoque útil para los valores Integer echar un vistazo a la función integerCubeRoot en el paquete Arithmoi .

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

Answer 4

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

Así que hay que corregir isCube para trabajar correctamente en Integers:

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 punto flotante. Básicamente, comprobando los números flotando por la igualdad, como lo hace en isInt, es casi siempre una mala idea. Ver otras respuestas para explicar cómo hacer una mejor prueba.