복잡한 Double
다른 언어: English Español Português 中文
이것을 이미 알고 있을 것입니다:
double 데이터 타입은 매우 정확하지 않다.
이 개념을 CodeWars의 문제를 해결함으로써 더 깊게 이해해 봅시다.
문제 정의
CodeWars에 설명된 과제는 다음과 같습니다:
당신의 과제는 n개의 큐브로 건물을 건설하는 것입니다. 맨 아래의 큐브의 부피는 n^3이 되고, 그 위의 큐브는 (n-1)^3의 부피를 가지며, 그리고 맨 위의 큐브는 1^3의 부피를 가질 것입니다.
당신에게 건물의 총 부피 m이 주어집니다. m이 주어진 상태에서, 당신은 얼마나 많은 n개의 큐브가 필요한지 구할 수 있을까요?
함수 findNb의 매개변수는 정수 m이 될 것이며,
만약 n^3 + (n-1)^3 + … + 1^3 = m과 같은 n이 존재한다면 n을 반환하아고, 없다면 -1을 반환해야 합니다.
단순한 해결법
가장 직접적인 가장 간단한 반복문을 이용한 해결책은 다음과 같을 수 있습니다:
public static long findNb(long m) {
long n = 0, totalVolume = 0;
while (totalVolume < m) {
totalVolume += ++n * n * n;
}
return totalVolume == m ? n : -1;
}수학적인 해결법
대학에서, 나는 수학적인 수열과 그들의 합을 계산하는 방법에 대해 배웠기에, 이는 내가 수학적인 해결법을 생각해낸 것입니다.
수식은 이제 기억나지 않지만, 다행히도 Wolfram Alpha가 도와주게 있습니다. 수식을 구하기 위해, 다음 쿼리를 실행해봅시다: n^3, n = 1 to k.
결과에서 우리는 아래와 같은 수식을 얻을 수 있습니다:
위 수식의 왼쪽에 m을 대입하고 제곱근 공식을 적용하고
모든 항을 2로 곱합니다.
그래서 정리하면 다음과 같이 됩니다:
코드 작성하기
위의 방정식의 해결을 자바로 구현하면 다음과 같습니다:
public static long findNb(long m) {
double res = Math.sqrt(m);
double d = 1 + 8 * res;
double n = (Math.sqrt(d) - 1) / 2;
return n - Math.floor(n) == 0 ? (long) n : -1;
}결과
이 코드는 특정 테스트 데이터의 부분 집합에 대해 잘못된 결과를 반환하는 것으로 밝혀졌습니다.
이 부일관성은 예를 들어,
1646842954019151682L 을 입력으로 전달할 때 보입니다.
자바에서 제곱근을 계산하면 완전히 정확한 결과를 얻지 못할 수 있습니다. 한 번 살펴보겠습니다:
System.out.println(String.format("%.30f", Math.sqrt(1646842954019151682L)));
// output 1283293791.000000000000000000000000000000
// correct 1283293791.00000000038962239473657673134031176401122912...명백하게, 출력과 올바른 답은 다릅니다. 끝!
결론
기술적으로 가장 정확하고 가장 빠른 해결책이 항상 최선의 선택이 아닐 수 있습니다. 이것은 숙련된 개발자들에게는 놀랍지 않지만, 프로그래밍에 처음 익숙해지는 사람들은 오류의 원인을 찾는 데 상당히 오랜 시간이 걸릴 수 있습니다.
만약 수학적인 해결법에 문제가 있는 이유를 알고 싶다면, 한가지 접근법은
BigDecimal 를 사용하는 것입니다. 이 코드는 모든 테스트를 통과합니다:
public static long findNb(long m) {
MathContext mc = new MathContext(64);
BigDecimal res = BigDecimal.valueOf(m).sqrt(mc);
BigDecimal d = res.multiply(BigDecimal.valueOf(8)).add(BigDecimal.ONE);
BigDecimal n = d.sqrt(mc).subtract(BigDecimal.ONE).divide(BigDecimal.valueOf(2));
return Objects.equals(n, n.setScale(0, RoundingMode.FLOOR)) ? n.longValue() : -1;
}… 그리고 조금의 보너스: 다음 중 어느 것이 true , 어느 것이 false 일까요?
(1646842954019151681L == 1646842954019151682D)(1646842954019151681L == (long) 1646842954019151682D)
