곱셈기를 사용한 정확한 제곱근 알고리즘

Abstract

부동소수점 나눗셈 및 제곱근 연산은 곱셈을 반복하는 뉴턴-랍손 알고리즘 과 골드스미트 알고리즘, 뺄셈을 반복하는 SRT 알고리즘이 있다. 본 논문에 서는 IEEE-754에서 요구하는 정확한 제곱근을 배정도 정수 곱셈기를 사용하 여 연산하는 제곱근 알고리즘을 제안한다. 즉, 뉴턴-랍손 알고리즘을 이용하여 근사 역제곱근을 구하고, 이의 오차를 줄이면서 제곱근을 구하는 알고리즘과 계산된 제곱근을 보정하는 알고리즘을 제안한다. 제안한 알고리즘은 단정도 실수에서는 전수 조사를 통해서, 배정도 실수에서는 10억개의 무작위 수에서의 계산을 통하여 모두 정확한 값을 얻어 서 알고리즘을 검증했다. 본 논문에서 제안한 알고리즘은 배정도 정수 곱셈기만을 사용하므로 부동소 수점 연산을 위한 별도의 하드웨어가 필요하지 않다. 따라서 실장제어용기기, 휴대용기기 등 정확한 제곱근 연산을 요구하는 분야에서 사용될 수 있다.

Floating point division and square root operation have two kinds of method, one is a repetition of multiplication, Newton-Raphson algorithm and Goldschmidt's algorithm, the other is a repetition of subtraction, SRT algorithm. On this paper, square root algorithm is suggested, which use double format digit multiplier for satisfying the accuracy required on IEEE-754. Using Newton-Raphson algorithm, approximate reversed square root is calculated, and one algorism for re-calculating square root reducing the error from above operation and the other algorithm for revising the calculated value are suggested. The correctness of the suggested algorithm is verified by investigating the total number on floating point and by investigating the randomly subtracted billion number on double. The suggested algorithm on this paper only use a double format digit multiplier, so an additional hardware is not required for floating point operation. This algorithm could be used requiring an accurate square root operation.