Symmetric level-index arithmetic

From Wikipedia, the free encyclopedia

 This article does not cite any references or sources. (March 2008)
Please help improve this article by adding citations to reliable sources. Unverifiable material may be challenged and removed.

The level-index (LI) representation of numbers, and its algorithms 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.

[edit] Definition

The idea of the level-index system is to represent a positive real number X as

           X=e^{e^{e^{...^{e^{f}}}}}

where 0\leq f<1 and the process of exponentiation is performed l times. l and f are the level and index of X respectively. X = l + f is the LI image of X. For an instance,

           X=1234567=e^{e^{e^{0.9711308}}}

so its LI image is

           x = l + f = 3 + 0.9711308 = 3.9711308

The symmetric form is used to allow negative exponents, if the magnitude of X is less than 1. One takes the logarithm of X and store its sign as the reciprocal sign. Mathematically, this is equivalent to taking the reciprocal 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, while a sign bit allows negative numbers.

The mapping function is called the generalized logarithm function. It is defined as

           \psi (X)= \left\{\begin{matrix}
X & \mathrm{if} \quad 0 \leq X<1 \\
1+ \psi (\ln X) & \mathrm{if} \quad X \geq 1
\end{matrix} \right.

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

           \phi (x)= \left\{\begin{matrix}
x & \mathrm{if} \quad 0\leq x<1 \\
e^{\phi (x-1)} & \mathrm{if} \quad x\geq 1
\end{matrix} \right.

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 nonzero X as

           X=s_{X}\phi (x)^{r_{X}}

where sX is the sign and rX is the reciprocal sign as in the following equations.

           x=\psi (\max (|X|,|X|^{-1}))=\psi (|X|^{r_{X}}),s_{X}=\text{sign}(X)

For example,

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

and its SLI representation is

           X =  − φ(3.9711308) − 1