Symmetric level-index arithmetic
Encyclopedia
The level-index representation of numbers, and its algorithm
s for arithmetic operations, were introduced by Clenshaw & Olver. The symmetric form of the LI system and its arithmetic operations were presented by Clenshaw & Turner. Anuta, Lozier, Schabanel and Turner developed the algorithm for symmetric level-index (SLI) arithmetic, and a parallel implementation of it. There has been extensive work on developing the SLI arithmetic algorithms and extending them to complex and vector arithmetic operations.
where
and the process of exponentiation is performed l times, with 
. l and f are the level and index of X respectively. x = l + f is the LI image of X. For example,
so its LI image is
.
The symmetric form is used to allow negative exponents, if the magnitude of X is less than 1. One takes sgn
(log(X)) or sgn
(|X|-|X|-1) and stores it (after substituting +1 for 0 for the reciprocal sign since for X=1=e0 the LI image is x=1.0 and uniquely defines X=1 and we can do away without a third state and use only 1 bit for the 2 states -1 and +1) as the reciprocal sign rX. Mathematically, this is equivalent to taking the reciprocal (multiplicative inverse) of a small magnitude number, and then finding the SLI image for the reciprocal. Using one bit for the reciprocal sign enables the representation of extremely small numbers.
A sign bit may also be used to allow negative numbers. One takes sgn
(X) and stores it (after substituting +1 for 0 for the sign since for X=0 the LI image is x=0.0 and uniquely defines X=0 and we can do away without a third state and use only 1 bit for the 2 states -1 and +1) as the sign sX. Mathematically, this is equivalent to taking the inverse (additive inverse) of a negative number, and then finding the SLI image for the inverse. Using one bit for the sign enables the representation of negative numbers.
The mapping function is called the generalized logarithm function. It is defined as
and it maps
onto itself monotonically and so it is invertible on this interval. The inverse, the generalized exponential function, is defined by
The density of values X represented by x has no discontinuities as we go from level l to l+1 (a very desirable property) since:
.
The generalized logarithm function is closely related to the iterated logarithm
used in computer science analysis of algorithms.
Formally, we can define the SLI representation for an arbitrary real X (not 0 or 1) as
where sX is the sign (additive inversion or not) of X and rX is the reciprocal sign (multiplicative inversion or not) as in the following equations:
whereas for X=0 or 1, we have:
,
.
For example,
and its SLI representation is
.
C. W. Clenshaw, F. W. J. Olver and P. R. Turner, "Level-index arithmetic: An introductory survey".
sli-c-library (hosted by Google Code), "C++ Implementation of Symmetric Level-Index Arithmetic".
Algorithm
In mathematics and computer science, an algorithm is an effective method expressed as a finite list of well-defined instructions for calculating a function. Algorithms are used for calculation, data processing, and automated reasoning...
s for arithmetic operations, were introduced by Clenshaw & Olver. The symmetric form of the LI system and its arithmetic operations were presented by Clenshaw & Turner. Anuta, Lozier, Schabanel and Turner developed the algorithm for symmetric level-index (SLI) arithmetic, and a parallel implementation of it. There has been extensive work on developing the SLI arithmetic algorithms and extending them to complex and vector arithmetic operations.
Definition
The idea of the level-index system is to represent a non-negative real number X aswhere
and the process of exponentiation is performed l times, with . l and f are the level and index of X respectively. x = l + f is the LI image of X. For example,so its LI image is
.The symmetric form is used to allow negative exponents, if the magnitude of X is less than 1. One takes sgn
Sign function
In mathematics, the sign function is an odd mathematical function that extracts the sign of a real number. To avoid confusion with the sine function, this function is often called the signum function ....
(log(X)) or sgn
Sign function
In mathematics, the sign function is an odd mathematical function that extracts the sign of a real number. To avoid confusion with the sine function, this function is often called the signum function ....
(|X|-|X|-1) and stores it (after substituting +1 for 0 for the reciprocal sign since for X=1=e0 the LI image is x=1.0 and uniquely defines X=1 and we can do away without a third state and use only 1 bit for the 2 states -1 and +1) as the reciprocal sign rX. Mathematically, this is equivalent to taking the reciprocal (multiplicative inverse) of a small magnitude number, and then finding the SLI image for the reciprocal. Using one bit for the reciprocal sign enables the representation of extremely small numbers.
A sign bit may also be used to allow negative numbers. One takes sgn
Sign function
In mathematics, the sign function is an odd mathematical function that extracts the sign of a real number. To avoid confusion with the sine function, this function is often called the signum function ....
(X) and stores it (after substituting +1 for 0 for the sign since for X=0 the LI image is x=0.0 and uniquely defines X=0 and we can do away without a third state and use only 1 bit for the 2 states -1 and +1) as the sign sX. Mathematically, this is equivalent to taking the inverse (additive inverse) of a negative number, and then finding the SLI image for the inverse. Using one bit for the sign enables the representation of negative numbers.
The mapping function is called the generalized logarithm function. It is defined as
and it maps
onto itself monotonically and so it is invertible on this interval. The inverse, the generalized exponential function, is defined byThe density of values X represented by x has no discontinuities as we go from level l to l+1 (a very desirable property) since:
.The generalized logarithm function is closely related to the iterated logarithm
Iterated logarithm
In computer science, the iterated logarithm of n, written n , is the number of times the logarithm function must be iteratively applied before the result is less than or equal to 1...
used in computer science analysis of algorithms.
Formally, we can define the SLI representation for an arbitrary real X (not 0 or 1) as
where sX is the sign (additive inversion or not) of X and rX is the reciprocal sign (multiplicative inversion or not) as in the following equations:
whereas for X=0 or 1, we have:
,.For example,
and its SLI representation is
.C. W. Clenshaw, F. W. J. Olver and P. R. Turner, "Level-index arithmetic: An introductory survey".
sli-c-library (hosted by Google Code), "C++ Implementation of Symmetric Level-Index Arithmetic".