현재 위치

홈 ›› Forums ›› 공부 ›› 프로그래밍 QnA

Rational 써보니

ifree의 이미지
글쓴이: ifree / 작성시간: 토, 2011/09/10 - 11:20오전

실수 연산의 유효숫자 한계의 문제로, 연산 결과가 0 보다 큰지 아닌지를 알아보는 판별식에서 부정확한 결과가 발생하는 바람에 boost 라이브러리의 rational 을 처음으로 써보려고,
실수를 int/int 형태의 분수로 표현하여 돌려 보았더니,

1. 속도가 10 배 이상 느려짐.
- 통분과 약분의 과정이 있다 해도 정수 연산이 이 정도로 느려진다는 사실에 낙담함.
2. 유효숫자의 문제는 역시 해결이 안됨을 뒤늦게 깨달음.
- long int 를 써도 근본적인 해결책이 안될 뿐 아니라 더 느려질 속도를 감당하기가 어려울 듯.

해서, 다시 실수 연산의 범위 안에서 해결책을 찾기 위해 고민 중인데,

이런 문제들은 어떻게 해결하시나요?

Forums: 
프로그래밍 QnA
snowall의 이미지

글쓴이: snowall / 작성시간: 일, 2011/09/11 - 12:52오전

제가 너무 단순하게 생각하는지는 모르겠으나...

일단 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

ifree의 이미지

글쓴이: ifree / 작성시간: 일, 2011/09/11 - 8:33오전

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 로도 해결이 안됩니다.

약간의 마진을 주면 되긴 하는데 찝찝하네요.

snowall의 이미지

글쓴이: snowall / 작성시간: 일, 2011/09/11 - 9:15오전

문자 앞의 부호가 같은 항끼리 몰아서, 아주 간단하게

D00*(D11*D22 -D12*D21) - D10*(D01*D22 - D02*D21) + D20*(D01*D12-D02*D11) = X - Y

이래놓고

X > Y

이걸 판별하면 되죠.

위 식은 아래 식과 동치인데

X/Y > Y/X

X나 Y가 둘 다 아주 작더라도 위와 같이 계산하면 양쪽이 어느정도 크기가 커져서 괜찮아질 것 같습니다.

그런데 유효숫자 문제는 본질적으로 해결이 안될 것 같다는 느낌이군요.

혹시, 원래의 D(ij)들이 int에서만 오는건가요? 아니면 int와 double에서 두루 섞여서 오는데 double로 캐스팅해서 연산하는건가요? 또는 순수하게 double에서만 오는지요

피할 수 있을때 즐겨라! http://melotopia.net/b

댓글 달기

텍스트 포맷에 대한 자세한 정보

Filtered HTML

  • 텍스트에 BBCode 태그를 사용할 수 있습니다. URL은 자동으로 링크 됩니다.
  • 사용할 수 있는 HTML 태그: <p><div><span><br><a><em><strong><del><ins><b><i><u><s><pre><code><cite><blockquote><ul><ol><li><dl><dt><dd><table><tr><td><th><thead><tbody><h1><h2><h3><h4><h5><h6><img><embed><object><param><hr>
  • 다음 태그를 이용하여 소스 코드 구문 강조를 할 수 있습니다: <code>, <blockcode>, <apache>, <applescript>, <autoconf>, <awk>, <bash>, <c>, <cpp>, <css>, <diff>, <drupal5>, <drupal6>, <gdb>, <html>, <html5>, <java>, <javascript>, <ldif>, <lua>, <make>, <mysql>, <perl>, <perl6>, <php>, <pgsql>, <proftpd>, <python>, <reg>, <spec>, <ruby>. 지원하는 태그 형식: <foo>, [foo].
  • web 주소와/이메일 주소를 클릭할 수 있는 링크로 자동으로 바꿉니다.

