affidabile radice cubica in Haskell

Question

sto facendo question 62 a Project Euler e si avvicinò con la seguente per verificare se un numero è cubica:

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

Ma a causa di un errore in virgola mobile, restituisce risultati non corretti:

*Main> isCube (384^3) 
False 

C'è un modo per implementare un test del cubo più affidabile?

Su un lato nota, qui è il resto della mia soluzione, che non funziona a causa di un errore di interfaccia di tipo on 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] 

Che cosa devo fare per correggere l'errore?

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

eventuali ottimizzazioni sono i benvenuti ;-)

Answer 1

Cercare di evitare l'uso di numeri in virgola mobile il più possibile, soprattutto quando si presenta un problema che riguarda i valori integer. I numeri in virgola mobile hanno problemi con l'arrotondamento e alcuni valori (come 1/3) non possono essere rappresentati esattamente. Quindi non sorprende che tu abbia risposte misteriose.

Prima di tutto, per correggere il tuo errore di tipo devi ridefinire isCube. Se si controlla il suo tipo di firma che appare così:

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

Nota che si aspetta qualcosa che è di classe Floating come primo argomento. Il tuo problema è che vuoi usare questa funzione su valori interi e numeri interi non sono un'istanza di Floating. È possibile ridefinire lo isCube in questo modo per rendere il controllo del tipo di funzione.

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

Tuttavia, ciò non renderà corretto il programma.

Un modo per rendere più corretto il programma è fare ciò che Henrik ha suggerito. Sarebbe come questo:

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

Buona fortuna!

Answer 2

Non so molto di Haskell, ma vorrei prendere la radice cubica, intorno al numero intero nearerst, prendere il cubo, e confrontare con l'originale valore.

Answer 3

perms ha il tipo [Integer]. isCube ha il tipo (RealFrac a, Floating a) => a -> Bool (come è possibile controllare in GHCI). Il vincolo RealFrac proviene da round x, il vincolo Floating deriva da x**(1/3). Poiché Integer non è né RealFrac né Floating, isCubenon è possibile utilizzare come Integer -> Bool. Quindi, filter isCube (perms n) non ha senso.

Quindi è necessario per risolvere isCube per funzionare correttamente su Integer s:

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

In effetti, la ragione isCube (384^3) compila anche è che "realmente" significa isCube ((fromInteger 384)^(fromInteger 3)).

Ovviamente, questo funzionerà ancora male a causa di errori in virgola mobile. Fondamentalmente, controllare i numeri fluttuanti per l'uguaglianza, come si fa in isInt, è quasi sempre una cattiva idea. Vedi altre risposte per spiegazioni su come fare un test migliore.

Answer 4

Per un altro approccio utile per i valori Integer dare un'occhiata alla funzione integerCubeRoot nello arithmoi package.

Esempio:

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