Electrical computers: arithmetic processing and calculating – Electrical digital calculating computer – Particular function performed
Reexamination Certificate
1999-08-24
2002-09-24
Ngo, Chuong Dinh (Department: 2124)
Electrical computers: arithmetic processing and calculating
Electrical digital calculating computer
Particular function performed
C708S553000
Reexamination Certificate
active
06457036
ABSTRACT:
FIELD OF THE INVENTION
This invention relates to the processing of mathematical data, and more particularly to a system for accurately and efficiently performing an integer multiply-divide operation to perform calculations of the form (A*B)/C, whose intermediate product or quotient would exceed the largest or smallest value that can be handled by the processor, without the need for complex software or floating point hardware.
PROBLEM
Users and developers of applications and systems desire reliable, faster, and more accurate results in their calculations. Increasingly, highly numerical applications are being implemented for products using embedded microprocessors which lack the hardware to perform floating point calculations. An example would be data and voice network traffic switch hardware which must make calculations of the form (A*B)/C whose intermediate product or quotient would exceed the largest or smallest storable value.
For example, suppose the result of the computation ((80,000*100,000)/800,000) is desired. If the solution were to be coded in software in a typical manner, the first step of the computation would be to compute one of the following three possible intermediate results: (80,000*100,000), (80,000/800,000), or (100,000/800,000). However, in a processor using 32-bit integer-only arithmetic, the operation of (80,000*100,000) cannot be computed directly because the result, (8,000,000,000), is nearly double the largest possible quantity, (4,294,967,295), which can be held in an unsigned 32-bit binary quantity. Using integer-only arithmetic, (80,000/800,000) or (100,000/800,000) would yield zero for the same reason. Hence, there is no order in which the calculation can be performed that generates the correct final result. Yet, the final result of the computation ((80,000*100,000)/800,000) is 10,000, which can be easily held in a 32-bit unsigned integer quantity.
Previous approaches for determining such a multiply-divide result include using floating point hardware; and for a processor without floating point hardware, using complex software to emulate floating point operations which typically has a memory image that is large in size (too large for many applications). In addition to being complex, floating point emulation is too slow for certain real-time applications. What is needed is a less complex, fast and accurate method and apparatus for determining the result of integer calculations of the form (A*B)/C.
SOLUTION
The present system for accurately and efficiently performing an integer multiply-divide operation efficiently determines the result of a multiple-divide operation having the form of (A*B)/C and produces an approximate but relatively accurate result. If the values of A, B, and C provide for an easy solution (A, B, or C are zero; A equals C or B equals C; or A or B equals one), the result is directly computed. Otherwise, if the product of A and B produces an overflow condition, A and/or B are scaled by a tracked number of bits so that the product of scaled A and B would fit in an integer variable of the processor. Then, the product of scaled or unscaled A and B is computed. If C is large compared to the calculated product of A*B, C is scaled to minimize the likelihood of a false zero as a result. Then, the result is scaled if required. The system for accurately and efficiently performing an integer multiply-divide operation also provides for (1) returning the largest unsigned integer value if the result of the integer multiple-divide operation is larger than what can be stored in an unsigned integer variable; (2) returning an amount of scaling required to the returned product to produce an accurate result; and (3) rounding, truncating, or taking the floor value of the result. Thus, the result of a multiple-divide operation having the form of (A*B)/C is efficiently determined by the present system for accurately and efficiently performing an integer multiply-divide operation, with the computed result being at least a close approximation of the exact result that would be computed using more complex and costly comutation methods.
Embodiments of the present system for accurately and efficiently performing an integer multiply-divide operation include computer-readable medium containing computer-executable instructions for performing the method of the present system for accurately and efficiently performing an integer multiply-divide operation, and a computer system having a processor and memory and performing the method of the present system for accurately and efficiently performing an integer multiply-divide operation. An embodiment of the method of the present system for accurately and efficiently performing an integer multiply-divide operation provides for determining an integer result of the quotient of the product of an integer A times and an integer B divided by an integer C using integer multiplication and division. An embodiment of this method can be performed comprising the steps of: (a) scaling the integer A and the integer B if the integer product of the integer A times the integer B will cause an overflow condition; (b) calculating the integer product of the scaled integers A and B; and (c) dividing the product by the integer C to produce the integer result. In an embodiment, this method further performs the step of: (d) scaling the value of the integer C before performing step (c); and possibly further performs the step of: (d) scaling the product determined in step (c). In an embodiment of the present system for accurately and efficiently performing an integer multiply-divide operation, the resultant integer result is rounded, truncated, or set to a floor value of the integer result. In an embodiment of the present system for accurately and efficiently performing an integer multiply-divide operation, if the values of the integers A, B and C comprise a simplified solution; then the simplified solution is determined without performing steps (a), (b), and (c). In an embodiment of the system for accurately and efficiently performing an integer multiply-divide operation, when the integer result would exceed the largest value storable in an integer variable, the integer result is set to the largest storable integer value.
REFERENCES:
patent: 5454011 (1995-09-01), Shimoyoshi
patent: 5576977 (1996-11-01), Eskildsen
patent: 5732389 (1998-03-01), Kroon et al.
patent: 5808924 (1998-09-01), White
patent: 6178186 (2001-01-01), Baker et al.
Avaya Technology Corp.
Ngo Chuong Dinh
Patton & Boggs LLP
LandOfFree
System for accurately performing an integer multiply-divide... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with System for accurately performing an integer multiply-divide..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and System for accurately performing an integer multiply-divide... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2824829