백준 13705, Ax+Bsin(x)=C

개요

문제 링크
다이아 5, 임의정밀도/큰 수 연산
Ax+Bsin(x)=C를 만족하는 x를 임의 정밀도를 고려해 구하기

---

접근

1. 이분탐색을 사용하는 문제라고하면 두 가지 유형이 있는데, 하나는 실행 횟수를 줄이기 위한 문제이고 하나는 오차를 완벽히 구할 수 없는 문제이다. 이 문제는 후자에 속하는데, sin(x)의 오차가 문제가 원하는 수준의 오차보다 크게 발생한다.

2. 이분탐색이면 왼쪽과 오른쪽을 잘 설정해야 하는데, Ax=C로 가정하고 구해도 되지만, sin의 범위는 -1부터 1까지라서 다음의 부등식이 성립한다.

    -B <= C-Ax <= B
    -> (C-B)/A <= x <= (C+B)/A

   사실 0에서 1e5안에 있을거라 왼쪽 오른쪽을 [0,1e5]로 설정해도 상관은 없다.

3. 그럼 long double을 사용하고 이렇게만 해주면 되냐?

    while(l+e<r) {
        x = (l+r)/2;
        if (A*x+B*sin(x)-C<0) l=x;
        else r=x;
    }

   하면 73%쯤에서 끊긴다.

   1. 왜냐? sin이 long double이 아닌 double함수이기 때문이다. double이 먹히는 문제는 14786번이 있다.
   2. 그럼 long double을 사용하는 sinl을 사용하면 되냐? 하면 75%에서 끊긴다. 그래서 테일러 전개를 이용해 sin(x)를 직접 만들어야 한다.
   3. 그럼 찐막으로 sin도 만들고 이분탐색도 많이 쓰면 되냐? 그것도 안된다. 77%에서 끊긴다.
   4. __float128이라는 자료형을 이용해야 되는데, 아래 설명을 잠깐 읽어보자.

4. 부동소수점 문제는 각을 잡고 제대로 배워야겠지만, 우선 예시부터 보자.

    #include <iostream>
    using namespace std;
   
    using lf=long double;
    using LF=__float128;
   
    int main() {
        lf f=0.0000000000000000000000000000009L;
        LF F=0.0000000000000000000000000000009Q;
        LF U=10000000000000000000000000000000.0Q;
        printf("long double : %d\n",int(f*U));
        printf("__float128  : %d\n",int(F*U));
    }

   31자리 소수이다. 출력을 해보면 아래와 같이 다른 결과가 나온다. 이게 유효숫자 차이 때문인 건 다들 알고 있을 텐데, 어떻게 차이가 나는걸까?

    // long double : 8
    // __float128  : 9

   long double의 유효숫자는 15개, __float128의 유효숫자는 34개라고 한다. 왜 하필 15, 34이냐? 하면 이것저것 알아보다가 너무 길어질 것 같아 나중에 따로 다루어 보려고 한다.

5. 간단하게만 설명하면 각각 double precision, extended precision 방식을 이용해 자료형을 정의하기 때문이라는데,

   	long double	__float128
   부호	1	1
   지수	15	15
   가수	64	112
   전체	80	128

   2^-64가 10진수로 대략 15자리까지, 2^-112가 34자리까지 커버할 수 있다고 한다.

6. 이렇게 특이한 문제를 풀 때를 제외하고는 잘 사용하지 않는 개념이니 테일러 전개를 잘 알아두자. 테일러전개도 따로 다루어야겠지만, 비선형함수를 선형함수의 조합으로 표현할 수 있는 막강한 함수이다. sin은 아래와 같이 표현한다.

    sin(x) = sum((-1)^n * x^(2n+1) / (2n+1)!)
    = x-x^3/3!+x^5/5!-x^7/7!....

   이걸 for문을 이용해 30-100번 정도만 해줘도 충분히 30자리 소수점까지는 커버할 수 있다.

7. 문제 풀 때의 팁이라면 이분탐색은 정밀도를 가지고 하는 것보다 시행횟수를 정해놓고 해버리는게 더 낫다는 것이고, 22자리의 원주율만 사용해도 된다는 것이다.

---

Source code

#include <iostream>
using namespace std;

#define N 30
using LF=__float128;
using LD=__int128;
using lf=long double;
LF PI2=3.1415926535897932384626Q;

LF Sin(LF a) {
    a-=LD(a/PI2)*PI2;
    LF r=a,x=a,f=-a*a;
    for (LF d=2;d<N;d+=2)
        r+=x*=f/(d*(d+1));
    return r;
}

int main() {
    PI2*=2;
    lf a,b,c;
    cin>>a>>b>>c;
    LF A,B,C,l,r,x;
    A=a,B=b,C=c;

    LF U=1000000, D=0.5;
    l = (C-B)/A;
    r = (C+B)/A;
    int t=80;
    while(t--) {
        x = (l+r)/2;
        LF V=A*x+B*Sin(x);
        (V<C?l:r)=x;
    }
    printf("%Lf\n",lf(LD(U*r+D)/U));
}