Symetryczna arytmetyka indeksu poziomu

Reprezentacja liczb z indeksem poziomu ( LI ) i jej algorytmy operacji arytmetycznych zostały wprowadzone przez Charlesa Clenshawa i Franka Olvera w 1984 roku.

Symetryczną postać systemu LI i jego operacje arytmetyczne przedstawili Clenshaw i Peter Turner w 1987 roku.

Michael Anuta, Daniel Lozier, Nicolas Schabanel i Turner opracowali algorytm arytmetyki symetrycznego indeksu poziomu ( SLI ) i jego równoległą implementację. Przeprowadzono wiele prac nad opracowaniem algorytmów arytmetycznych SLI i rozszerzeniem ich na złożone i wektorowe operacje arytmetyczne.

Definicja

Ideą systemu indeksów poziomów jest reprezentowanie nieujemnej liczby rzeczywistej $X$ jako

\ Displaystyle X = e ^ {e ^ {e ^ {\ cdots ^ {e ^ {f}}}}}}

gdzie ${\ Displaystyle 0 \ równoważnik f <1},$ a proces potęgowania jest wykonywany $ℓ$ razy, z ${\ Displaystyle \ ell \ geq 0}$ . $ℓ$ i $f$ to odpowiednio poziom i indeks X. $_$ $x = ℓ + f$ jest obrazem LI $X$ . Na przykład,

{\ Displaystyle X = 1234567 = e ^ {e ^ {e ^ {0,9711308}}}}

taki jest jego obraz LI

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

Postać symetryczna jest używana, aby umożliwić ujemne wykładniki, jeśli wielkość $X$ jest mniejsza niż 1. Bierze się $sgn (log(X))$ lub $sgn(| X | - | X | -1)$ i przechowuje (po podstawieniu +1 dla 0 dla znaku odwrotności, ponieważ dla $X = 1 = e 0$ obraz LI wynosi $x = 1,0$ i jednoznacznie definiuje $X = 1$ i możemy zrezygnować z trzeciego stanu i użyć tylko jednego bitu dla dwóch stanów −1 i +1) jako znak odwrotny $r X$ . Matematycznie jest to równoważne z obliczeniem odwrotności (odwrotności multiplikatywnej) liczby o małej wielkości, a następnie znalezieniem obrazu SLI dla odwrotności. Użycie jednego bitu jako znaku odwrotności umożliwia reprezentację bardzo małych liczb.

Bit znaku może być również użyty do zezwolenia na liczby ujemne. Bierze się sgn (X) i przechowuje (po podstawieniu znaku +1 za 0, ponieważ dla $X = 0$ obraz LI wynosi $x = 0.0$ i jednoznacznie definiuje $X = 0$ i możemy zrezygnować bez trzeciego stanu i użyć tylko jednego bit dla dwóch stanów −1 i +1) jako znak $s X$ . Matematycznie jest to równoważne z obliczeniem odwrotności (odwrotności addytywnej) liczby ujemnej, a następnie znalezieniem obrazu SLI dla odwrotności. Użycie jednego bitu na znak umożliwia reprezentację liczb ujemnych.

Funkcja odwzorowania nazywana jest uogólnioną funkcją logarytmiczną . Określa się jako

{\ Displaystyle \ psi (X) = {\ rozpocząć {przypadki} X & {\ tekst {jeśli}} 0 \ równoważnik X<1\\1+\psi (\ln X)&{\text{if }}X\geq 1\end{przypadki}}}

$,$ odwzorowuje na siebie monotonicznie więc jest odwracalny w Odwrotność, uogólniona funkcja wykładnicza , jest zdefiniowana przez

{\ Displaystyle \ varphi (x) = {\ rozpocząć {przypadki} x & {\ tekst {jeśli}} 0 \ równoważnik x <1\\e^{\varphi (x-1)}&{\text{if }}x\geq 1\end{przypadki}}}

Gęstość wartości $X$ reprezentowana przez $x$ nie ma nieciągłości, gdy przechodzimy od poziomu $ℓ$ do $ℓ + 1$ (właściwość bardzo pożądana), ponieważ:

{\ Displaystyle \ lewo. {\ Frac {d \ varphi (x)} {dx}} \ prawo | _ {x = 1} = \ lewo. {\ Frac {d \ varphi (e ^ {x})} dx}}\prawo|_{x=0}.}

Uogólniona funkcja logarytmu jest ściśle związana z logarytmem iterowanym używanym w informatycznej analizie algorytmów.

Formalnie możemy zdefiniować reprezentację SLI dla dowolnego rzeczywistego $X$ (nie 0 lub 1) jako

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

gdzie $s X$ jest znakiem (inwersja addytywna lub nie) $X ,$ a $r X$ jest znakiem odwrotności (inwersja multiplikatywna lub nie), jak w następujących równaniach:

{\ Displaystyle s_ {X} = \ nazwa operatora {sgn} (X), \, r_ {X} = \ nazwa operatora {sgn} (| X | - | X | ^ {-1}), \, x = \ psi (\max(|X|,|X|^{-1}))=\psi (|X|^{r_{X}})}

natomiast dla $X$ = 0 lub 1 mamy:

{\ Displaystyle s_ {0} = + 1, r_ {0} = + 1, x = 0,0 \,}

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

Na przykład,

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

a jego reprezentacja SLI to

{\ Displaystyle x = - \ varphi (3,9711308) ^ {- 1}.}

Zobacz też

Dalsza lektura

Clenshaw, Charles William; Olvera, Franka Williama Johna ; Turner, Peter R. (1989). „Arytmetyka indeksów poziomów: ankieta wprowadzająca”. Analiza numeryczna i przetwarzanie równoległe (materiały konferencyjne / The Lancaster Numerical Analysis Summer School 1987). Notatki z wykładów z matematyki (LNM). 1397 : 95–168. doi : 10.1007/BFb0085718 .
Clenshaw, Charles William; Turner, Peter R. (1989-06-23) [1988-10-04]. „Pierwiastek do kwadratu przy użyciu arytmetyki indeksu poziomu” . Informatyka . Springer-Verlag . 43 (2): 171–185. ISSN 0010-485X .
Zehendner, Eberhard (lato 2008). „Rechnerarithmetik: Logarithmische Zahlensysteme” (PDF) (skrypt wykładu) (w języku niemieckim). Friedrich-Schiller-Universität Jena . s. 21–22. Zarchiwizowane (PDF) od oryginału w dniu 09.07.2018 r . Źródło 2018-07-09 . [1]
Hayes, Brian (wrzesień – październik 2009). „Wyższa arytmetyka” . Amerykański naukowiec . 97 (5): 364–368. doi : 10.1511/2009.80.364 . Zarchiwizowane od oryginału w dniu 2018-07-09 . Źródło 2018-07-09 . [2] . Przedrukowano także w: Hayes, Brian (2017). „Rozdział 8: Wyższa arytmetyka”. Niezawodne i inne medytacje matematyczne (1 wyd.). Prasa MIT . s. 113–126. ISBN 978-0-26203686-3 . ISBN 0-26203686-X .

Linki zewnętrzne

sli-c-library (hostowana przez Google Code), „Implementacja w C++ arytmetyki symetrycznego indeksu poziomu” .