Electrical computers: arithmetic processing and calculating – Electrical digital calculating computer – Particular function performed
Reexamination Certificate
1998-12-28
2001-07-03
Ngo, Chuong Dinh (Department: 2121)
Electrical computers: arithmetic processing and calculating
Electrical digital calculating computer
Particular function performed
C708S491000
Reexamination Certificate
active
06256656
ABSTRACT:
FIELD OF THE INVENTION
This invention relates to increasing the fixed-point precision of a digital computer. More specifically, it extends the existing fixed-point single precision of any computer by utilizing multiple processing components. Most significantly, this invention introduces the process of dinking to overcome the problem of performing modular division within a computer system.
BACKGROUND OF THE INVENTION
While performing arithmetic calculations, little thought is usually given to the question of how many decimal digits it takes to represent a number. For example, physicists can calculate that there are approximately 10{circumflex over ( )}78 electrons in the universe without being bothered by the fact that 79 decimal digits are required to write out that number in full. As another example, someone calculating the value of a function with pen and paper who needs the answer to six significant digits simply keeps intermediate results to seven, or eight, or however many digits are needed. The problem of the paper not being wide enough for seven-digit numbers never arises.
With computers, matters are quite different. On most computers, the amount of memory available for storing a number (single precision) is fixed at the time that the computer is designed. With a certain amount of effort, the programmer can represent numbers two, or three, or even many times larger than this fixed amount, but doing so does not change the nature of this difficulty.
The magnitude of numbers that a computer can represent is finite in nature, whereas the set of number is infinite in nature. Because of this inherent difference, encapsulating infinity with finite means will forever remain a quixotic quest. In fact, this constant clash between the finite confine of a digital computer and the infinity of numbers characterizes the special blend of challenges offered by computer science and computer hardware design in particular. A number whose size is larger than the given computer word size (known as single precision) underscores the fundamental question of how a large integer can be represented by a computer. Therefore, because the size of an integer can be quantified by the number of digits of an integer under consideration, and because the number of digits of an integer is also known as precision, the goal is to extend the precision of a computer word.
Stimulated by problems from computer science, mathematicians have begun to study computational algorithms in their own right. Consequently, new algorithms as well as creative and novel uses of well known classical mathematical algorithms are discovered. On the classical front, for the purpose of extending precision, one example of classical mathematical ideas that can be put to the service of computer science and particularly fixed-point precision extension is the methodology of modular arithmetic.
Modular arithmetic is useful in extending precision because the reformulated way of performing modular addition, modular subtraction, and modular multiplication becomes distributed and is thus more efficient. In particular, the essence of modular arithmetic is the method of “divide and conquer.” More particularly, this modular reformulation of arithmetic operations exploits parallelism, whereas the normal methods of performing arithmetic calculations are serial in nature. At the theoretical level, the procedure of representing a given integer n in modular arithmetic is to specify a finite set of k moduli m1, m2, . . . , mk that are “relatively prime” to each other, then divide the given integer n by m1, m2, . . . , mk respectively to obtain k remainders r1, r2, . . . , rk. Next, via the Chinese Remainder Theorem (CRT), this single integer n is reformulated and replaced by its modular representation as a set of k smaller integers, each of which lies within the limit of single precision. Thus, the integer n is denoted as a k-tuple (r1,r2, . . . , rk) or (r1=n mod m1, r2=n mod m1, . . . , rk=n mod mk) to emphasize the fact that the remainder r1 results from dividing n by m1, and so on. Finally, this k-tuple modular representation is converted back to the ordinary number representation by applying the Chinese Remainder Algorithm (CRA) that is at the core of the mathematical proof for the Chinese Remainder Theorem (CRT).
A brief discussion of CRT is highly relevent here because CRT plays a key role in the methodology of modular arithmetic. The story about the Chinese Remainder Theorem can be told in many ways. In a highly abstracted mathematical exposition, one could start with a Dedekind ring and the decomposition of the principal ideal into a product of prime ideals and then proceed further. But such an approach fail to portray the original landscape of CRT: integers and remainders under division. The opposite extreme of telling the story would consist of various numerical examples in the original landscape, with little general theory, or none whatsoever. However, the approach taken here lies between the two extreme approaches mentioned above. Indeed, the story of CRT to be told here can be labeled as application-oriented. During its long history, CRT has appeared in many disguises, never failing to find new aspects of application. An aspect inherent in the very core of CRT is computing: algorithm for taking calculation via a detour where much smaller numbers can be used.
CRT can be classified as belonging to an active field of mathematical research called modular arithmetic because it deals with and makes use of what is called modular arithmetical systems, or simply modular systems. There exists infinitely many modular arithmetic systems, and each of these arithmetic systems is in dexed by a positive integer called the modulus. One specific example of a modular arithmetical system is formed from the set of numbers {0, 1, 2}. In this system called the modular system mod 3, modular addition, modular subtraction, and modular multiplication are characterized by the following two tables:
+
0
1
2
×
0
1
2
0
0
1
2
0
0
0
0
1
1
2
0
1
0
1
2
2
2
0
1
2
0
2
1
At the intuitive level, CRT's usefulness can be demonstrated succinctly by the following scenario. If a person secretly selected a number n between 0 and 21, how much more information is needed to discover the selected number n? From the fact that 21 factorizes as 3*7, and with 3 and 7 being relatively prime to each other, CRT guarantees that if the remainder of n divided by 3 and the remainder of n divided by 7 are given, then the secretly selected number can be discovered by using CRA. To use a specific example, if the secretly selected number n between 0 and 21 is equal to 16, then by knowing 1 as the remainder of n divided by 3, and 2 as the remainder of n divided by 7, 16 can be discovered via CRA. Furthermore, to rephrase the above scenario in symbolic form, the 2-tuple (1,2) actually represents the integer 16.
On the other hand, to continue the above example at the more abstract level, CRT says that the structure formed by coupling the mod 3 system and the mod 7 system is equivalent to the structure of the mod 21 system. Or, using the mathematical jargon, these two structures are “isomorphic.” That is, whatever arithmetical action (excluding division) is carried out in one structure, the equivalent arithmetical action will also happen in the other structure. Accordingly, CRT can be thought of as the catalyst that enables the swift change for a given number's modular representation to shift from the mod 21 representation to the distributed (mod 3, mod 7) representation, then back to the mod 21 representation again.
One benefit of computing indirectly with integers in their modular representations is that the size of each integer under consideration is reduced to the size of the specified moduli m1, m1, . . . , mk. Therefore, doing arithmetic indirectly with modularly represented integers reduces the arithmetic complexity simply because the size of each integer under consideration, which is on the order to M=m1*m2* . . . *mk, is reduced to
Cam Winget Nancy
Gossett Carroll Philip
Ngo Chuong Dinh
Silicon Graphics Inc.
Wagner , Murabito & Hao LLP
LandOfFree
Apparatus and method for extending computational precision... 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 and method for extending computational precision..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Apparatus and method for extending computational precision... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2499327