Zuverlässige Kubikwurzel in Haskell

Question

ich question 62 bei Project Euler tue und kam mit dem folgenden Test auf, ob eine Zahl kubisch ist:

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

Aber aufgrund Gleitkommafehler, es falsche Ergebnisse zurückgibt:

*Main> isCube (384^3) 
False 

Gibt es eine Möglichkeit, einen zuverlässigeren Cube-Test zu implementieren?

An einer Nebennote, hier ist der Rest meiner Lösung, die nicht wegen eines Typ-Schnittstellenfehler 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 brauche ich, um den Fehler zu beheben, zu tun?

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

Alle Optimierungen sind auch willkommen ;-)

Answer 1

Versuchen Sie, die Verwendung von Fließkommazahlen so weit wie möglich zu vermeiden, insbesondere wenn Sie ein Problem haben, das ganzzahlige Werte betrifft. Fließkommazahlen haben Probleme beim Runden und bestimmte Werte (zB 1/3) können nicht exakt dargestellt werden. Es ist also keine Überraschung, dass Sie mysteriöse Antworten bekommen.

Zuerst müssen Sie isCube neu definieren, um Ihren Typfehler zu beheben. Wenn Sie überprüfen, ist es Unterschrift geben Sie es wie folgt aussieht:

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

Beachten Sie, dass es etwas erwartet, dass Floating als erstes Argument der Klasse ist. Ihr Problem besteht darin, dass Sie diese Funktion für ganzzahlige Werte verwenden möchten, und Ganzzahlen sind keine Instanz von Floating. Sie können isCube wie folgt neu definieren, um die Funktionstypüberprüfung durchzuführen.

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

Das wird jedoch Ihr Programm nicht korrekt machen.

Ein Weg, um Ihr Programm richtiger zu machen, ist zu tun, was Henrik vorgeschlagen hat. Es würde so 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 nehmen, nehmen Sie die Würfel, und mit dem Original vergleichen Wert.

Answer 3

perms hat den Typ [Integer]. isCube hat den Typ (RealFrac a, Floating a) => a -> Bool (wie Sie in GHCI einchecken können). Die RealFrac-Randbedingung kommt von round x, die Floating-Randbedingung kommt von x**(1/3). Da Integer ist weder RealFrac noch Floating, isCubekann nicht verwendet werden als Integer -> Bool. So macht filter isCube (perms n) keinen Sinn.

So müssen Sie isCube beheben richtig auf Integer s zu arbeiten:

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

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

Natürlich wird dies weiterhin aufgrund von Gleitkommafehlern schlecht funktionieren. Grundsätzlich ist es fast immer eine schlechte Idee, Floating-Zahlen für Gleichheit zu prüfen, wie Sie es in isInt tun. Sehen Sie sich die anderen Antworten an, um zu erklären, wie Sie einen besseren Test durchführen können.

Answer 4

Für einen anderen Ansatz nützlich für Integer Werte sehen Sie sich die integerCubeRoot Funktion in der arithmoi package.

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