Zuverlässige Kubikwurzel in Haskell

Question

Ich tue Frage 62 bei Project Euler und kam mit der folgende zu testen, ob eine Zahl cubic:

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

Aber aufgrund Punktfehler schwimmen, es gibt falsche Ergebnisse:

*Main> isCube (384^3)
False

Gibt es eine Möglichkeit, einen zuverlässigere Würfel Test zu implementieren?

Auf einer Seite zur Kenntnis, hier ist der Rest meiner Lösung, die nicht wegen eines Typ-Schnittstellenfehlers auf filter (isCube) (perms n) funktioniert:

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

Was muss ich tun, um den Fehler zu beheben?

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

Jede Optimierungen sind ebenfalls willkommen; -)

Answer 1

Versuchen Sie Gleitkommazahlen so weit wie möglich zu vermeiden, mit, vor allem, wenn Sie ein Problem haben, die ganzzahlige Werte betrifft. Gleitkommazahlen hat Probleme mit der Abrundung und dass bestimmte Werte (wie 1/3) nicht exakt dargestellt werden. So ist es keine Überraschung, dass Sie geheimnisvolle Antworten bekommen.

Zunächst einmal, um Ihre Art Fehler zu beheben haben Sie isCube neu zu definieren. Wenn Sie überprüfen, ist es Unterschrift geben Sie sieht es wie folgt aus:

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

Beachten Sie, dass es etwas erwartet, dass die Klassen Floating als erstes Argument ist. Ihr Problem ist, dass Sie diese Funktion auf ganzzahlige Werte verwenden möchten, und ganze Zahlen sind keine Instanz von Floating. Sie können isCube wie folgt neu zu definieren, um die Funktion Typprüfung zu machen.

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

Doch das wird nicht Ihr Programm richtig machen.

Eine Möglichkeit, Ihr Programm richtig zu machen, ist zu tun, was Henrik vorgeschlagen. Es würde wie folgt aussehen:

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

Viel Glück!

Answer 2

Sie wissen nicht viel über Haskell, aber ich würde die Kubikwurzel, rund um die nearerst ganze Zahl ist, nehmen Sie die Würfel nehmen und auf den ursprünglichen Wert vergleichen.

Answer 3

Für einen anderen Ansatz nützlich für Integer Werte haben einen Blick auf die integerCubeRoot Funktion in der arithmoi Paket .

Beispiel:

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 hat den Typ [Integer]. isCube hat den Typ (RealFrac a, Floating a) => a -> Bool (wie Sie in GHCI überprüfen). Die RealFrac Einschränkung von round x kommt, dann kommt die Floating Einschränkung von x**(1/3). Da Integer weder RealFrac noch Floating ist, isCube nicht als Integer -> Bool verwendet werden. So filter isCube (perms n) macht keinen Sinn.

Sie müssen also isCube beheben richtig auf Integers zu arbeiten:

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

In der Tat, der Grund isCube (384^3) selbst kompiliert ist, dass es "wirklich" bedeutet isCube ((fromInteger 384)^(fromInteger 3)).

Natürlich wird dies immer noch schlecht funktionieren aufgrund Gleitkommafehler. Grundsätzlich Überprüfung Zahlen für die Gleichstellung schwimmen, wie Sie in isInt tun, ist fast immer eine schlechte Idee. Andere Antworten zur Erläuterung, wie man einen besseren Test machen.