Симметричная арифметика индекса уровня

Представление чисел с помощью индекса уровня ( LI ) и его алгоритмы для арифметических операций были введены Чарльзом Кленшоу и Фрэнком Олвером в 1984 году. ^[1]

Симметричная форма системы LI и ее арифметические операции были представлены Кленшоу и Питером Тернером в 1987 году. ^[2]

Майкл Анюта, Дэниел Лозье, Николя Шабанель и Тернер разработали алгоритм для симметричной арифметики индекса уровня ( SLI ) и ее параллельную реализацию. Была проведена обширная работа по разработке арифметических алгоритмов SLI и их расширению до комплексных и векторных арифметических операций.

Идея системы индексов уровней заключается в представлении неотрицательного действительного числа X в виде

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

где , и процесс возведения в степень выполняется ℓ раз, при этом . ℓ и f — уровень и индекс X соответственно. x = ℓ + f — LI - изображение X . Например,${\displaystyle 0\leq f<1}$${\displaystyle \ell \geq 0}$

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

поэтому его LI-изображение

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

Симметричная форма используется для разрешения отрицательных показателей степени, если величина X меньше 1. Берется sgn (log( X )) или sgn(| X | − | X | ⁻¹ ) и сохраняется (после подстановки +1 вместо 0 для обратного знака; поскольку для X  = 1 =  e ⁰ изображение LI равно x  = 1,0 и однозначно определяет X = 1 , мы можем обойтись без третьего состояния и использовать только один бит для двух состояний −1 и +1 ^{[ необходимо разъяснение ]} ) как обратный знак r _X . Математически это эквивалентно взятию обратного (мультипликативного обратного) числа малой величины, а затем нахождению изображения SLI для обратного знака. Использование одного бита для обратного знака позволяет представлять чрезвычайно малые числа.

Бит знака также может использоваться для разрешения отрицательных чисел. Берется sgn ( X ) и сохраняется (после подстановки +1 вместо 0 для знака; поскольку для X  = 0 изображение LI равно x  = 0,0 и однозначно определяет X  = 0 , мы можем обойтись без третьего состояния и использовать только один бит для двух состояний −1 и +1 ^{[ необходимо разъяснение ]} ) как знак s _X . Математически это эквивалентно взятию обратного (аддитивного обратного) отрицательного числа, а затем нахождению изображения SLI для обратного. Использование одного бита для знака позволяет представлять отрицательные числа.

Функция отображения называется обобщенной логарифмической функцией . Она определяется как

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

и она отображается на себя монотонно, таким образом, будучи обратимой на этом интервале. Обратная, обобщенная экспоненциальная функция , определяется как${\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}}}$

Плотность значений X, представленная x, не имеет разрывов при переходе от уровня ℓ к ℓ  + 1 (весьма желательное свойство), поскольку

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

Функция обобщенного логарифма тесно связана с итерированным логарифмом, используемым в компьютерном анализе алгоритмов.

Формально мы можем определить представление SLI для произвольного действительного числа X (не 0 или 1) как

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

где s _X — знак (аддитивная инверсия или нет) X , а r _X — обратный знак (мультипликативная инверсия или нет), как в следующих уравнениях:

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

тогда как для X = 0 или 1 мы имеем

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

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

Например,

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

и его SLI-представление

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

• Тетрация
• С плавающей точкой (FP)
• Коническая плавающая точка (TFP)
• Логарифмическая система счисления (ЛСС)
• Уровень (логарифмическая величина)

• Clenshaw, Charles William; Olver, Frank William John ; Turner, Peter R. (1989). "Level-index arithmetic: An introductory survey". Numerical Analysis and Parallel Processing (Материалы конференции / Lancaster Numerical Analysis Summer School 1987). Lecture Notes in Mathematics (LNM). 1397 : 95– 168. doi :10.1007/BFb0085718. ISBN 978-3-540-51645-3.
• Кленшоу, Чарльз Уильям; Тернер, Питер Р. (1989-06-23) [1988-10-04]. "Извлечение квадратного корня с использованием арифметики индекса уровня". Computing . 43 (2). Springer-Verlag : 171– 185. doi :10.1007/BF02241860. ISSN  0010-485X.
• Цехенднер, Эберхард (лето 2008 г.). «Rechnerarithmetik: Logarithmische Zahlensysteme» (PDF) (сценарий лекции) (на немецком языке). Йенский университет имени Фридриха Шиллера . стр.  21–22 . Архивировано (PDF) из оригинала 9 июля 2018 г. Проверено 9 июля 2018 г.[1]
• Хейс, Брайан (сентябрь–октябрь 2009 г.). «Высшая арифметика». American Scientist . 97 (5): 364– 368. doi :10.1511/2009.80.364. Архивировано из оригинала 2018-07-09 . Получено 2018-07-09 .[2]. Также перепечатано в: Hayes, Brian (2017). "Глава 8: Высшая арифметика". Foolproof, and Other Mathematical Meditations (1-е изд.). The MIT Press . стр.  113–126 . ISBN 978-0-26203686-3. ISBN 0-26203686-X . 

• sli-c-library (размещено на Google Code), «Реализация симметричной уровневой индексной арифметики на языке C++».