구간연산에 대해서

Published: 2019-09-21
Last modified:
Category • Tech

컴퓨터의 구조적 한계

컴퓨터는 기본적으로 2진연산을 다루고, 사람은 10진법을 사용하기 때문에 10진수를 2진수로 바꾸기 위한 규칙이 필요하다. 현용되는 컴퓨터의 소숫점 연산에 관한 규칙은 IEEE754에 정의되어 있고, 거의 모든 컴퓨터가 이를 따르게 되어있다.

현용 64비트 컴퓨터의 소숫점(double, float64)은
부호(s,1 bit)+지수(e, 11 bits)+밑(b, 52 bits) (밑? 이라고 하는게 맞는지 모르겠다)

\[(-1)^{s}\left(1+\sum\limits_{i=1}^{52}b_{52-i}2^{-i}\right)\times 2^{e-1023}\]

$2^{10}$ 은 대략 $10^3$정도 되기때문에 b로 표현 할 수 있는 약 $10^{-15}$ 까지는 수 사이의 간격보다
컴퓨터가 표현할 수 있는 해상도가 더 높기 때문에 값을 신뢰할 수 있지만,
그 아래로 내려갈 경우 10진수 소수 사이의 간격보다 컴퓨터의 간격이 더 크기 때문에 값을 정확하게 표현 할 수 없다.

숫자가 무작정 작은게 문제가 아니라, b로 표현할 수 있는 값이 문제가 된다.

예를 들면(보기 쉽게 소수 4자리씩 끊었다.)

  • 5e-17
    • 0.0000 0000 0000 0000 5000 0000 0000 0000 0000 0000 0000 00
    • 0.0000 0000 0000 0000 4999 9999 9999 9999 8954 8893 3620 17
    • 위가 10진수 표현, 아래가 그 수와 가장 가까운 float값을 나타낸다.
    • 오차: $(1.0451106637983)\times 10^{-16} \times 10^{-17}$

그러나
2.0000 0000 0000 0000~
2.0000 0000 0000 0009 사이의 값을 보면

2.0000 0000 0000 0000 -> 2.0000 0000 0000 0000
2.0000 0000 0000 0001 -> 2.0000 0000 0000 0000
2.0000 0000 0000 0002 -> 2.0000 0000 0000 0000
2.0000 0000 0000 0003 -> 2.0000 0000 0000 0004 4408 9209 85006
2.0000 0000 0000 0004 -> 2.0000 0000 0000 0004 4408 9209 85006
2.0000 0000 0000 0005 -> 2.0000 0000 0000 0004 4408 9209 85006
2.0000 0000 0000 0006 -> 2.0000 0000 0000 0004 4408 9209 85006
2.0000 0000 0000 0007 -> 2.0000 0000 0000 0008 8817 8419 70013
2.0000 0000 0000 0008 -> 2.0000 0000 0000 0008 8817 8419 70013
2.0000 0000 0000 0009 -> 2.0000 0000 0000 0008 8817 8419 70013

각각의 숫자를 제대로 계산해내지 못하는걸 알 수 있다.

이 부분에 관한 더 자세한 설명은 Round-off error, Machine epsilon 등의 검색어로 검색하면 나온다.

컴퓨터의 구조적 한계2

그런데 수 자체엔 문제가 없는 경우도 있다.

\[\begin{pmatrix} 64919121& -159018721\\ 41869520.5&-102558961 \end{pmatrix} \begin{pmatrix} x\\ y \end{pmatrix}= \begin{pmatrix} 1\\ 0 \end{pmatrix}.\]

위 식을 python으로 풀어보면,

import numpy as np
a = 64919121
b = -159018721
c = 41869520.5
d = -102558961
A = np.array([[a,b],[c,d]])
B = np.array([[1],[0]])
answer1 = np.linalg.solve(A,B)
print(answer1)
# [[1.06018308e+08]
#  [4.32817930e+07]]
print(np.dot(A,answer1))
# [[1.]
#  [0.]]

값이 생략되어 있긴 한데 Matlab으로 소숫점을 전부 표현해보면 \(\begin{pmatrix} x\\ y \end{pmatrix}=\begin{pmatrix} 106018308.0071325\\ 43281793.0017831 \end{pmatrix},\)

손계산 다 하고 계산한 경우 \(\begin{align} x_1 &= \frac{d}{ad-bc}\\ x_2 &= \frac{-c}{ad-bc} \end{align}\)

x1 = d/(a*d-b*c)
x2 = -c/(a*d-b*c)
print(x1,x2)
# (102558961.0, 41869520.5)
answer2 = np.array([[x1],[x2]])
print(np.dot(A,answer2))
# [[1.]
#  [0.]]

두 방법 모두 검산에도 문제가 없다.

정답은 \(\begin{pmatrix} x\\ y \end{pmatrix}=\begin{pmatrix} 205117922\\ 83739041 \end{pmatrix},\)

혹시 진짜인가 싶은분은 손으로 계산해보시기 바란다.

구간연산

이러한 문제를 해결 할 수 있는 방법 중 하나가 구간 연산(Interval Arithmetic)이다.

구간 연산에서는 값을 point로 저장하는 것이 아닌 $[\text{lower_bound},\text{upper_bound}]$의 형태로 저장한다.
lower_bound와 upper_bound는 반드시 2진 소수 표현으로 표현 가능한 수이기 때문에 중간에 값이 오염되지 않는다.

계산 결과도 구간으로 출력되기 때문에, 우리는 이 값을 해석할 때에
“정답(Real Solution)은 lower_bound와 upper_bound 사이에 반드시 존재한다.”라고 결론을 내릴 수 있다.

이전의 2x2행렬 연산을 Matlab의 구간연산 라이브러리인 INTLAB를 사용해서 연산할 경우
$(x,y)=(\text{NaN},\text{NaN})$ 을 출력하기 때문에 사용자가 연산이 잘못되었음을 인식할 수 있다.

Related Posts