Electrical computers: arithmetic processing and calculating – Electrical digital calculating computer – Particular function performed
Reexamination Certificate
1999-06-07
2002-05-14
Ngo, Chuong Dinh (Department: 2121)
Electrical computers: arithmetic processing and calculating
Electrical digital calculating computer
Particular function performed
Reexamination Certificate
active
06389443
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates generally to a square-root computation, and, more particularly, to a square-root computation embodied in a fixed-point processor or an Application Specific Integrated Circuit (ASIC).
BACKGROUND OF THE INVENTION
In many real time applications, the square root operation serves as an “inner loop” operation, i.e. an operation called repeatedly as a subroutine by other subroutines of an application. Thus, the ultimate efficiency of a real time application is critically dependent on the efficiency of an underlying square root operation. In particular, this is true in audio signal processing and compression applications.
Computing the square root of any number can be a complicated and intensive computation. A fixed-point processor typically does not directly support this type of operation. That is, a fixed-point processor typically does not have a built-in instruction to compute a square root. If any application requires this function it must be implemented as an approximation in the software. The accuracy of the approximation depends significantly on the complexity of the calculations. Better approximations need more calculations and, conversely, more calculations produce better approximations.
A common technique for computing a square root operation is an iterative process called the Newton-Raphson technique. The Newton-Raphson technique is implemented using the following equation:
x(n+1)=½(x(n)+{fraction (&agr;/x(n))})
The number “a” designates the number for which the square root is to be computed. The iterative process starts with n=0. The iterative process then proceeds with x(n+1) being calculated as a function of x(n) where n=1, 2, . . . N. The number of iteration cycles N needed to achieve an accurate approximation to the square root may be minimized by carefully choosing a start value. A well-chosen start value x(0) is typically stored in a predefined lookup-table.
The main problem with the Newton-Raphson technique is that a high computational load is needed to make the final result reliable. In many cases this technique is so computationally intensive, that further approximation must be done to make the calculation efficient. This will of course give an even more imprecise result. Another problem is that the look-up table occupies expensive memory area.
In view of the foregoing, it would be desirable to provide a technique which overcomes the above-described inadequacies and shortcomings. More particularly, it would be desirable to provide a technique for calculating the square root of a number in an efficient and cost effective manner.
SUMMARY OF THE INVENTION
According to the present invention, a technique for efficiently computing an approximation to the square root of a number X is provided. The number X is typically represented in a fixed-point binary form. In one embodiment, the technique can be realized by setting a first register of a processor to the number X. A second register of the processor is set to a number L, wherein the number L indicates a number of significant bits of X. The number L is right shifted in the second register by one bit to produce a number N. The number X is right shifted in the first register by N bits to produce a number X
1
. A third register of the processor is set to 1 and left shifted by N bits to produce the result N
1
in the third register. The results N
1
and X
1
are added and shifted right by one bit to produce an approximation to the square root of X. Typically, the processor is a general purpose computer system, but may also be an Application Specific Integrated Circuit.
REFERENCES:
patent: 4336599 (1982-06-01), Wong
patent: 4949296 (1990-08-01), Malinowski
patent: 5157624 (1992-10-01), Hesson
patent: 5341321 (1994-08-01), Karp et al.
patent: H1385 (1994-12-01), Stickel et al.
patent: 5386375 (1995-01-01), Smith
patent: 5537345 (1996-07-01), Nakano
patent: 5539682 (1996-07-01), Jain et al.
patent: 5602768 (1997-02-01), Cunto et al.
Fast Algorithm Computes Square Root by Bruce Komusin; EDN Electrical Design News; vol. 32, No. 24; Nov. 26, 1987, pp. 250-252, XP000717382.
An Algorithm for High Speed Square Roots by Bob Conover and Donald L. Gustafson; Proceedings of the Region 5 Conference, Lubbock, Texas, Mar. 13-15, 1985, Mar. 1, 1985, pp. 19-21; XP000758038; Institute of Electrical and Electronics Engineers.
Square Root Algorithms for Integer and Floating-Point Numbers by Reza Hashemian; IEEE Transactions on Computers, vol. 39, No. 8; Aug. 1, 1990, pp. 1025-1029, XP000143033.
Jenkens & Gilchrist P.C.
Ngo Chuong Dinh
Telefonaktiebolaget LM Ericsson
LandOfFree
Method and apparatus for an efficient square-root computation does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and apparatus for an efficient square-root computation, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for an efficient square-root computation will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2871671