Electrical computers: arithmetic processing and calculating – Electrical digital calculating computer – Particular function performed
Reexamination Certificate
2000-02-15
2002-04-02
Ngo, Chuong Dinh (Department: 2787)
Electrical computers: arithmetic processing and calculating
Electrical digital calculating computer
Particular function performed
C708S276000
Reexamination Certificate
active
06366939
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates to integrated circuits, and more particularly to integrated circuits for performing arithmetic operations.
BACKGROUND OF THE INVENTION
Many microprocessors such as the popular Intel X86 series and their clones contain apparatus for computing exponential and trigonometric functions. Such functions are useful in diverse areas of engineering, science, and mathematics, as well as in computer graphics applications. Using previously known methods, such functions may take a long time to compute. For example, the computation of sine and cosine functions can take approximately 100 clock cycles for some operands on the Intel Pentium processor and more than 300 clock cycles on the Intel 486.
1
This information came from a document entitled “Everything You Always Wanted to Know about Math Coprocessors,” published on the Internet by Norbert Juffa.
We will now reference various known types of circuits for computing exponential and trigonometric functions.
1. Table lookup method. The pure table lookup method involves keeping a table of the values of the function to be computed for every possible argument x. This approach was seriously considered for 16 bits of precision, but is no longer feasible for higher precision processors such as the high-end processors of today. Table-lookups are now only feasible for approximating such functions, as disclosed in U.S. Pat. No. 5,224,064, entitled “Transcendental Function Approximation Apparatus and Method,” to M. Henry and G. Martin.
2. Polynomial approximation method. For example one could compute e
x
by using the first “few” terms of the infinite series
e
x
=
∑
i
=
0
∞
x
i
i
!
.
This series converge quickly for small values of x but converges too slowly for larger values of x. There are other series than power series that may lead to better convergence. However, it is not clear how to speed up such a procedure further. For example, it is not clear how to combine several iterations into one.
3. Combined method. It is possible to combine the two aforementioned methods. Tang, for example, (P. T. P. Tang, “Table-lookup algorithms for elementary functions and their error analysis,” Proc. 10th Symp. Computer Arith.) designed such a method, which is used in the Intel Pentium processor. However, like the previous method, it is not clear how to speed up such a procedure further.
4. Method of rational approximation. This method is efficient, but requires a very fast divider, which is expensive.
5. Digit-by-digit methods. This class of methods, which includes the new one discussed in this document, is a very commonly used class of methods for hardware evaluation of exponential, trigonometric, and other transcendental functions. The methods in this class are based on simple iterative equations that imply only addition/subtraction and shift operations. Simple as the methods may be, they traditionally suffer from slow linear convergence.
These iterative methods were first discovered by Volder (J. E. Volder, “The CORDIC Trigonometric Computing Technique,” IRE Trans. Electronic Computers,” Vol. 8, pp. 330-334, 1959). Recent references include a U.S. Patent (Nakayama, U.S. Pat. No. 4,956,799, Sep. 11, 1990) where the inventor called these iterative methods “pseudo-division.”
The principles behind these iterative methods for computing transcendental functions will now be described.
The basic, well-known method for computing e
x
for x &egr; [0, ln 2) involves 2 recurrences, as follows:
x
i+1
=x
i
−ln b
i
(1)
y
i+1
=y
i
b
i
(2)
Here x
0
is the operand, x, where x can be limited to the range [0, ln 2) because any computation of e
x
where x is not in this range can be reduced to a computation of e
x
where x is in this range. (Israel Koren's book entitled
Computer Arithmetic Algorithms,
Prentice-Hall, 1993, explains this point as well as the entire traditional algorithm.)
We iterate according to (1) until x
n
=0 for some n. We then have x
n
=0=x
0
−&Sgr;
i=1
n−1
ln b
i
, that is, x
0
=ln &pgr;
i=0
n−1
b
i
. Hence it follows that &pgr;
i=0
n−1
b
i
=e
x0
, which is e
x
. Solving the recurrence (2) for y
n
yields y
n
=y
0
&pgr;
i=0
n−1
b
i
=y
0
e
x
, which is just slightly more general than e
x
. Thus the task of computing e
x
is reduced to the task of finding a sequence {b
i
} and a number n such that &Sgr;
i=0
n−1
ln b
i
=x and then computing y
0
&pgr;
i=0
n−1
b
i
. In order to be useful, the b
i
's must not merely exist, but it must also be easy to compute a product by each b
i
. It turns out that if b
i
=1+s
i
2
−i
, where s
i
=0 or 1 would satisfy the aforementioned properties.
The remaining thing to consider is how to choose s
i
for each i to guarantee convergence of the x
i
's to zero. It turns out that we can pick s
i
by trial subtraction: First try picking s
i
to be 1, yielding x
i+1
=x
i
−ln(1+2
−i
). If x
i+1
≧0, then the choice of s
i
is correct.
But otherwise, choose s
i
=0 instead, yielding x
i+1
=x
i
. This process is akin to that of bit-by-bit division, hence the name “pseudodivision” for these iterations.
It is not apparent how to combine several such iterations into 1 step. Ercegovac (M. Ercegovac, “Radix-16 Evaluation of Certain Elementary Functions,” IEEE Trans. Comput., C-22: 561-566 (1973)) showed how to compute the logarithm and exponential functions in radix-16. However, each iteration is done at a fairly high cost, and it is not clear how Ercegovac's scheme can be adapted to the computation of sine and cosine.
Accordingly, notwithstanding the abovementioned methods used in machinery for computing exponential and trigonometric functions, there continues to be a need for new types of machinery for computing such functions that are fast and not too large.
SUMMARY OF THE INVENTION
It is therefore the object of the present invention to provide circuits for computing exponential and trigonometric functions at high speed and reasonable cost.
This and other objects of the invention are provided by a circuit that uses a novel computational method wherein eight radix-2 iterations (which we will also call “logical iterations”) are combined into one larger iteration (which we will also call “physical iterations”). In each of the logical (that is, radix- 2) iterations, only low-precision (and therefore very fast) adders are used, causing temporary error to accumulate. After each physical (larger) iteration (comprising 8 logical (smaller) iterations) is completed, fast and complete correction of the aforementioned temporary error is performed. After eight physical iterations and corrections, all 64 smaller iterations would therefore be completed quickly and without error, that is, with no more error than if we were to simply perform only the smaller iterations in the first place.
REFERENCES:
patent: 4910698 (1990-03-01), McCartney
patent: 4956799 (1990-09-01), Nakayama
patent: 5737253 (1998-04-01), Madisetti
patent: 6317764 (2001-11-01), Rarick
No associations
LandOfFree
Apparatus for computing exponential and trigonometric functions does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Apparatus for computing exponential and trigonometric functions, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Apparatus for computing exponential and trigonometric functions will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2843240