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

Тип компьютерной арифметики

Представление чисел с помощью индекса уровня ( 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),\,r_{X}=\operatorname {sgn}(|X|-|X|^{-1}),\,x=\psi (\max(|X|,|X|^{-1}))=\psi (|X|^{r_{X}})}$

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

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

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

Например,

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

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

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

Смотрите также

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

Ссылки

1. Кленшоу, Чарльз Уильям; Олвер, Фрэнк Уильям Джон (1984). «За пределами плавающей точки». Журнал ACM . 31 (2): 319–328. doi : 10.1145/62.322429 .
2. Кленшоу, Чарльз Уильям; Тернер, Питер Р. (1988-10-01) [1986-09-16, 1987-06-04]. "Симметричная система уровня-индекса". Журнал численного анализа IMA . 8 (4). Oxford University Press , Институт математики и ее приложений: 517–526. doi :10.1093/imanum/8.4.517. ISSN  0272-4979. OCLC  42026743. Получено 10 июля 2018 г.

Дальнейшее чтение

• Clenshaw, Charles William; Olver, Frank William John ; Turner, Peter R. (1989). "Level-index arithmetic: An introductory survey". Numerical Analysis and Parallel Processing (Материалы конференции / Летняя школа численного анализа в Ланкастере, 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++».