파이썬 백준 13705 Ax+Bsin(x)=C

import sys input = sys.stdin.readline from decimal import * getcontext().prec = 27 getcontext().rounding = ROUND_HALF_UP a, b, c = map(Decimal,map(int,input().split())) pi = Decimal('3.141592653589793238462643383') def sin(x) :      x = x % (2 * pi)     getcontext().prec += 2     i, lasts, s, fact, num, sign = 1, 0, x, 1, x, 1     while s != lasts:         lasts = s         i += 2         fact *= i * (i-1)         num *= x * x         sign *= -1         s += num / fact * sign     getcontext().prec -= 2     return +s # sinx = x^1/1! - x^3/3! + x^5/5! - ... lower = (c - b) / a upper = (c + b) / a while upper - lower > Decimal('0.000000000000000000001') :     center = (lower + upper) / 2     if a * center + b * sin(center) < c :          lower = center     else :          upper = center print(round(upper, 6))

Ax+Bsin(x)=C의 근사해를 소수점 6자리 반올림으로 구하라는 문제이다. 무려 다이아 문제
이항하면 Ax = - Bsinx + C 인데, sinx가 -1이상 1이하이므로 Ax는 C-B 이상 C+B 이하이다.
즉 근 x의 range는 (C-B)/A부터 (C+B)/A까지이다.
x의 range가 제한되었으니 이분탐색으로 점점 x의 범위를 줄여나간다.
줄여나가다 보면 OO.OOOOOOAB < x < OO.OOOOOOCD 이런 식으로 소수점 6자리까진 fix가 될 텐데,
그때의 여섯자리까지를 출력하면 될 것이다.

sin은 파이썬이 제공해준 것을 그대로 긁어왔는데, 삼각함수가 테일러 전개를 통해 다항식의 꼴로 표현이 가능함을 이용해서 while문으로 다항식의 합을 계산한 함수이다. 다항식의 다음 항이 소수점 계산 깊이 밑의 작은 수라면, s와 lasts가 소수 계산 깊이 이내에서 같은 값이 되니 while문이 종료되고 값을 리턴한다.
원하는 소수 깊이의 +2자리까지 계산한 뒤 끝 2자리를 자르니 원하는 깊이까지는 정확한 값이 나온다.

sinx가 소수 깊이 +2까지 계산한 뒤 끝 2자리를 자르는 것처럼
위에서 말한것처럼 소수점 6자리까지 출력해야 하니 8자리까지 이분탐색하고 7자리에서 반올림을 하면 된다고 믿었다.
근데 제출해보니 틀렸다.

사람이었다면 이게 맞는데 컴퓨터가 소수도 2진수로 계산을 해서 그로인한 오차가 있다고 한다.
예를들어 출력값은 1.XXXXX49이지만 이게 컴퓨터에 저장된 값을 10진수로 표현했을때 이럴 뿐 실제 2진수의 값은 1.XXXXX50일 수가 있다. 이런 경우 반올림값이 실제와 달라지고, 틀린 값을 출력하게 된다.

결국 6자리까지 출력하더라도 소수점 계산은 저 2진계산의 오차가 무의미해질 만큼 깊게 해야 한다는 의미이다.
틀렸습니다가 안나올때까지 소수 깊이, 원주율, while문 종료조건을 한자리씩 늘려갔다. 그냥 노가다...
결과적으로 range를 소수점 21자리까지 줄여야 모든 testcase에 대해 올바른 값이 나오고, -21자리 range를 정확히 계산하기 위한 계산 깊이는 27자리까지 내려갔다.

이건 문제니까 정답비교가 가능해서 그냥 될때까지 제출해가며 내려가면 되는데, 만약 정답이 없는 본인 연구같은데에서 이런 상황이 된다면 코드에 구현된 모든 사칙연산에 대해 오차의 확산 따져가면서 저 적정 깊이값을 구해야 하지 않을까.
아니면 그냥 컴퓨터 성능을 업그레이드해서 대충 엄청 큰 자리수 때려넣든가ㅋㅋ

그동안 알고리즘 풀면서 컴퓨터의 유능한 부분만 봐왔는데, 수치해석학 쪽으로 들어가니 컴퓨터가 사람보다 멍청해지는 것 같다...