Rational 써보니
글쓴이: ifree / 작성시간: 토, 2011/09/10 - 11:20오전
실수 연산의 유효숫자 한계의 문제로, 연산 결과가 0 보다 큰지 아닌지를 알아보는 판별식에서 부정확한 결과가 발생하는 바람에 boost 라이브러리의 rational 을 처음으로 써보려고,
실수를 int/int 형태의 분수로 표현하여 돌려 보았더니,
1. 속도가 10 배 이상 느려짐.
- 통분과 약분의 과정이 있다 해도 정수 연산이 이 정도로 느려진다는 사실에 낙담함.
2. 유효숫자의 문제는 역시 해결이 안됨을 뒤늦게 깨달음.
- long int 를 써도 근본적인 해결책이 안될 뿐 아니라 더 느려질 속도를 감당하기가 어려울 듯.
해서, 다시 실수 연산의 범위 안에서 해결책을 찾기 위해 고민 중인데,
이런 문제들은 어떻게 해결하시나요?
Forums:
제가 너무 단순하게 생각하는지는
제가 너무 단순하게 생각하는지는 모르겠으나...
일단 x가 (컴퓨터 관점에서)0인지 아닌지 판별하는 루틴이라면, 1/x를 알아보면 되겠죠. x=0이라면 NaN이나 Inf가 반환될겁니다.
이미 이걸 써서 문제가 발생한 경우라면, x가 0이 아닌데 1/x가 표현 가능 범위를 넘어가서 발생하는 것이겠죠. 그럼 1/x를 작게 줄여주면 되고, x에 꽤 큰 수를 곱해주면 됩니다. x에 꽤 큰수라면, 실수에서 표현 가능한 최대값 근처의 수를 곱해주면 될거라고 생각합니다. x가 진짜 0이라면 아무리 큰 수를 곱해도 0이 될 것이니 잘 작동할겁니다.
그런데, 부호 있는 실수라면 적어도 하나의 비트는 그 부호를 알려주지 않나요?
http://en.wikipedia.org/wiki/Floating_point
혹시 이런 문제가 아닌가요...
피할 수 있을때 즐겨라! http://melotopia.net/b
Delaunay 알고리듬을 이용해 삼각형이 유효한지를
Delaunay 알고리듬을 이용해 삼각형이 유효한지를 판별하는 식인데 다음과 같은 연산의 결과를 리턴합니다.
D00*(D11*D22 -D12*D21) - D10*(D01*D22 - D02*D21) + D20*(D01*D12-D02*D11)
저 값이 0보다 크면 삼각형을 버리게 되는데, 문제는 곱셈 과정에서 유효숫자들이 소실되면서 0에 아주 가까운 결과에서는 0보다 커야할 결과가 0보다 작아지거나 그 반대의 결과가 발생합니다.
또 애당초 D00 등의 값이 1/13 등과 같이 무한소수인 경우도 있어서 arbitrary precision floating number 로도 해결이 안됩니다.
약간의 마진을 주면 되긴 하는데 찝찝하네요.
문자 앞의 부호가 같은 항끼리 몰아서, 아주
문자 앞의 부호가 같은 항끼리 몰아서, 아주 간단하게
이래놓고
이걸 판별하면 되죠.
위 식은 아래 식과 동치인데
X나 Y가 둘 다 아주 작더라도 위와 같이 계산하면 양쪽이 어느정도 크기가 커져서 괜찮아질 것 같습니다.
그런데 유효숫자 문제는 본질적으로 해결이 안될 것 같다는 느낌이군요.
혹시, 원래의 D(ij)들이 int에서만 오는건가요? 아니면 int와 double에서 두루 섞여서 오는데 double로 캐스팅해서 연산하는건가요? 또는 순수하게 double에서만 오는지요
피할 수 있을때 즐겨라! http://melotopia.net/b
댓글 달기