Symmetric level-index arithmetic

Template:Short description Template:Use dmy dates 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 Template:Mvar as

$X=e^{e^{e^{{\cdot }^{{\cdot }^{{\cdot }^{e^f}}}}}},$

where $0\le f<1$, and the process of exponentiation is performed Template:Mvar times, with $\ell \ge 0$. Template:Mvar and Template:Mvar are the level and index of Template:Mvar respectively. Template:Math is the LI image of Template:Mvar. For example,

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

so its LI image is

$x=\ell +f=3+0.9711308=\mathrm{3.9711308.}$

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

$\psi (X)=\{\begin{array}{cc}X& \text{if }0\le X<1,\\ 1+\psi (\ln X)& \text{if }X\ge 1,\end{array}$

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

$\phi (x)=\{\begin{array}{cc}x& \text{if }0\le x<1,\\ e^{\phi (x-1)}& \text{if }x\ge 1.\end{array}$

The density of values Template:Mvar represented by Template:Mvar has no discontinuities as we go from level Template:Mvar to Template:Math (a very desirable property) since

${\frac{d\phi (x)}{dx}|}_{x=1}={\frac{d\phi (e^x)}{dx}|}_{x=0}.$

The generalized logarithm function is closely related to the iterated logarithm used in computer science analysis of algorithms.

A sign bit may also be used to allow negative numbers. One takes sgn(X) and stores it as a boolean Template:Mvar (0 only occurs when Template:Math so could be stored either way, +1 chosen here). Mathematically, this is equivalent to taking the negative (additive inverse) of a number, and finding the SLI image for that. Using one bit for the sign enables the representation of negative numbers.

The symmetric form is used to allow negative exponents, if the magnitude of Template:Mvar is less than 1. One takes Template:Math or Template:Math and stores it as a boolean Template:Mvar (0 only occurs when Template:Math so could be stored either way, +1 chosen here). Mathematically, this is equivalent to taking the reciprocal (multiplicative inverse) of a small-magnitude number, and finding the SLI image for that. Using one bit for the reciprocal sign enables the representation of extremely small numbers.

Formally, we can define the SLI representation for an arbitrary real Template:Mvar (not 0 or 1) as

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

where Template:Mvar is the sign (additive inversion or not) of Template:Mvar, and Template:Mvar is the reciprocal sign (multiplicative inversion or not) as in the following equations:

$s_X=\mathrm{sgn}(X),r_X=\mathrm{sgn}(|X|-|X{|}^{-1}),x=\psi (max(|X|,|X{|}^{-1}\left)\right)=\psi \left(s_X{X}^{r_X}\right),$

whereas for Template:Mvar = 0 or 1, we have

$s_0=+1,r_0=+1,x=0.0,$

$s_1=+1,r_1=+1,x=\mathrm{1.0.}$

For example,

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

and its SLI representation is

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

Adding

Most arithmetic operations in LI can be easily reduced to addition due to the nature of logarithms. If we have some Template:Mvar, Template:Mvar, and Template:Mvar related by $\phi (z)=\phi (x{)}^{\phi (y)}$, taking the logarithm of both sides gives us $\phi (z-1)=\phi (y)\phi (x-1)$, and once more gives us $\phi (z-2)=\phi (y-1)+\phi (x-2)$. The only non-trivial operation left to define is addition.

The problem of addition is posed as being able to find some Template:Mvar, given an arbitrary Template:Mvar and Template:Mvar with $\phi (x)\ge \phi (y)$, such that $\phi (x)+\phi (y)=\phi (z)$. We also say that the levels of $\phi (x)$, $\phi (y)$, and $\phi (z)$ are Template:Mvar, Template:Mvar, and Template:Mvar, and their indices are Template:Mvar, Template:Mvar, and Template:Mvar. It is helpful to define these 3 sequences, each indexed with some Template:Mvar:

$\begin{array}{cc}& a_j=\frac{1}{\phi (x-j)}j=l-1,l-2,\mathrm{...},0\\ & b_j=\frac{\phi (y-j)}{\phi (x-j)}j=m-1,m-2,\mathrm{...},0\\ & c_j=\frac{\phi (z-j)}{\phi (x-j)}j=0,1,\mathrm{...}\end{array}$

With this defined, we can now state that Template:Mvar is equal to $j+\frac{c_j}{a_j}$ for the smallest Template:Mvar where $c_j<a_j$. To find the actual values in these sequences, we use a set of recursive definitions each with an initial condition:

$\begin{array}{cccc}{a}_{j-1}& =e^{-\frac{1}{a_j}}& a_{l-1}& =e^{-f}\\ b_{j-1}& =e^{-\frac{1-b_j}{a_j}}& b_{m-1}& =a_{m-1}{e}^g\\ c_j& =1+a_j\ln (c_{j-1})& c_0& =1+b_0\end{array}$

This can also be used to implement subtraction by changing the initial condition for Template:Mvar to be $c_0=1-b_0$.

When using SLI, $\phi (x)+\phi (y)=\phi (z)$ is not the only case; $\phi (x)+{}^1/{}_{\phi (y)}=\phi (z)$ and ${}^1/{}_{\phi (x)}+{}^1/{}_{\phi (y)}={}^1/{}_{\phi (z)}$ should also be considered; typically called "large", "mixed", and "small" arithmetic. In mixed arithmetic, we replace the Template:Mvar sequence with ${\alpha }_j={}^1/{}_{\phi (y-j)}$ and define $c_0$ as $c_0=1+a_0{\alpha }_0$; and in small arithmetic we replace the Template:Mvar sequence with ${\beta }_j={}^{\phi (x-j)}/{}_{\phi (y-j)}$, and $c_0$ becomes $c_0={}^1/{}_{1+{\beta }_0}$

See also

• Tetration
• Floating point (FP)
• Tapered floating point (TFP)
• Logarithmic number system (LNS)
• Level (logarithmic quantity)

Further reading

• Template:Cite journal
• Template:Cite journal
• Template:Cite web [1]
• Template:Cite journal [2]. Also reprinted in: Template:Cite book

External links

• sli-c-library (hosted by Google Code), "C++ Implementation of Symmetric Level-Index Arithmetic".