곱셈기를 이용한 정확한 부동소수점 제곱근 계산기 = An exact floating point square root calculator using multiplier

국문 초록 (Abstract)

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

다국어 초록 (Multilingual Abstract)

There are two major algorithms to find a square root of floating point number, one is the Newton_Raphson algorithm and GoldSchmidt algorithm which calculate it approximately by iterating multiplications and the other is SRT algorithm which calculates it exactly by iterating subtractions. This paper proposes an exact floating point square root algorithm using only multiplication. At first an approximate inverse square root is calculated by Newton_Raphson algorithm, and then an exact square root algorithm by reducing an error in it and a compensation algorithm of it are proposed. The proposed algorithm is verified to calculate all of numbers in a single precision floating point number and 1 billion random numbers in a double precision floating point number. The proposed algorithm requires only the multipliers without another hardware, so it can be widely used in an embedded system and mobile production which requires an efact square root of floating point number.

참고문헌 (Reference)

1 조경연, "개선된 뉴톤-랍손 역수 및 역제곱근 알고리즘" 한국해양정보통신학회 11 (11): 46-55, 2007

2 김성기, "가변 시간 골드스미트 부동소수점 제곱근 계산기" 한국해양정보통신학회 9 (9): 188-198, 2005

3 C. V. Freiman, "Statistical Analysis of Certain Binary Division Algorithm" 49 : 91-103, 1961

4 D. L. Harris, "SRT Division Architectures and Implementations" 1997

5 이원, "Radix-4 SRT 알고리즘을 사용한 나눗셈/제곱근 연산기에 관한 연구" 33 (33): 1996

6 M. Flynn, "On Division by Functional Iteration" C-19 (C-19): 702-706, 1970

7 S. F. McQuillan, "New Algorithms and VLSI Architectures for SRT Division and Square Root" IEEE 80-86, 1993

8 M. D. Ercegovac, "Improving Goldschmidt Division, Square Root, and Square Root Reciprocal" 49 (49): 759-763, 2000

9 S. Oberman, "Floating Point Division and Square Root Algorithms and Implementation in the AMD-K7 Microprocessors" 106-115, 1999

10 S. F. Oberman, "Design Issues in Division and Other Floating Point Operations" C-46 : 154-161, 1997

11 R. Goldschmidt, "Application of division by convergence" MIT 1964

12 D. L. Fowler, "An Accurate, High Speed Implementation of Division by Reciprocal Approximation" IEEE 60-67, 1989