기하관련 코딩을 하다보면 컴퓨터에서의 수치오차 때문에 골치아플 때가 있다.

일반적인 어플리케이션에서는 값이 1000.000 이건 1000.001 이건간에 큰 차이가 없을 수도 있지만,

기하 알고리즘에서는 그 차이 때문에 두 도형이 만나는지/안만나는지 가 갈릴 수도 있기 때문이다.

기하 알고리즘이 아니더라도 시뮬레이션 같은이 계산결과가 누적되는 곳에서는 오차가 누적되서 커질 수 있기 때문에 역시 문제가 되곤 한다.

한 예로, 걸프전 당시 미군에서 사용하던 패트리어트 미사일은, 뉴스에서 요란하게 떠들던것과는 다르게 실제로 명중률이 굉장히 낮았다.

실수 계산을 할때 수치오차를 제대로 고려하지 않아서 엉뚱한 결과가 나왔기 때문이다.

(왼쪽이 정상적으로 계산되어야할 미사일 궤도. 오른쪽이 y축의 float오차때문에 깍여서 실제 계산된 궤도)


이러한 수치오차가 발생하는 이유는 컴퓨터가 실수를 저장할때

유효숫자의 n승 형태로 저장하기 때문이다.

그래서 더하기나 빼기를 할때 특히나 문제가 되는데 (왜 곱하기가 아니라 더하기 인지는 유효숫자*n승 표현으로 직접 계산해보면 알듯...)


이런 수치오차를 해결하는 한가지 방법은 float이 아니라 좀 더 많은 유효숫자를 가지는 double을 사용하는거다.

하지만 double로 해서도 문제가 생길 경우에는 숫자들을 더할때 약간 더 조심함으로서 계산오차를 줄일 수 있는 방법들이 있다.


그중 한가지 방법이 작은수부터 더하는건데, 이때 얼마나 많은 수를 더할지 모르기 때문에,

가변인수를 사용하면 코딩을 좀 더 쉽게 할 수 있다.

최근 코딩을 하면서 가변인수로 만들어둔 함수가 있어서 붙여본다.

#include <stdio.h>
#include <vector>
#include <math.h>
#include <stdarg.h>
#include <algorithm>

using namespace std;

bool lessABS(const double& lhs, const double& rhs)
{
return fabs(lhs) < fabs(rhs);
}

double numeric_addition(int num,...){
     double sum=0.0;
     vector<double> v;
     int i;
     va_list ap;
     double arg;

     v.assign(num,0);
     va_start(ap,num);
     for (i=0;i<num;i++) {
          arg=(double)va_arg(ap,double);
          v[i] = arg;
     }
     va_end(ap);

     sort(v.begin(),v.end(),lessABS);
     for(i=0;i<(int)v.size();i++){
         sum+=v[i];
     }
     return sum;
}

int main(int argc, char **argv){
double a = 10000000000000000;
double b = 1;
double c = 1;
printf("%lf\n",numeric_addition(3,a, b, c));
printf("%lf\n",a+b+c);

return 0;
}




10000000000000000(경)에다가 1을 두번 더해보면, 일반적으로 1000000000000+1+1을 하면 1경이 그대로 나오지만,

위의 numeric_addition함수를 이용해서 더하면 올바른 값이 나옴을 알 수 있다.


위 numeric_addition함수의 첫번째 숫자는 argument의 수를 말한다. (여기서는 3개의 숫자를 더했으므로 3)

저작자 표시
신고

'공부' 카테고리의 다른 글

작지도,크지도, 같지도 않다. -1.#IND  (0) 2010.12.29
언어의 모호성  (0) 2010.11.16
가변인수(va_arg)를 이용한 계산오차 줄이기  (3) 2010.08.02
계산기하 - 원 포함 알고리즘 코딩  (0) 2010.06.03
NP, NP-COMPLETE, NP-HARD  (7) 2010.05.05
for문에서 j  (3) 2010.04.26
Posted by youknow04
요즘에는 모처럼 계산기하 관련 코딩을 하고있다.

평면위에 원들이 있을때 각각의 원들을 일부라도 포함하는 가장 작은 원을 찾는 문제다.

(까만원들이 이렇게 문제로 주어졌을때,
모든 까만원의 일부라도 포함하거나 터치하는 원들 중 가장 작은 저 빨간 원을 찾으면 된다.)


재밌는건 원의 갯수를 n개라고 했을때,

이 문제는 n개의 원을 x축을 따라서 정렬하는것보다 빠르게 풀 수 있다는거다.(시간복잡도가 expected O(n))


재미없는건...

사실 논문으로 쓸때에는 99%의 지면을 할당하는 주요 알고리즘이 코드에서는 10%가량밖에 안되고

it's trivial 이라고 논문에 적은 1%에 해당하는 부분이 저 코드의 90%에 해당한다는거다.


예를들면 단순히 3개의 원을 터치하는 가장 작은 원을 찾는 trivial한 문제조차도

실제 구현하려면 비선형 연립 방정식을 풀어야한다.

논문에서는 매우 직관적이고 우아한 알고리즘이지만

구현은 지옥임.

근데 사실 굳이 이 문제만이 아니라 계산기하쪽 알고리즘들이 대부분 그런듯...


아무튼 이제 거의 구현해서 코드 돌리고 xml로 결과 뽑아서 ipe에서 열어봤더니 위에 그럼처럼 이쁘게 나온다.

이걸 열심히 구현한 공로(?)로 논문에 공저자로도 들어갈것 같으니 조만간 그간 노력한 보람이 있을듯하다.
저작자 표시
신고

'공부' 카테고리의 다른 글

언어의 모호성  (0) 2010.11.16
가변인수(va_arg)를 이용한 계산오차 줄이기  (3) 2010.08.02
계산기하 - 원 포함 알고리즘 코딩  (0) 2010.06.03
NP, NP-COMPLETE, NP-HARD  (7) 2010.05.05
for문에서 j  (3) 2010.04.26
SQL injection on python+SQLite3  (0) 2010.04.02
Posted by youknow04

구글 코드잼 2010

일상 2010.05.24 17:35


최근 파이썬으로 코드잼이라는 프로그래밍 대회에 참가해서 재밌게 하고있다.

퀄리피케이션과 Round1 까지는 통과한 상태.


프로그래밍을 대학에 와서야 접한지라 프로그래밍 대회 같은거에서 별다른 성적이 없었는데

요즘 재밌게 배우던 내 파이썬 실력이 이런 국제대회 같은데서도 먹히는것 같아서 기분이 좋다.


워낙에 괴물 같은 실력을 가진 사람들이 많아서

다음 라운드에는 어떻게 될지 모르겠지만...

계산기하 알고리즘 연구하면서 틈틈히 이런 대회식의 문제풀이 같은것도 익히면

내년쯤에 다시 참가할때는 더 좋은 성적을 낼 수 있지 않을까?
저작자 표시
신고

'일상' 카테고리의 다른 글

구글 코드잼 2010  (0) 2010.05.24
티스토리로 블로그 이전  (0) 2010.05.11
AAAC2010  (0) 2010.04.18
일본여행  (0) 2010.02.08
귀국  (0) 2009.09.04
IEEE 인공지능 대회  (0) 2009.08.08
Posted by youknow04


티스토리 툴바