algospot.com :: 질답 및 토론 - double 형의 정확도 문제

글수 62

double 형의 정확도 문제

nocut98

http://www.algospot.com/zbxe/?document_srl=48519

2008.08.07 03:27:21 (*.49.160.253)

1629

413 div2-medium, div1-easy 문제인데요.

double minCommonDifference(int a0, vector <int> seq) {
    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);
    }
    for(int i=0; i<seq.size(); ++i) {
        int t = a0 + (i+1)*lo;
        if(t != seq[i]) return -1;
    }
    return lo;
}

요렇게 하면 틀립니다 (정확도가 문제인가 봐요)
같은 코드를 살짝 바꿔서

double minCommonDifference(int a0, vector <int> seq) {
    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;
}

요렇게 하면 패스 하구요.
쉽게 말해서 lo라는 값은 정확히 구하는데, 이 구한 값이 맞는지 확인하는 과정에서 자꾸 정확도 문제로 오류가 발생하는데요.
double형의 정확도 문제를 어느정도 안다고 생각했는데, 저렇게 구하면 뭐가 문제인 걸까요 ㅠ_ㅠ

이 게시물을..

2008.08.07 14:43:22 (*.151.244.22)

nocut98

다시 곱해서 해당 integer가 나오는 게 쉽지가 않군요 ㅡ.ㅜ
다른 분들은 double형을 대하실 때 어떤식으로 처리하시는 지 궁금합니다

2008.08.08 17:48:07 (*.44.133.5)

astein

아마 저 소스에서는 정확도 문제가 아니라 floor 문제 아닐까요?

int t = -1.8 로 하면 -1이 나올텐데, [-1.8] = -2 니까요.

2008.09.17 00:43:48 (*.55.180.112)

free7942g

짧은 생각으로는 클래스를 하나 이용해서 double을 흉내내며
연산자 오버로딩한 함수에서 오차를 찾아내면 바로 예외를 던져서
임시 방편으로 찾아 내는 것도 괜찮을 것 같습니다.
C#에서 double 입실론을 바꿀 수 있으면 좋겠지만..
이상 알고리즘이랑은 별 관계 없는 이야기였습니다.;;;

2008.09.17 14:10:36 (*.146.211.175)

오차를 찾아낸다는 것이 좀 어렵죠. ^^; 우리 입장에서야 어떤 값이 되어야 할 지 알 수 있지만, 컴퓨터야 double 밖에 없으니 ;;

2008.09.17 16:30:23 (*.151.244.22)

nocut98

double 형을 사용하는 문제의 경우 연산이 좀 겹치기 시작하면 어떻게 풀면 괜찮고, 어떻게 풀면 안되는지 감이 별로 없어요

뭐 예를 들어서 곱셈이 한 10번 이상 된다 싶으면 오차 때문에 다른 방법을 찾아야 한다던지...

다른 분들은 어떤 기준을 가지고 double형 문제에 접근하시는 지 궁금하네요 :)

2008.09.17 17:34:13 (*.132.168.145)

음 그러게요. 저도 알고리즘의 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 (불안정성) 을 완전히 피해서 코드를 작성하는 것은 이상적인 경우의 이야기고.. 언제나 그럴 수 있진 않지요. 따라서, 코드를 따라가면서, 오차가 어떤 형식으로 누적되는지, 범위 밖을 벗어나는 값을 언제 사용하게 되는지 등을 볼 수 있는 능력이 있어야 하겠지요. 음.. 타겟이 되려면 -.- ㅋㅋㅋㅋ

2008.09.17 17:16:07 (*.55.180.61)

free7942g

아예 분자와 분모가 모두 BigInt 형을 가지는 유리수 클래스를 정의하는 것도 좋을 것 같습니다.

2008.09.17 17:36:31 (*.132.168.145)

예, 실제로 유리수 클래스를 사용하는 것은 실전에서도 많이 사용되는 테크닉이죠. ^^ 하지만 항상 사용할 수 있는 것은 아니죠. sqrt 나 exp 같은 연산들이 포함되거나, pi 같은 상수도 못 쓰니까..;;

번호		글쓴이	조회수	날짜
62	질문 (2008 Dhaka) 간단한 문제(?)인데, 더해주세요[.....] 6	wookayin	242	2008-12-23
61	질문 이런 문제의 풀이 방법은?? 11	leedohyun	281	2008-11-30
60	질문 Prime K tuple 문제 좀 풀어주세요ㅜ- ㅠ 4	zelos89	338	2008-11-19
59	질문 ICPC I번 에 대해서.. 5	dgsquare	276	2008-11-17
58	질문 재밌는 논문 추천해주세요~ 12	유키	368	2008-11-12
57	질문 백트래킹(!?)문제 질문입니다~ 5	LucidaSH	356	2008-11-10
56	질문 초보자 알고리즘 질문 하나만요,ㅜ 5	페브리즈	273	2008-11-01
55	질문 모의 고사 접속관련 1	야드버즈	151	2008-11-01
54	index tree 질문있습니다. 2	ibroker	206	2008-10-30
53	질문 ICPC 온라인 예선 D번문제 어떻게 풀었나여? 3	dgsquare	443	2008-10-09
52	질문 2년째 눈팅하고 있는 청년(?)입니다. 몇가지 질문좀~~ 6	compilerkim	513	2008-10-07
51	질문 어제 ACM ICPC H번문제..질문이요. 5	거부기	672	2008-09-28
50	질문 ACM internet competition 연습문제 ㅠㅠ 12	Arbitrator	817	2008-09-27
49	질문 ACM 온라인예선 연습문제 A번 8	설지	595	2008-09-26
48	질문 1주년 모의고사를 신청했는데 메일이 안오네요 1	jangc	405	2008-09-19
47	질문 icpc 온라인 2004년도 F문제 어떻게 푸나요? 11	포아	633	2008-09-17
	double 형의 정확도 문제 8	nocut98	1630	2008-08-07
45	질문 어디 동적계획법문제 모아논거 없을까요? 10	포아	1084	2008-08-05
44	질문 GCJ Round1 에디토리얼 써주세요~ 2	soyoja	928	2008-07-28
43	질문 궁금한게있어요... 3	minkyung	1289	2008-06-19

쓰기

첫페이지 1 2 3 4 끝페이지