3. 컴퓨터 연산

비트와 바이트

  • 1 비트 - 0 또는 1로 표현
  • 1 바이트 = 1 비트
  • 4 바이트 = 32 비트; single precision
  • 8 바이트 = 64 비트; double precision

비트 수열 $S$의 정수값은 다음과 같이 표현된다.

(1)
\begin{align} I = \sum_{i=1}^N 2^{i-1} S_i \end{align}

e.g. $1110_{(2)} = 2^3 \times 1 + 2^2 \times 1 + 2^1 \times 1 + 2^0 \times 0 = 14_{(10)}$
32비트 최대 정수값은 $2^{32} - 1 = 4,294,976,295.$
음수는 단일 비트가 아닌 두 개 비트의 합으로 나타낸다.

  1. 0과 1을 반전시킨 비트를 서로 더한다.
  2. 마지막 비트에 1을 더한다.
(2)
\begin{align} & 22_{(10)} = & 00010110_{(2)} \\ & & 11101001_{(2)} \\ + & & 1_{(2)} \\ \hline & & 11101010_{(2)} & = - 22_{(10)} \end{align}

부동소수점

십진부동소수점(Decimal Floating-Point Numbers)

(3)
\begin{align} x = \sigma \cdot \xi \cdot 10^e \end{align}
  • $x$: 0이 아닌 수
  • $e$: 정수 지수(exponent)
  • $1 \le \xi \le 10$: 가수(mantissa)
  • $\sigma = \pm 1$: 부호(sign)

예:

(4)
\begin{align} {50 \over 3} = (+1) \cdot (1.6666 \cdots )_{(10)} \cdot 10^1 \end{align}

이진부동소수점(Binary Floating-Point Numbers)

(5)
\begin{align} x = \sigma \cdot \xi \cdot e^2 \end{align}
  • $x$: 0이 아닌 수
  • $e$: 정수 지수(exponent)
  • $1 \le \xi \le 10_{(2)} = 2$: 가수(mantissa)
  • $\sigma = \pm 1$: 부호(sign)

예:

(6)
\begin{align} {.1}_{(10)} = (+1) \cdot (1.10011001100 \cdots )_{(2)} \cdot 2^{-4} \end{align}

모든 컴퓨터는 $\xi, e$ 값에 한계가 있다 — 부동소수점한계

정밀도

단정밀도(Single Precision) - float

  • 총 4바이트 = 32비트
(7)
\begin{align} fl(x) = \sigma \cdot (1. a_{1} a_{2} \cdots a_{23})_{(2)} \cdot 2^e \end{align}
  • $\sigma$에 1 비트, 가수 $\xi$에 23비트, 지수 $e$에 8비트 사용

배정밀도(Double Precision) - double

  • 총 8바이트 = 64비트
(8)
\begin{align} fl(x) = \sigma \cdot (1. a_{1} a_{2} \cdots a_{52})_{(2)} \cdot 2^e \end{align}
  • $\sigma$에 1 비트, 가수 $\xi$에 52비트, 지수 $e$에 11비트 사용

복소수

