Haskell의 신뢰할 수있는 큐브 루트

Question

내가 뭐하는 거지 질문 62 Project Euler에서 숫자가 입방인지 테스트하기 위해 다음을 생각해 냈습니다.

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

그러나 부동 소수점 오류로 인해 잘못된 결과를 반환합니다.

*Main> isCube (384^3)
False

보다 안정적인 큐브 테스트를 구현할 수있는 방법이 있습니까?

사이드 코트에는 다음은 내 솔루션의 나머지 부분이 있습니다. 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]

오류를 수정하려면 어떻게해야합니까?

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

모든 최적화도 환영합니다 ;-)

Answer 1

특히 정수 값과 관련된 문제가있을 때 플로팅 포인트 번호를 최대한 사용하지 마십시오. 부동 소수점 번호는 반올림에 문제가 있으며 특정 값 (예 : 1/3)은 정확히 표현할 수 없습니다. 따라서 신비한 대답을 얻는 것은 놀라운 일이 아닙니다.

우선, 유형 오류를 수정하려면 재정의해야합니다. isCube. 유형 서명인지 확인하면 다음과 같습니다.

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

수업에 대한 것을 기대합니다 Floating 첫 번째 논쟁으로. 문제는 정수 값 에서이 함수를 사용하고 정수가 인스턴스가 아니라는 것입니다. Floating. 당신은 재정의 할 수 있습니다 isCube 이와 같이 함수 유형을 확인합니다.

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

그러나 프로그램이 정확하지는 않습니다.

프로그램을보다 올바르게 만드는 한 가지 방법은 Henrik이 제안한 일을하는 것입니다. 다음과 같습니다.

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

행운을 빕니다!

Answer 2

Haskell에 대해 많이 알지 못하지만 큐브 뿌리를 가져 가서 Nearerst Integer로 돌아와서 큐브를 가져 가서 원래 값과 비교할 것입니다.

Answer 3

유용한 또 다른 접근법 Integer 값은 integerCubeRoot 기능 Arithmoi 패키지.

예시:

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 유형이 있습니다 [Integer]. isCube 유형이 있습니다 (RealFrac a, Floating a) => a -> Bool (GHCI를 확인할 수 있듯이). 그만큼 RealFrac 제약은에서 나옵니다 round x,, Floating 제약은에서 나옵니다 x**(1/3). 부터 Integer 아니에요 RealFrac ...도 아니다 Floating, isCube 캔트 사용하십시오 Integer -> Bool. 그래서 filter isCube (perms n) 말이되지 않습니다.

그래서 당신은 해결해야합니다 isCube 제대로 작동합니다 Integer에스:

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

사실, 이유 isCube (384^3) 컴파일조차도 "정말로"의미한다는 것입니다 isCube ((fromInteger 384)^(fromInteger 3)).

물론 이것은 부동 소수점 오류로 인해 여전히 잘못 작동합니다. 기본적으로, 당신이하는 것처럼 평등에 대한 플로팅 숫자를 확인합니다. isInt, 거의 항상 나쁜 생각입니다. 더 나은 테스트를하는 방법에 대한 설명은 다른 답변을 참조하십시오.