Electrical computers: arithmetic processing and calculating – Electrical digital calculating computer – Particular function performed
Reexamination Certificate
1998-11-18
2001-10-16
Malzahn, David H. (Department: 2121)
Electrical computers: arithmetic processing and calculating
Electrical digital calculating computer
Particular function performed
Reexamination Certificate
active
06304889
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates generally to the implementation of an exponential function in computers, and, in particular, to an optimal set of instructions for performing an exponential function.
2. Description of the Related Art
One of the most important and widely used mathematical library functions in nearly every computer is one to evaluate integer powers of “real” or floating-point numbers. For example, the notation X**N (where X is usually called the base and N is called the exponent or power) is used in nearly every high-level language to represent this operation, in expressions such as “AREA=PI*R**2”.
Prior art implementations generally involve looking at the binary representation of the exponent N, and doing successive floating point squaring of X and/or multiplications by X or X**2. This technique is currently used in the mathematical function libraries of Fortran, PL/I, COBOL, Pascal, APL, etc.
The primary shortcoming of the prior art is that the “bookkeeping overhead” of determining the bits of N and figuring out whether or not to square or multiply takes more instructions than for the actual evaluations. In early computers, floating point operations were relatively slow, so this was a reasonable approach. Now that floating point operations are fairly fast, the ratio of “useful” work to “overhead” is low.
Thus, there is a need in the art for improved methods of performing exponential functions.
SUMMARY OF THE INVENTION
To overcome the limitations in the prior art described above, and to overcome other limitations that will become apparent upon reading and understanding the present specification, the present invention discloses a method, apparatus, and article of manufacture for performing an exponential function on a base X raised to a power of N in a manner that maximizes computing efficiency, as well as a data and/or code structure for use when the function is performed. The exponential function initially positions at a starting node in an exponential tree stored in a memory, wherein the starting node represents the value of N. A working value W is created in the memory and the working value W is initially set equal to the base X. The exponential tree is traversed from the starting node to an answer node and the working value W is updated at each node encountered during the traversal. The working value is squared when a next node is above and to the right of the current node. Otherwise, the working value is squared and a result thereof is multiplied by X when the next node is above and to the left of the current node. This working value W is finally outputted as a result of the exponential function when the root of the tree is reached.
REFERENCES:
patent: 4225933 (1980-09-01), Monden
patent: 5177702 (1993-01-01), Lindsley
patent: 6128638 (2000-10-01), Thomas
IBM Program Product: IBM System/360 OS Fortran IV Mathematical and Serivice Subprograms Supplement for MOD I and MOD II Libraries, first edition (Mar. 1971), see p. 20.
Donald E. Knuth,Seminumerical Algorithms, The Art of Computer Programming, vol. 2 second edition (1981), “Evaluation of Powers”, see pp. 441-467.
IBM System/360 Operating System Fortran IV Library—Mathematical and Service Subprograms, IBM Systems Reference Library, Program No. 360S-LM-501, second edition (Sep. 1972), see pp. 41-42.
IBM vs Fortran Version 2 Language and Library Reference, Release 1.1, second edition (Sep. 1986), see pp. 430-431.
Donald E. Knuth,Seminumerical Algorithms, The Art of Computer Programming, vol. 2 (second Edition) 1981, “Answers to Exercises,” see pp. 632-639.
Gates & Cooper LLP
International Business Machines - Corporation
Malzahn David H.
LandOfFree
Exponential optimization does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Exponential optimization, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Exponential optimization will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2585721