#include <stdio.h>
#include <complex.h> 
int main()  
    {
        double complex z1 = 1.0 + 3.0 * I; 
        double complex z2 = 1.0 - 4.0 * I; 
        printf(%.2f % +.2fi\n", creal(z2), cimag(z2)); 
 
        double complex sum = z1 + z2; 
        double complex difference = z1 - z2; 
        double complex product = z1 * z2; 
        double complex quotient = z1 / z2; 
        double complex conjugate = conj(z1); 
        printf("%.2f %+.2fi\n", creal(conjugate), cimag(conjugate)); 
        return 0;
    }

계산기 엡실론

  • 특정 부동소수점의 계산기 엡실론(machine epsilon) = 1과 그 부동소수점에서 저장될 수 있는 다음 숫자 사이의 차이
  • 부동소수점 표시의 정확도의 척도

예:

  • 단정밀도에서 1 다음의 숫자는 1.00000000000000000000001(2) (소수점 아래 23째 자리에 1)
  • 단정밀도의 계산기 엡실론 $\epsilon = 2^{-23} \simeq 1.19 \times 10^{-7}$
  • 배정밀도에서 1 다음의 숫자는 1.0000000000000000000000000000000000000000000000000001(2) (소수점 아래 52째 자리에 1)
  • 단정밀도의 계산기 엡실론 $\epsilon = 2^{-52} \simeq 2.22 \times 10^{-16}$
  • 가수 저장의 비트수(위 참조)만큼 소수점 아래

반올림

  • 계산기 엡실론이라는 한계가 있으므로 모든 실수를 컴퓨터로 나타낼 수는 없다
  • 부동소수점 계산 결과가 그 정밀도에서 표시할 수 없는 숫자일 때 반올림(rounding)이 이루어짐

예컨대 $x = \sigma \cdot ( 1. a_2 \cdots a_n \cdots )_{(2)} \cdot 2^e$

  • 최적반올림(Optimal rounding): 가장 가까운 표시할 수 있는 수를 사용한다.
    • $fl(x) = \begin{cases} \sigma \cdot (1. a_2 \cdots a_n)_{(2)} \cdot 10^e & a_{n+1} = 0 \\ \sigma \cdot [(1. a_2 \cdots a_n)_{(2)} + (0.0 \cdots 1)_{(2)}] \cdot 10^2 & a_{n+1} = 1 \end{cases}$
  • 버림(rounding by chopping): 넘어서는 부분 그냥 버림
    • $fl (x) = \sigma \cdot ( 1. a_2 \cdots a_n )_{(2)} \cdot 2^e$

반올림 오차

반올림 오차: $x - fl(x)$

  • 반올림 오차는 작게 만들 수 있어도 아예 피할 수는 없다
  • 수치해석의 엄격한 오차분석의 기본: 반올림 상대오차가 계산기 엡실론보다 작아야 한다.
(9)
\begin{align} {{\left\lvert x - fl(x) \right\rvert } \over { \left\lvert x \right\rvert }} \le \epsilon \end{align}

예: $x = (1. d_1 \cdots d_{23} ; d_{24} \cdots ) \cdot 2^e$ (단정밀도)

  • $fl (x) = (1. d_1 \cdots d_{23} ; 0 ) \cdot 2^e$ (버림)
  • $\left\lvert x - fl(x) \right\rvert$$\le (0.00 \cdots 0;11 \cdots ) \cdot 2^e \\ \le (0.00 \cdots 1;00 \cdots ) \cdot 2^e \\ = \epsilon \times 2^e \\ \le \epsilon \times \left\lvert x \right\rvert$

알고리듬의 안정성

  • 반올림 오차가 작고 유한하다면 알고리듬은 안정하다.
  • 어떤 경우 반올림 오차가 증폭된다. 이때 알고리듬은 불안정하다.

예:

  • $y = (1 - x)^6$
  • $y = 1 - 6x + 15 x^2 - 20 x^3 + 15 x^4 - 6 x^5 + x^6$
  • 후자의 오차가 상당히 더 크다.

다른 예:

(10)
\begin{align} f(x) = x [ \sqrt{x + 1} - \sqrt{x} ] \end{align}
$x$ $f(x)$ 계산값 $f(x)$ 참값
1 .414210 .414214
10 1.54340 1.54347
100 4.99000 4.98756
1000 15.8000 15.8074
10000 50.0000 49.9988
100000 100.000 158.113
(11)
\begin{align} f(x) = {{x} \over {\sqrt{x+1} + \sqrt{x}}} \end{align}

로 고쳐 쓰는 것이 좋다.

또 다른 예:

(12)
\begin{align} f(x) = {{1 - \cos (x) } \over {x^2}} \end{align}
$x$ $f(x)$ 계산값 $f(x)$ 참값
0.1 0.4995834700 0.4995834722
0.01 0.4999960000 0.4999958333
0.001 0.5000000000 0.4999999583
0.0001 0.5000000000 0.4999999996
0.00001 0.0 0.5000000000

테일러 전개로 고쳐 쓰는 것이 좋다.

(13)
\begin{align} f(x) \approx {1 \over {2!}} - {{x^2} \over {4!}} + {{x^4} \over {6!}} \end{align}

덧셈

(14)
\begin{align} S = a_1 + a_2 + \cdots + a_n \qquad \left\{ a_1, \cdots a_n \right\} \end{align}

을 계산할 때, 큰 것부터 작은 순서로 더해야 할까, 작은 것부터 큰 순서로 더해야 할까, 아니면 주어진 수열 순서대로 더해야 할까?

(15)
\begin{align} S_2 & = fl(a_1 + a_2) & = (1 + \epsilon _2 ) ( a_1 + a_2 ) \\ S_3 & = fl(S_2 + a_3) & = (1 + \epsilon _3 ) ( S_2 + a_3 ) \\ S_4 & = fl(S_3 + a_4) & = (1 + \epsilon _4 ) ( S_3 + a_4 ) \\ & \vdots & \vdots \\ S_n & = fl(S_{n-1} + a_n) & = (1 + \epsilon _n ) ( S_{n-1} + a_n ) \\ \end{align}
(16)
\begin{align} \implies S - S_n = & - a_1 ( \epsilon_2 + \cdots + \epsilon_n ) \\ & - a_2 ( \epsilon_2 + \cdots + \epsilon_n ) \\ & - a_3 ( \epsilon_3 + \cdots + \epsilon_n ) \\ & - a_4 ( \epsilon_4 + \cdots + \epsilon_n ) \\ & \vdots \\ & - a_n \epsilon_n \end{align}

$a_1, a_2$에 곱해지는 $\epsilon_j$가 가장 크므로, $a_1, a_2$는 작아야 오차가 작아질 것이다. 즉, 반올림 오차를 줄이기 위해서는

(17)
\begin{align} \left\lvert a_1 \right\rvert \le \left\lvert a_2 \right\rvert \le \cdots \le \left\lvert a_n \right\rvert \end{align}

를 만족해야(작은 것부터 더해야) 한다.

이것은 최적화된 방법은 아니지만 그냥 주어진 순서대로 더하는 것이나 큰 것부터 더하는 것보다는 훨씬 좋다.