BBCode

  • 텍스트에 BBCode 태그를 사용할 수 있습니다. URL은 자동으로 링크 됩니다.
  • 다음 태그를 이용하여 소스 코드 구문 강조를 할 수 있습니다: <code>, <blockcode>, <apache>, <applescript>, <autoconf>, <awk>, <bash>, <c>, <cpp>, <css>, <diff>, <drupal5>, <drupal6>, <gdb>, <html>, <html5>, <java>, <javascript>, <ldif>, <lua>, <make>, <mysql>, <perl>, <perl6>, <php>, <pgsql>, <proftpd>, <python>, <reg>, <spec>, <ruby>. 지원하는 태그 형식: <foo>, [foo].
  • 사용할 수 있는 HTML 태그: <p><div><span><br><a><em><strong><del><ins><b><i><u><s><pre><code><cite><blockquote><ul><ol><li><dl><dt><dd><table><tr><td><th><thead><tbody><h1><h2><h3><h4><h5><h6><img><embed><object><param>
  • web 주소와/이메일 주소를 클릭할 수 있는 링크로 자동으로 바꿉니다.

Textile

  • 다음 태그를 이용하여 소스 코드 구문 강조를 할 수 있습니다: <code>, <blockcode>, <apache>, <applescript>, <autoconf>, <awk>, <bash>, <c>, <cpp>, <css>, <diff>, <drupal5>, <drupal6>, <gdb>, <html>, <html5>, <java>, <javascript>, <ldif>, <lua>, <make>, <mysql>, <perl>, <perl6>, <php>, <pgsql>, <proftpd>, <python>, <reg>, <spec>, <ruby>. 지원하는 태그 형식: <foo>, [foo].
  • You can use Textile markup to format text.
  • 사용할 수 있는 HTML 태그: <p><div><span><br><a><em><strong><del><ins><b><i><u><s><pre><code><cite><blockquote><ul><ol><li><dl><dt><dd><table><tr><td><th><thead><tbody><h1><h2><h3><h4><h5><h6><img><embed><object><param><hr>

Markdown

  • 다음 태그를 이용하여 소스 코드 구문 강조를 할 수 있습니다: <code>, <blockcode>, <apache>, <applescript>, <autoconf>, <awk>, <bash>, <c>, <cpp>, <css>, <diff>, <drupal5>, <drupal6>, <gdb>, <html>, <html5>, <java>, <javascript>, <ldif>, <lua>, <make>, <mysql>, <perl>, <perl6>, <php>, <pgsql>, <proftpd>, <python>, <reg>, <spec>, <ruby>. 지원하는 태그 형식: <foo>, [foo].
  • Quick Tips:
    • Two or more spaces at a line's end = Line break
    • Double returns = Paragraph
    • *Single asterisks* or _single underscores_ = Emphasis
    • **Double** or __double__ = Strong
    • This is [a link](http://the.link.example.com "The optional title text")
    For complete details on the Markdown syntax, see the Markdown documentation and Markdown Extra documentation for tables, footnotes, and more.
  • web 주소와/이메일 주소를 클릭할 수 있는 링크로 자동으로 바꿉니다.
  • 사용할 수 있는 HTML 태그: <p><div><span><br><a><em><strong><del><ins><b><i><u><s><pre><code><cite><blockquote><ul><ol><li><dl><dt><dd><table><tr><td><th><thead><tbody><h1><h2><h3><h4><h5><h6><img><embed><object><param><hr>

Plain text

  • HTML 태그를 사용할 수 없습니다.
  • web 주소와/이메일 주소를 클릭할 수 있는 링크로 자동으로 바꿉니다.
  • 줄과 단락은 자동으로 분리됩니다.
댓글 첨부 파일
이 댓글에 이미지나 파일을 업로드 합니다.
파일 크기는 8 MB보다 작아야 합니다.
허용할 파일 형식: txt pdf doc xls gif jpg jpeg mp3 png rar zip.
CAPTCHA
이것은 자동으로 스팸을 올리는 것을 막기 위해서 제공됩니다.