6개의 댓글이 있습니다.
-
-
JongMan -
음 그러게요. 저도 알고리즘의 floating point stability 에 대해서는 아는 것이 별로 없습니다. ^^; 이번 학기에 수치해석 듣는데 관련 얘기 나오면 한번 강좌라도 올려보죠.
일단 제가 아는 대로 써 보자면.. 실수를 사용하는 이상 오차는 늘 생길 수밖에 없습니다. (범위 안의 정수만 사용하신다면, 정확성이 보장됩니다만..) 중요한 점은 오차가 큰 영향을 주지 않는 코드를 작성하는 것이지요. 코드 한 줄마다, 만약 이 값이 1e-12 만큼 다르다고 해도, 항상 비슷한 (정답과 1e-10 이하로 차이나는) 결과가 나올까? 라는 질문을 던져 보시면 답이 나옵니다.
예를 들어, (7.0 / 4.0) * 4.0 이라는 식을 계산한다고 할 때, 7.0 / 4.0 부에서 1e-12 만큼의 오차가 났다고 합시다. 하지만, 그 이후에 4 를 곱해도, 오차는 꼴랑 4e-12 가 될 뿐입니다. 충분히 용납할 수 있는 오차이지요. 하지만 여기에 floor() 를 씌운다면? 그때는 1e-12 차이에 의해 답이 1 이나 차이날 수 있게 됩니다. 따라서, 이런 경우를 가능한한 피하는 프로그램을 작성해야 합니다.
예를 들어:
해가 반드시 2개 있다고 할때 2차 방정식의 해를 구하기 => 중간 과정에 오차가 난다고 해도 해는 별로 달라지지 않으니 안정적입니다.
두 원이 접하는지 판단하기 => 오차가 조금 나면 완전 교차한다고 볼 수도 있고, 닿지 않았다고 판단할 수 있으니 불안정합니다.
이런 식이죠.
사실 floating point instability (불안정성) 을 완전히 피해서 코드를 작성하는 것은 이상적인 경우의 이야기고.. 언제나 그럴 수 있진 않지요. 따라서, 코드를 따라가면서, 오차가 어떤 형식으로 누적되는지, 범위 밖을 벗어나는 값을 언제 사용하게 되는지 등을 볼 수 있는 능력이 있어야 하겠지요. 음.. 타겟이 되려면 -.- ㅋㅋㅋㅋ
16년 전 link
-
-
정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.
nocut98
413 div2-medium, div1-easy 문제인데요. seq) {
long double t = (long double)(seq[i]-a0)/(long double)(i+1);
int t = a0 + (i+1)*lo; seq) {
[code c++]
double minCommonDifference(int a0, vector
long double lo(0), hi(1e26);
for(int i=0; i
lo = max(lo, t);
}
for(int i=0; i
if(t != seq[i]) return -1;
}
return lo;
}
[/code]
요렇게 하면 틀립니다 (정확도가 문제인가 봐요)
같은 코드를 살짝 바꿔서
[code c++]
double minCommonDifference(int a0, vector
long double lo(0), hi(1e26);
for(int i=0; i<seq.size(); ++i) {
long double t = (long double)(seq[i]-a0)/(long double)(i+1);
lo = max(lo, t);
t = (long double)(seq[i]-a0+1)/(long double)(i+1);
hi = min(hi, t);
}
if(lo<hi) return lo;
else return -1;
}
[/code]
요렇게 하면 패스 하구요.
쉽게 말해서 lo라는 값은 정확히 구하는데, 이 구한 값이 맞는지 확인하는 과정에서 자꾸 정확도 문제로 오류가 발생하는데요.
double형의 정확도 문제를 어느정도 안다고 생각했는데, 저렇게 구하면 뭐가 문제인 걸까요 ㅠ_ㅠ
16년 전