제곱근을 구하는 sqrt() 함수를 구현하고자 한다면, 뉴턴의 방법(Newton Method)을 사용해서 근사식을 얻는 것에서부터 출발한다. 그러나, 제곱근을 뉴턴의 방법을 적용해본다면, 다시 같은 식이 반복되어 나오기 때문에, 구하고자 하는 x를 대수로 정의하고 이것에서부터 출발해보자.
x = x(i) + d
여기서 x는 구하고자 하는 x 값이고, x(i)는 초기값, 그리고 d는 오차이다.
그리고, a = x^2이라 한다면, a = (x(i) + d)^2으로 표현할 수 있고, a = x(i)^2 + 2x(i) * d + d^2의 꼴로 전개할 수 있다. 여기서, d는 초기값 x(i)가 x에 매우 가깝게 추측되었다고 가정한다면, 그리고 d가 무시할 수 있을 정도라면 d^2은 매우 0에 가까울 것이다. 따라서, a = x(i)^2 + 2x(i) * d로 정리할 수 있다. 이제, 오차 d에 대해서 이 식을 정리하면,
d = (a - x(i)^2) / 2x(i)를 얻을 수 있으며, 이것을 x = x(i) + d에 대해 정리한다면, 다음과 같은 식을 얻을 수 있다.
x ≒ x(i) + (a - x(i)^2) / 2x(i)
최종적으로, x ≒ 1 / 2 * (a / x(i) + x(i))의 식을 얻게 되는데, 이것이 sqrt() 함수의 근사식이 된다.
그러나, 바로 이 식을 sqrt() 함수의 구현으로 사용할 수는 없다. 왜냐하면, x(i)는 초기에 주어져야 하는 추측값이며, 이 값이 구하고자 하는 x와 얼마나 가까운지 알 수 없기 때문이다. 또, 이것은 근사식이므로, 첫 번째 과정에서 구해진 x 값을 반복적으로 다음 초기값 x(i)의 자리에 넣어서 원하는 오차 이내로 들어올 때까지 반복해서 계산해야 한다. 결국, 이 말은 오차 범위를 측정해서 해당 오차 이내가 될 때까지 반복 계산해야 한다는 말인데, 매우 비효율적이다. 따라서, 이 sqrt() 함수를 최적화하는 것은, 초기값을 얼마나 잘 추측할 수 있는지, 그리고 오차를 줄이기 위한 반복 계산을 얼마나 줄일 수 있는지가 관건이 된다.
이 두 가지 사항을 다루기 전에, sqrt() 함수를 계산하는데 있어서 기본적인 전략은 위의 근사식을 사용해 구하고자 하는 값에 근사시킨다는 것을 기억하자. 만약, 아주 큰 수가 입력으로 들어온다면, 비교적 정확한 값에 도달하기 위해 상당히 많은 반복 계산이 필요하다(근사식을 보라). 이것을 줄이기 위해서, 부동소수점의 저장 방식과 제곱근 함수의 특성을 이용해보자. 부동소수점은, 대부분의 경우 IEEE 754 방식으로 저장되며, 여기서 실제로 필요한 정보는 가수(mantissa)이다. 즉, 지수 부분 계산은, 제곱근의 특성을 이용하여 그냥 반으로 내려주고, 필요한 가수만 입력값으로 넣어주면 반복 계산을 크게 줄일 수 있다. 그리고, 부동소수점 형식에서의 가수는 대부분 표준화(normalization)되어 있는 형태이기 때문에, 입렵값의 범위도 제한되어 있다. 이것은 중요한 최적화 전략이 된다.
먼저, 초기값을 적절하게 추측하기 위해 이 표준화를 살펴보도록 하자. 표준화는 소수점 자리의 왼쪽에 1이 남을 때까지 계속 소수점 자리를 이동하는 것을 말하며, 결과적으로 모든 가수는 1.xxxx의 형태가 된다. (이동된 자리수는 지수 부분에 저장된다) 그리고, 표준화를 거치면 언제나 소수점의 왼쪽에는 1이 있기 때문에 1은 저장하지 않아도 되며, 결과적으로 비트 하나를 절약하는 셈이 된다. 그리고, 이러한 특징 때문에 가수는 0.5 이상, 1 미만의 값을 가지게 된다. 즉, 실제로 sqrt()에서 입력으로 받아야 할 것은 0.5와 1 사이에 있는 값이 된다. 즉, sqrt(0.5)와 sqrt(1)의 기하평균(geometric mean)을 구해보면,
x(i) = (1 * (2^(0.5) / 2))^(1 / 2) ≒ 0.840896
이며, 이 값을 초기값으로 선택하면 주어진 값을 그대로 초기값으로 사용하는 것보다 훨씬 빠르게 실제 값에 빠르게 근사한다.
그러나, 이것은 sqrt(0.5)와 sqrt(1)의 양쪽 극단값에 대한 기하평균 값이므로, 이것보다 좀 더 좋은 초기값을 선택할 수 있는 여지가 있다. 즉, 제곱근 그래프에서, 0.5와 1을 통과하는 어떤 직선의 방정식을 생각해볼 수 있으며, 이 직선이 sqrt(0.5)와 sqrt(1)에서의 오차가 같다면, 이것을 초기값을 결정할 수 있는 직선의 방정식으로 선택할 수 있다. 오차를 나타내는 식 E(x)를 다음과 같이 정의한다면,
E(x) = (f(x) - r(x)) / f(x), f(x) = x^(1 / 2), r(x) = Bx + a
E(0.5) = E(1)이며, 이것을 바탕으로 B = 2^(1 / 2) * A를 얻을 수 있다. 즉, r(x) = A * (1 + 2^(1 / 2) * x)이다.
< not complete >
x = x(i) + d
여기서 x는 구하고자 하는 x 값이고, x(i)는 초기값, 그리고 d는 오차이다.
그리고, a = x^2이라 한다면, a = (x(i) + d)^2으로 표현할 수 있고, a = x(i)^2 + 2x(i) * d + d^2의 꼴로 전개할 수 있다. 여기서, d는 초기값 x(i)가 x에 매우 가깝게 추측되었다고 가정한다면, 그리고 d가 무시할 수 있을 정도라면 d^2은 매우 0에 가까울 것이다. 따라서, a = x(i)^2 + 2x(i) * d로 정리할 수 있다. 이제, 오차 d에 대해서 이 식을 정리하면,
d = (a - x(i)^2) / 2x(i)를 얻을 수 있으며, 이것을 x = x(i) + d에 대해 정리한다면, 다음과 같은 식을 얻을 수 있다.
x ≒ x(i) + (a - x(i)^2) / 2x(i)
최종적으로, x ≒ 1 / 2 * (a / x(i) + x(i))의 식을 얻게 되는데, 이것이 sqrt() 함수의 근사식이 된다.
그러나, 바로 이 식을 sqrt() 함수의 구현으로 사용할 수는 없다. 왜냐하면, x(i)는 초기에 주어져야 하는 추측값이며, 이 값이 구하고자 하는 x와 얼마나 가까운지 알 수 없기 때문이다. 또, 이것은 근사식이므로, 첫 번째 과정에서 구해진 x 값을 반복적으로 다음 초기값 x(i)의 자리에 넣어서 원하는 오차 이내로 들어올 때까지 반복해서 계산해야 한다. 결국, 이 말은 오차 범위를 측정해서 해당 오차 이내가 될 때까지 반복 계산해야 한다는 말인데, 매우 비효율적이다. 따라서, 이 sqrt() 함수를 최적화하는 것은, 초기값을 얼마나 잘 추측할 수 있는지, 그리고 오차를 줄이기 위한 반복 계산을 얼마나 줄일 수 있는지가 관건이 된다.
이 두 가지 사항을 다루기 전에, sqrt() 함수를 계산하는데 있어서 기본적인 전략은 위의 근사식을 사용해 구하고자 하는 값에 근사시킨다는 것을 기억하자. 만약, 아주 큰 수가 입력으로 들어온다면, 비교적 정확한 값에 도달하기 위해 상당히 많은 반복 계산이 필요하다(근사식을 보라). 이것을 줄이기 위해서, 부동소수점의 저장 방식과 제곱근 함수의 특성을 이용해보자. 부동소수점은, 대부분의 경우 IEEE 754 방식으로 저장되며, 여기서 실제로 필요한 정보는 가수(mantissa)이다. 즉, 지수 부분 계산은, 제곱근의 특성을 이용하여 그냥 반으로 내려주고, 필요한 가수만 입력값으로 넣어주면 반복 계산을 크게 줄일 수 있다. 그리고, 부동소수점 형식에서의 가수는 대부분 표준화(normalization)되어 있는 형태이기 때문에, 입렵값의 범위도 제한되어 있다. 이것은 중요한 최적화 전략이 된다.
먼저, 초기값을 적절하게 추측하기 위해 이 표준화를 살펴보도록 하자. 표준화는 소수점 자리의 왼쪽에 1이 남을 때까지 계속 소수점 자리를 이동하는 것을 말하며, 결과적으로 모든 가수는 1.xxxx의 형태가 된다. (이동된 자리수는 지수 부분에 저장된다) 그리고, 표준화를 거치면 언제나 소수점의 왼쪽에는 1이 있기 때문에 1은 저장하지 않아도 되며, 결과적으로 비트 하나를 절약하는 셈이 된다. 그리고, 이러한 특징 때문에 가수는 0.5 이상, 1 미만의 값을 가지게 된다. 즉, 실제로 sqrt()에서 입력으로 받아야 할 것은 0.5와 1 사이에 있는 값이 된다. 즉, sqrt(0.5)와 sqrt(1)의 기하평균(geometric mean)을 구해보면,
x(i) = (1 * (2^(0.5) / 2))^(1 / 2) ≒ 0.840896
이며, 이 값을 초기값으로 선택하면 주어진 값을 그대로 초기값으로 사용하는 것보다 훨씬 빠르게 실제 값에 빠르게 근사한다.
그러나, 이것은 sqrt(0.5)와 sqrt(1)의 양쪽 극단값에 대한 기하평균 값이므로, 이것보다 좀 더 좋은 초기값을 선택할 수 있는 여지가 있다. 즉, 제곱근 그래프에서, 0.5와 1을 통과하는 어떤 직선의 방정식을 생각해볼 수 있으며, 이 직선이 sqrt(0.5)와 sqrt(1)에서의 오차가 같다면, 이것을 초기값을 결정할 수 있는 직선의 방정식으로 선택할 수 있다. 오차를 나타내는 식 E(x)를 다음과 같이 정의한다면,
E(x) = (f(x) - r(x)) / f(x), f(x) = x^(1 / 2), r(x) = Bx + a
E(0.5) = E(1)이며, 이것을 바탕으로 B = 2^(1 / 2) * A를 얻을 수 있다. 즉, r(x) = A * (1 + 2^(1 / 2) * x)이다.
< not complete >
