symmetric level-index arithmetic

The level-index (LI) representation of numbers, and its algorithms for arithmetic operations, were introduced by Charles Clenshaw and Frank Olver in 1984.

The symmetric form of the LI system and its arithmetic operations were presented by Clenshaw and Peter Turner in 1987.

Michael Anuta, Daniel Lozier, Nicolas 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 {{mvar|X}} as

: $X = e^{e^{e^{\cdots^{e^f}}}},$

where $0 \leq f < 1$ , and the process of exponentiation is performed {{mvar|ℓ}} times, with $\ell \geq 0$ . {{mvar|ℓ}} and {{mvar|f}} are the level and index of {{mvar|X}} respectively. {{math|1=x = ℓ + f}} is the LI image of {{mvar|X}}. For example,

: $X = 1234567 = e^{e^{e^{0.9711308}}},$

so its LI image is

: $x = \ell + f = 3 + 0.9711308 = 3.9711308.$

The symmetric form is used to allow negative exponents, if the magnitude of {{mvar|X}} is less than 1. One takes {{math|sgn(log(X))}} or {{math|sgn({{abs|X}} − {{abs|X}}⁻¹)}} and stores it (after substituting +1 for 0 for the reciprocal sign; since for {{math|1=X = 1 = e⁰}} the LI image is {{math|1=x = 1.0}} and uniquely defines {{math|1=X = 1}}, we can do away without a third state and use only one bit for the two states −1 and +1{{clarify |date=December 2023}}) as the reciprocal sign {{mvar|r_X}}. 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 {{math|1=X = 0}} the LI image is {{math|1=x = 0.0}} and uniquely defines {{math|1=X = 0}}, we can do away without a third state and use only one bit for the two states −1 and +1{{clarify |date=December 2023}}) as the sign {{mvar|s_X}}. 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

: $\psi(X) = \begin{cases}
X & \text{if } 0 \leq X < 1, \\
1 + \psi(\ln X) & \text{if } X \geq 1,
\end{cases}$

and it maps $[0, \infty )$ onto itself monotonically, thus being invertible on this interval. The inverse, the generalized exponential function, is defined by

: $\varphi(x) = \begin{cases}
x & \text{if } 0 \leq x < 1, \\
e^{\varphi(x-1)} & \text{if } x \geq 1.
\end{cases}$

The density of values {{mvar|X}} represented by {{mvar|x}} has no discontinuities as we go from level {{mvar|ℓ}} to {{math|ℓ + 1}} (a very desirable property) since

: $\left.\frac{d\varphi(x)}{dx}\right|_{x=1} = \left.\frac{d\varphi(e^x)}{dx}\right|_{x=0}.$

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 {{mvar|X}} (not 0 or 1) as

: $X = s_X\varphi(x)^{r_X},$

where {{mvar|s_X}} is the sign (additive inversion or not) of {{mvar|X}}, and {{mvar|r_X}} is the reciprocal sign (multiplicative inversion or not) as in the following equations:

: $s_X = \sgn(X),\quad
r_X = \sgn\big(|X| - |X|^{-1}\big),\quad
x = \psi\big(\max\big(|X|, |X|^{-1}\big)\big) = \psi\big(|X|^{r_X}\big),$

whereas for {{mvar|X}} = 0 or 1, we have

: $s_0 = +1,\quad r_0 = +1,\quad x = 0.0,$

: $s_1 = +1,\quad r_1 = +1,\quad x = 1.0.$

For example,

: $X = -\dfrac{1}{1234567} = -e^{-e^{e^{0.9711308}}},$

and its SLI representation is

: $x = -\varphi(3.9711308)^{-1}.$

References

{{Reflist|refs=

{{cite journal |author-first1=Charles William |author-last1=Clenshaw |author-first2=Frank William John |author-last2=Olver |author-link2=Frank William John Olver |title=Beyond floating point |journal=Journal of the ACM |volume=31 |issue=2 |pages=319–328 |date=1984 |doi=10.1145/62.322429|doi-access=free }}

{{cite journal |author-first1=Charles William |author-last1=Clenshaw |author-first2=Peter R. |author-last2=Turner |title=The Symmetric Level-Index System |journal=IMA Journal of Numerical Analysis |issn=0272-4979 |oclc=42026743 |publisher=Oxford University Press, Institute of Mathematics and Its Applications |volume=8 |issue=4 |pages=517–526 |date=1988-10-01 |orig-year=1986-09-16, 1987-06-04 |doi=10.1093/imanum/8.4.517 |url=https://www.researchgate.net/publication/31393487 |access-date=2018-07-10}}

}}

External links

sli-c-library (hosted by Google Code), [http://code.google.com/p/sli-c-library/ "C++ Implementation of Symmetric Level-Index Arithmetic"].

Category:Computer arithmetic

symmetric level-index arithmetic

Definition

See also

References

Further reading

External links