Symmetrische Level-Index-Arithmetik - Symmetric level-index arithmetic

Die Level-Index- Darstellung ( LI ) von Zahlen und ihre Algorithmen für arithmetische Operationen wurden 1984 von Charles Clenshaw und Frank Olver eingeführt .

Die symmetrische Form des LI-Systems und seine arithmetischen Operationen wurden 1987 von Clenshaw und Peter Turner vorgestellt.

Michael Anuta, Daniel Lozier, Nicolas Schabanel und Turner entwickelten den Algorithmus für symmetrische Level-Index ( SLI ) Arithmetik und eine parallele Implementierung davon. Es wurden umfangreiche Arbeiten an der Entwicklung der SLI-Rechenalgorithmen und deren Erweiterung auf komplexe und vektorielle Rechenoperationen durchgeführt.

Definition

Die Idee des Level-Index-Systems besteht darin, eine nicht-negative reelle Zahl X als

${\displaystyle X=e^{e^{e^{\cdots^{e^{f}}}}}}$

wobei und der Prozess der Exponentiation ℓ mal durchgeführt wird, mit . l und f sind die Pegel und Index von X ist. x = ℓ + f ist das LI-Bild von X . Beispielsweise, ${\displaystyle 0\leq f<1}$${\displaystyle \ell \geq 0}$

${\displaystyle X=1234567=e^{e^{e^{0,9711308}}}}$

also ist sein LI-Bild

${\displaystyle x=\ell+f=3+0,9711308=3,9711308.}$

Die symmetrische Form wird verwendet, um negative Exponenten zuzulassen, wenn der Betrag von X kleiner als 1 ist. Man nimmt sgn (log( X )) oder sgn(| X | − | X | ⁻¹ ) und speichert es (nach Einsetzen von +1 für 0 für das Kehrwertzeichen, denn für X  = 1 =  e ^{0 ist} das LI-Bild x  = 1.0 und definiert X =1 eindeutig und wir können auf einen dritten Zustand verzichten und nur ein Bit für die beiden Zustände −1 und +1 . verwenden ) als Kehrwert r _X . Mathematisch ist dies gleichbedeutend damit, den Kehrwert (multiplikativ invers) einer kleinen Zahl zu nehmen und dann das SLI-Bild für den Kehrwert zu finden. Die Verwendung eines Bits für das Kehrwertzeichen ermöglicht die Darstellung extrem kleiner Zahlen.

Ein Vorzeichenbit kann auch verwendet werden, um negative Zahlen zuzulassen. Man nimmt sgn (X) und speichert es (nach dem Ersetzen von +1 für 0 für das Vorzeichen, da für X  = 0 das LI-Bild x  = 0.0 ist und X  = 0 eindeutig definiert und wir auf einen dritten Zustand verzichten und nur einen verwenden können Bit für die beiden Zustände −1 und +1) als Vorzeichen s _X . Mathematisch ist dies gleichbedeutend damit, die Umkehrung (additive Umkehrung) einer negativen Zahl zu nehmen und dann das SLI-Bild für die Umkehrung zu finden. Die Verwendung eines Bits für das Vorzeichen ermöglicht die Darstellung negativer Zahlen.

Die Abbildungsfunktion wird als verallgemeinerte Logarithmusfunktion bezeichnet . Es ist definiert als

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

und es bildet sich monoton auf sich selbst ab und ist daher auf diesem Intervall invertierbar. Die Umkehrung, die verallgemeinerte Exponentialfunktion , ist definiert durch ${\displaystyle [0,\infty )}$

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

Die Dichte der Werte X, die durch x dargestellt wird, weist keine Diskontinuitäten auf, wenn wir vom Niveau ℓ zu ℓ  + 1 gehen (eine sehr wünschenswerte Eigenschaft), denn

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

Die verallgemeinerte Logarithmusfunktion ist eng verwandt mit dem iterierten Logarithmus, der in der Informatikanalyse von Algorithmen verwendet wird.

Formal können wir die SLI-Darstellung für ein beliebiges reelles X (nicht 0 oder 1) definieren als

${\displaystyle X=s_{X}\varphi(x)^{r_{X}}}$

wobei s _X das Vorzeichen (additive Inversion oder nicht) von X ist und r _X das reziproke Vorzeichen (multiplikative Inversion oder nicht) wie in den folgenden Gleichungen ist:

${\displaystyle s_{X}=\operatorname {sgn}(X),\,r_{X}=\operatorname {sgn}(|X|-|X|^{-1}),\,x=\psi (\max(|X|,|X|^{-1}))=\psi (|X|^{r_{X}})}$

wohingegen für X = 0 oder 1 gilt:

${\displaystyle s_{0}=+1,r_{0}=+1,x=0.0,\,}$

${\displaystyle s_{1}=+1,r_{1}=+1,x=1.0.\,}$

Beispielsweise,

${\displaystyle X=-{\dfrac {1}{1234567}}=-e^{-e^{e^{0,9711308}}}}$

und seine SLI-Darstellung ist

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

Siehe auch

• Tetration
• Gleitkomma (FP)
• Tapered Floating Point (TFP)
• Logarithmisches Zahlensystem (LNS)
• Füllstand (logarithmische Größe)

Verweise

Weiterlesen

• Clenshaw, Charles William; Olver, Frank William John ; Turner, Peter R. (1989). "Niveau-Index-Arithmetik: Eine einführende Umfrage". Numerical Analysis and Parallel Processing (Konferenzbericht / The Lancaster Numerical Analysis Summer School 1987). Vorlesungsnotizen in Mathematik (LNM). 1397 : 95–168. doi : 10.1007/BFb0085718 .
• Clenshaw, Charles William; Turner, Peter R. (1989-06-23) [1988-10-04]. "Root Squaring Using Level-Index Arithmetic". Computer . Springer-Verlag . 43 (2): 171–185. ISSN  0010-485X .
• Zehendner, Eberhard (Sommer 2008). "Rechnerarithmetik: Logarithmische Zahlensysteme" (PDF) (Skript zur Vorlesung). Friedrich-Schiller-Universität Jena . S. 21–22. Archiviert (PDF) vom Original am 09.07.2018 . Abgerufen 2018-07-09 . [1]
• Hayes, Brian (September–Oktober 2009). „Die höhere Arithmetik“ . Amerikanischer Wissenschaftler . 97 (5): 364–368. doi : 10.1511/2009.80.364 . Archiviert vom Original am 2018-07-09 . Abgerufen 2018-07-09 . [2] . Auch abgedruckt in: Hayes, Brian (2017). "Kapitel 8: Höhere Arithmetik". Narrensichere und andere mathematische Meditationen (1 Hrsg.). Die MIT-Presse . S. 113–126. ISBN 978-0-26203686-3. ISBN  0-26203686-X .

Externe Links

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