Electrical computers: arithmetic processing and calculating – Electrical digital calculating computer – Particular function performed
Reexamination Certificate
2000-05-10
2004-06-29
Ngo, Chuong Dinh (Department: 2121)
Electrical computers: arithmetic processing and calculating
Electrical digital calculating computer
Particular function performed
C708S490000
Reexamination Certificate
active
06757700
ABSTRACT:
FIELD OF THE INVENTION
The invention relates to a method of computer calculations that avoids round off errosion. It further relates to optimizing noise processing operations, such as spectral analysis, filtering, cancellation, in telecommunications, medical or instrumentation systems. It performs the usual arithmetic (+/*−) and transcendental/trigonometric operations on floating point numbers, the most prevalent representation of real numbers on diverse computer architectures. These properties stem directly from the behavior of the D Scale.
BACKGROUND OF THE INVENTION
Digital numerical calculation involves round off errors that accumulate when repetitive operations are performed. Where a limited number of calculations are involved, the calculation may be carried out to 16 significant digits and results displayed to 12 digits. However, where billions of calculations are performed, this may be insufficient. It is also known that single non linear model sof physical systems create such problems and may appear to be chaotic, thereby limiting the ability to forecast.
Current State-of-the-Art
Review of Current Floating Point Computer Arithmetic
The mathematical foundation of computer arithmetic is Boolean algebra. This is a self-consistent set of rules specifying the results (or mappings) of logical operations on bits. A bit is the basic unit of computation having values of 0 or 1 (i.e, true or false). The rules are often implemented, or regarded, as logical truth tables. These operations also have corresponding counterparts in the mathematical theory of sets (e.g., union corresponding to + and intersection corresponding to *). Such operations include negation and basic arithmetic (addition, subtraction, multiplication, division).
From that foundation, many approaches evolved to perform calculations on groups of bits, in the form of real numbers. A real number is either rational, expressible as a fraction, or irrational. And a real number is represented in a computer as a sequence of 0/1 bits. Many algorithms are used to perform the calculations or computations on these blocks of bits.
Out of the many arithmetic techniques that evolved over the years, floating point arithmetic emerged as the clear winner. Therefore, this presentation will focus exclusively on floating point computations as the benchmark from which to measure the merits of the D Arithmetic. The integer arithmetic will also be mentioned because of its frequent use in real-time calculations.
A floating point number is conveniently expressed in scientific notation, having three components. They are the sign, the mantissa, and the power [not correct term]. Or, in the usual base
10
notation:
x
=0
.n
1
. . .
ns
*10
s
s indicates the number of significant digits. A significant digit is one that has physical significance because it was actually measured during sampling.
Over the years, standard packaging of real numbers evolved to improve computational efficiency. These special packaging are referred to as “data types”.
There is also an “infinite precision” number which uses so many bits to represent a real number, that the precision is effectively “infinite”. Then the round-off errors effectively disappear, to provide the truest representation of multiple calculations on measured numbers. Until recent advances in computer CPU processing speed and memory capacity/price, it was not commercially feasible to work with infinite precision numbers. They require much more memory and processing time to implement, vis-a-vis the native data types.
Over time, the native data types were considered the golden compromise between the conflicting constraints of calculation efficiency vs. accuracy. But infinite precision numbers were increasingly used for more exacting calculations in scientific and even in financial applications. Indeed, packaging of indefinite and otherwise custom precision numbers is occurring more frequently. For example, the Java language packaged an infinite precision arithmetic in its Big Decimal object. Another commercial example is the packaging of a Money object to precisely handle arithmetic on currency sub-units (like cents).
Infinite precision arithmetic also serves as a useful benchmark against which the other restricted precision calculations can be compared. Because the infinite precision calculations do not have inherent rounding errors, they provide true values.
The following floating point representation will be used to show how the current standard floating point arithmetic can destabilize. A “double” data type is indicated, resulting from n calculations. In scientific notation, it is:
0
.n
1
. . . n
s
. . . n
b
. . . n
c
*10
s
Here, s again indicates the number of significant digits maintained from the actual original data measured. The first s digits are significant. The digits from s+1 until b are the buffer zone that will absorb the effect of round-off, errors. This buffer, in effect, shields the significant digits from the ripple effect of round-off. The digits from b+1 until c are the digits already corrupted by the rippling effect of previous round-off operations.
Note that the round-off error is generally indeterminate, and not calculable to a definite value. That increases, yet further, the uncertainty in the resultant calculations.
Numerical Instability of Floating Point Calculations
One problem is the inherent instability of the arithmetic due to the ever presence of rounding errors. Indeed, it does not even obey the basic laws of algebra, such as the associative law. That is, if A, B, C are floating point representations of real numbers, then it is not guaranteed that (A*B)*C=A*(B*C). These rounding errors accumulate until the significant digits are corrupted by the rippling round-off errors. Thus, the floating point arithmetic can only be useful for repeated calculations on a limited number of sample points, after which instability sets in.
The numerical stability can be vividly illustrated by following these two sets of (* or +) calculations on the same sequence of real numbers. Each number is expressed in scientific notation, with the significant, buffer and corrupted (or rounded) digits indicated, as described in the previous section.
The first set of calculations is performed on the standard “double” representation. And the second set is performed on the infinite precision representation. The second sequence serves as a genuine benchmark against which the double precision calculations are compared, because it does not have inherent rounding errors.
Both traces start with the same digit, having s
1
significant digits and a buffer of b
1
digits. The first case already starts with a corrupted digit because of the round-off at its end. The second number does not have a round-off error because of its infinite precision.
Standard type (double) “Infinite” Precision
0.
n
l1
…
n
s1
…
n
b1
…
n
c1
*
10
s
*
/
+
*
/
+
0.
n
lk
…
n
sk
…
n
bk
…
n
ck
*
10
s
0.
n
l1
…
n
s1
…
n
b1
…
*
10
s
*
/
+
,
*
/
+
,
0.
n
lk
…
n
sk
…
n
bk
…
*
10
s
Note at this point, that the buffer digits have become corrupted in the first case.
Subsequent calculations will corrupt the significant digits.
0.
n
lr
…
n
sr
…
n
cr
*
10
s
*
/
+
*
/
+
0.
n
l
m
…
n
c
m
…
*
10
s
0.
n
lr
…
n
sr
…
&emsp
Gottlieb Rackman & Reisman P.C.
Ngo Chuong Dinh
LandOfFree
Self-stabilizing, portable and efficient computer arithmetic... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Self-stabilizing, portable and efficient computer arithmetic..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Self-stabilizing, portable and efficient computer arithmetic... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3305899