Browse Prior Art Database

Multiple Rounding Tables for Multiple Error Sources

IP.com Disclosure Number: IPCOM000115290D
Original Publication Date: 1995-Apr-01
Included in the Prior Art Database: 2005-Mar-30
Document File: 4 page(s) / 120K

IBM

Related People

Schwarz, EM: AUTHOR

Abstract

The hardware design of a complex control circuit for selective rounding is disclosed. A high precision value can be transformed into a lower precision value by either incrementing or truncating the value. The general transformation between precisions is called rounding, and is sometimes controlled by a rounding table. The sign of the value and any extra bits of precision provide information to index into a rounding table which then dictates the action to perform to create the low precision value, increment or truncate. In algorithms for high-order arithmetic operations, such as the square root operation, the range of error can vary each iteration due to different error sources and/or iteration dependent error. A method for skewing the error range in a system which has multiple error sources is disclosed.

This text was extracted from an ASCII text file.
This is the abbreviated version, containing approximately 52% of the total text.

Multiple Rounding Tables for Multiple Error Sources

The hardware design of a complex control circuit for selective
rounding is disclosed.  A high precision value can be transformed
into a lower precision value by either incrementing or truncating the
value.  The general transformation between precisions is called
rounding, and is sometimes controlled by a rounding table.  The sign
of the value and any extra bits of precision provide information to
index into a rounding table which then dictates the action to perform
to create the low precision value, increment or truncate.  In
algorithms for high-order arithmetic operations, such as the square
root operation, the range of error can vary each iteration due to
different error sources and/or iteration dependent error.  A method
for skewing the error range in a system which has multiple error
sources is disclosed.  The method uses multiple rounding tables which
are chosen based on the iteration.

An example of an algorithm which can use this scheme
effectively is a particular square root algorithm.  The algorithm
follows the steps shown below where Q(i) represents the accumulated
root, REM(i)  the remainder, NREM(i)  the normalized remainder, X the
input operand, CONV the convergence factor.  Let CONV approx.  equals
1/(2* SQRT(X)), Q(1) = 0, REM(1) = X, q(1) = round( truncate(2X) *
CONV).
For i > 1:
1.  Q(i) = Q(i-1)  + q(i-1)
2.  REM(i)  = REM(i-1) - q(i-1)* (2Q(i-1) + q(i-1))
3.  q(i) = round( truncate(REM(i)) * CONV)

The only step which introduces error into the calculation is
the step which determines the next incremental root.  The normalized
version of this step can be expressed by Equation 1: nq(i) = round(
truncate(NREM(i)) * CONV).  "k" bits are calculated each iteration
with an error bounded by + or - 2(-k).

There are four sources of error in this calculation:  1) Error
in the formula, 2) Error due to truncating the remainder (NREM(i)),
3) Error in the convergence factor (CONV), and 4) Error due rounding
the exact product to a lower precision (k bits).  The second and the
third source produce an error which behaves constantly per iteration
(the bounds remain the same).  The first source is dominant in the
second iteration and decreases each iteration.  It is due to Equation
1 being inexact and it can be described by the following formula:
error = (Q(i) - SQRT(X))(2) / (2* SQRT(X)).  This type of error is
quadratic and is very significant (between -2(-k)  and 0) in the
second iteration and diminishes significantly (magnitude of error is
less than or equal to 2(-2k)) in the remaining iterations.  The
fourth source of error, rounding, can actually be used to reduce the
maximum error by skewing the r...