mastershim   1년 전

간단한 이분탐색 문제라고 생각하고 푸는데 이상하게 34%에서 시간초과가 나와서.. 

결국 루프를 일정 횟수 이상으로 하면 끊어내는 코드를 넣어줬더니 AC가 나왔네요.

https://www.acmicpc.net/board/...

이 글을 보긴 했지만, mid 값이 계속 줄어든다고 생각했는데 10**-9 부터는 안되는건가요?

lcr7324   1년 전

N = 1000, L = W = H = 1000000000 인 입력을 넣고, 10번 줄과 11번 줄 사이에 print(s, m, e) 문을 넣어 이분탐색 과정에서 s, m, e가 각각 어떻게 변화하는지 확인해보면, 놀랍게도 s = 100000000.0, m = 100000000.0, e = 100000000.00000001 에서 더 이상 변화하지 않는 것을 알 수 있습니다.

m = (s + e) / 2가 실행되면 m이 100000000.000000005 등으로 점점 줄어야 할 것 같은데 왜 이런 일이 발생할까요?

파이썬을 포함한 상당수의 프로그래밍 언어에서 실수를 처리할 때 IEEE 754 (IEEE 부동소수점 연산 표준)를 따르기 때문입니다.

6.02 x 10^23 처럼 표현하는 과학적 표기법과 유사한 방식으로, 파이썬은 64비트로 실수를 표현하기 위해 부호에 1비트, 지수부에 11비트, 유효숫자 정밀도를 위한 가수부에 52비트를 사용합니다.

구체적으로 이 값들이 내부적으로 어떻게 저장되고 있는지 찾아봅시다.

https://stackoverflow.com/ques...

위 스택오버플로우 질문과 답변을 참고하여, 원 질문의 코드에 파이썬에서 float 형 값을 64비트 binary 형식으로 변환하여 출력하는 코드를 추가하였습니다.

N = 1000, L = W = H = 1000000000일 때 어느 시점 이후부터 아래의 출력이 반복되는 것을 확인할 수 있습니다.

-----
0100000110010111110101111000010000000000000000000000000000000000
0100000110010111110101111000010000000000000000000000000000000000
0100000110010111110101111000010000000000000000000000000000000001

s의 비트 표현을 뜯어봅시다.

0100000110010111110101111000010000000000000000000000000000000000은 다음과 같이 풀어 쓸 수 있습니다.

부호 비트: 0 / 지수부: 10000011001 / 가수부: 0111110101111000010000000000000000000000000000000000

부호 비트가 0이므로 이 수는 양수이며, 지수부는 1049인데 IEEE 754에서는 이 값에 1023을 빼서 해석해야 합니다. 즉 실제 지수 값은 26입니다.

가수부는 1.xxx... 부분에서 xxx 부분을 나타냅니다. 즉 s를 다시 쓰면 아래와 같습니다.

s = +1.0111110101111000010000000000000000000000000000000000 x 2^26

소수점을 오른쪽으로 26자리 이동시켜보면 101111101011110000100000000.00000000000000000000000000에 해당하고, 이 값을 10진수로 해석해보면 정확히 100,000,000 입니다. 잘 계산한 것 같군요.

이제 e를 살펴봅시다. e는 s와 부호 비트와 지수부가 동일하며, 가수부의 비트 표현이 정확히 1 늘어났습니다. 즉 e는 아래와 같습니다.

e = +1.0111110101111000010000000000000000000000000000000001 x 2^26

눈치 채셨겠지만, 이 표현 방식 상에서 s보다 크고 e보다 작은 실수를 표현할 방식이 없습니다. 왜냐하면 과학적 표기법을 이진법에서 그대로 모사한 IEEE 754 표현 방식의 특성 상, 유효숫자 범위보다 작은 변화는 표현할 수 없기 때문입니다.

e는 s와 가수부의 52번째 비트만이 다른데, 현재 지수가 26이므로 s와 e의 차이는 2^(26-52) = 2^-26 = 0.00000001490116119384765625 입니다.

즉, print(e) 와 같은 식으로 출력할 때 출력되는 값은 100000000.00000001 이지만, 파이썬이 저장하고 있는 실제 e의 정확한 값은 100000000.00000001490116119384765625인 것입니다. print 함수가 내부적으로 잘라서 출력해주고 있는 것입니다.

마지막으로 m = (s + e) / 2로 계산해주고 있는데, 아까 언급했다시피 s와 e 사이에 있는 값을 표현할 방법이 없습니다. 어쩔 수 없이 m의 값은 s와 e 중 하나를 택해야 하는데, round to even 규칙에 따라 가장 낮은 유효 숫자가 짝수인 s를 택하게 됩니다.

s와 e의 차이는 약 1.5 * 10^-8 정도이기 때문에 코드에서 택한 10^-9를 넘고, loop 횟수에 따라 탈출하는 코드가 없다면 이 코드는 무한 루프에 빠지게 됩니다.

많은 문제에서 스페셜 저지로 오차 범위를 나타낼 때 절대/상대 오차 중 어느 하나만이라도 특정 값보다 작으면 허용하는 경우가 많은데, 이 문제 또한 상대 오차를 이용하여 해결할 수 있습니다. 절대 오차만을 검사한다면 실수 표현 방식의 한계 때문에 이런 입력에서 10^-9 이하의 절대 오차를 만들 방법이 전무하지만, 상대 오차를 계산해보면 10^-9보다 이미 충분히 작은 상황입니다.

mastershim   1년 전

정성스러운 답변 감사합니다! IEEE 754 실수 오차에 대해 이렇게 당해보니까 더 신기한 거 같습니다. 

oh040411   1년 전

윗 분이 답변한 실수 오차 이슈를 피하는 방법으로, while 대신 for _ in range(100): 를 사용하면 간단합니다. 실수 범위 이분탐색 문제를 풀 때 많은 분들이 사용하는 방법입니다.

댓글을 작성하려면 로그인해야 합니다.