Electrical computers: arithmetic processing and calculating – Electrical digital calculating computer – Particular function performed
Reexamination Certificate
2000-11-13
2004-03-23
Malzahn, David H. (Department: 2124)
Electrical computers: arithmetic processing and calculating
Electrical digital calculating computer
Particular function performed
Reexamination Certificate
active
06711596
ABSTRACT:
The present invention relates to a logarithmic calculating apparatus and method, and relates particularly, but not exclusively, to a logarithmic calculating apparatus and method to be incorporated within microprocessors.
In electronic computational machines, it is known to represent real numbers upon which the machines operate using the “floating point” system, which will be familiar to persons skilled in the art. Using the “floating point” system, add, subtract and multiply operations can be exercised at reasonable speed. However, this system suffers from the drawback that divide operations take place much more slowly, and all operations are subject to a maximum rounding error of half of a least significant bit.
An alternative known approach is to represent real numbers as fixed-point logarithms, this approach generally being referred to as a Logarithmic Number System (LNS). Using such a system, multiplication and division operations may be implemented very rapidly and with no error, but this is at the expense of considerable complexity, latency and lack of accuracy in the addition and subtraction processes.
The operation of a conventional Logarithmic Number System, such as in existing arithmetic devices, is shown schematically in
FIG. 1
, in which addition and subtraction operations require the evaluation of:
log
2
(2
i
+2
j
)=
i
+log
2
(1+2
j−i
);
log
2
(2
i
−2
j
)=
i
+log
2
(1−2
j−i
);
where j is less than or equal to i.
The logarithmic function F(r=(j−i))=log
2
(1+2
j−i
) for the add operation is shown in FIG.
2
. The device shown in
FIG. 1
is provided with look up tables which store the value of the function F(r) for a range of discrete values of r. For practical applications, it is not possible to store the function for all values of r, as this would require a look up table of impracticable size, and so the value of the function is therefore stored at intervals of width &Dgr;. To further minimise the storage requirements, &Dgr; is progressively increased as the function becomes more linear with decreasing r, and an intervening value of r lying in the nth interval is thus expressed as:
r=−&dgr;{n=O}; r
=&Sgr;(−&Dgr;
n
)−&dgr;{
n
>0}
For clarity, however, this description omits any further reference to the variation in &Dgr;, and the expression may be abbreviated to r=−n&Dgr;−&dgr;.
Alongside each value of the function F(r) is stored its derivative, or slope at that point, D(r). The function for any intermediate value of r is then obtained by interpolation with a first-order Taylor-series:
F
(−
n
&Dgr;−&dgr;)=
F
(−
n
&Dgr;)−&dgr;
D
(−
n
&Dgr;)
FIG. 3
shows in detail the function F(r) within one interval of width &Dgr;. The error &egr; between the true value of the Function F(r) at position &dgr; and that interpolated from the derivative at an adjacent stored position is shown. Referring to
FIG. 1
, the apparatus has a selector/subtracter
1
for deriving the values of i and r=j−i, a look up table
2
containing the value of the function F(r) at discrete values of r, and a look up table
3
containing values of the derivative D(r) at discrete values of r. A multiply stage
4
multiplies the derivative D(r) by &dgr; and a carry-save-add stage
5
adds together the outputs of the selector/subtracter
1
, look up table
2
and multiplier
4
. The output of the carry-save-add stage
5
is then fed to a carry-propagate-add stage
6
.
It can therefore be seen that following the initial subtraction in selector/subtracter
1
to obtain r, r is partitioned into lower and higher order segments, so effectively dividing by &Dgr;. The higher order segment represents n and is used to access the function F(r) in look up table
2
and derivative D(r) in look up table
3
, whilst the lower order segment represents &dgr;. F(−n&Dgr;) stored in look up table
2
is then added in the carry-save-add stage
5
to the product &dgr;.D(−n&Dgr;) obtained from the multiplier
4
, so as to obtain the approximation to F(r) at the value of r of interest, to which is also added i, the addition being completed in the final carry-propagate-add stage
6
, so as to yield the result.
As can be seen from
FIG. 3
, the prior art arrangement described with reference to
FIGS. 1
to
3
includes an interpolation error:
&egr;(
n
,&dgr;)=
F
(−
n
&Dgr;)−&dgr;.
D
(−
n
&Dgr;)−
F
(−
n
&Dgr;−&dgr;)
and for each n, &egr; increases with &dgr; to a maximum:
E
(
n
)=
F
(−
n
&Dgr;)−&Dgr;.
D
(−
n
&Dgr;)−
F
(−
n
&Dgr;−&Dgr;) approximately.
In any practical implementation, the error &egr; must be minimised to an acceptable magnitude. This can be achieved by decreasing the increment &Dgr;, but at the cost of a considerable increase in the required capacity of the look up tables. Alternatively, methods are known which apply correction algorithms to minimise the error without increasing the necessary capacity of the look up tables. However, these all suffer from the drawback that they involve many extra stages in the computation process, which are executed serially, and therefore introduce speed limitations.
Preferred embodiments of the present invention seek to overcome the above disadvantages of the prior art.
According to an aspect of the present invention, there is provided a logarithmic calculating apparatus for determining the approximate value of a logarithmic function F(x) at a value of x of interest, the apparatus comprising:
first memory means for storing values of the function F(x) for a plurality of discrete values of x;
second memory means for storing values of F′(x), the slope of the function F(x), for said plurality of discrete values of x;
first multiplier means, or equivalent thereof, for multiplying the value of F′(x) for a said discrete value of x adjacent to the value of x of interest by &dgr;, the difference between said adjacent discrete value of x and the value of x of interest;
third memory means for storing values of E (x), the approximate difference between [F(x)+&Dgr;.F′(x)] and F(x+&Dgr;) where x and x+&Dgr; are the adjacent pair of said discrete values of x nearest to the value of x of interest;
fourth memory means for storing values of P(&dgr;), the ratio of (i) the difference between F(x+&dgr;) and [F(x)+&dgr;.F′(x)], to (ii) E(x) for a plurality of values of &dgr;;
second multiplier means, or equivalent thereof, for multiplying together the outputs of said third and fourth memory means; and
adder means for adding together the outputs of said first memory means, said first multiplier means and said second multiplier means to produce an output representing the approximate value of F(x) at the value of x of interest.
The present invention is based on the surprising observation that for many logarithmic functions, the ratio function P(&dgr;) for a given value of &dgr; is almost, although not exactly, constant for all values of n. This provides the advantage that it is possible to store for a single value of n a look up table containing the values of P(&dgr;) at successive points throughout an interval of width &Dgr;. This in turn provides the advantage of enabling the logarithmic function F(x) to be calculated accurately for a value of x of interest without significantly increasing the necessary size of look up tables in the apparatus, and without significantly decreasing the speed of calculation. For example, the necessary size of look up tables may be doubled compared with the prior art, which does not cause significant problems. It will also be appreciated by persons skilled in the art that the quantities x, F(x), F′(x),&dgr;, E(x) and &Dgr; defined above can be positive or negative.
In a preferred embodiment, said first and second multiplier means operate substantially simultaneously in use.
This provides t
Malzahn David H.
Schein, Esq. Daniel B.
University of Newcastle Upon Tyne
LandOfFree
Method and apparatus for determining the approximate valve... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and apparatus for determining the approximate valve..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for determining the approximate valve... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3202501