radice cubica affidabile in Haskell

Question

domanda 62 a Project Euler e si avvicinò con la seguito per verificare se un numero è cubica:

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

Ma a causa di floating errore del punto, restituisce risultati errati:

*Main> isCube (384^3)
False

C'è un modo per implementare un test 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

Le eventuali ottimizzazioni sono anche benvenuti; -)

Answer 1

Cercate di evitare l'uso di numeri in virgola mobile, per quanto possibile, soprattutto quando si ha un problema che riguarda valori interi. numeri in virgola mobile hanno problemi di arrotondamento e che certi valori (come 1/3) non possono essere rappresentati esattamente. Quindi non è una sorpresa che si ottiene risposte misteriose.

Prima di tutto, al fine di correggere il vostro errore tipo è necessario ridefinire isCube. Se si controlla il suo tipo di firma che appare così:

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

Si noti che si aspetta qualcosa che è di classe Floating come primo argomento. Il tuo problema è che si desidera utilizzare questa funzione sui valori interi e interi non sono un caso di Floating. È possibile ridefinire isCube come questo per rendere il controllo di tipo di funzione.

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

Tuttavia, che non renderà il vostro programma corretto.

Un modo per rendere il vostro programma più corretto è quello di fare ciò che Henrik suggerito. Si sarebbe simile a questa:

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

In bocca al lupo!

Answer 2

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

Answer 3

Per un altro approccio utile per i valori Integer uno sguardo alla funzione integerCubeRoot nel pacchetto Arithmoi .

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

Answer 4

perms ha il tipo [Integer]. isCube ha il tipo (RealFrac a, Floating a) => a -> Bool (come si può verificare in GHCI). Il vincolo RealFrac viene dal round x, il vincolo Floating viene da x**(1/3). Dal momento che non è né Integer RealFrac né Floating, isCube non può essere usato come Integer -> Bool. Quindi filter isCube (perms n) non ha senso.

Quindi, è necessario fissare isCube per funzionare correttamente su Integers:

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

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

Naturalmente, questo continua a funzionare male a causa di errori di virgola mobile. In sostanza, il controllo dei numeri galleggiante per l'uguaglianza, come si fa in isInt, è quasi sempre una cattiva idea. Vedi altre risposte per spiegare come fare un test migliore.