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

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

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

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

Определение

Идея системы индексов уровней состоит в том, чтобы представить неотрицательное действительное число $X$ как

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

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

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

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

x=\ell +f=3+0.9711308=3.9711308.

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

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

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

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

и это отображает $[0,\infty )$ на себя монотонно и поэтому обратимо на этом интервале. Обратная, обобщенная экспоненциальная функция , определяется выражением

\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$ (очень желательное свойство), поскольку:

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

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

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

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

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

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 мы имеем:

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

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

Например,

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

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

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

См. также

Ссылки

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

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

Кленшоу, Чарльз Уильям; Олвер, Фрэнк Уильям Джон ; Тернер, Питер Р. (1989). «Арифметика индекса уровня: вводный обзор». Численный анализ и параллельная обработка (Материалы конференции / Летняя школа численного анализа в Ланкастере, 1987). Конспекты лекций по математике (LNM). 1397 : 95–168. дои : 10.1007/BFb0085718 .
Кленшоу, Чарльз Уильям; Тернер, Питер Р. (23 июня 1989 г.) [4 октября 1988 г.]. «Возведение корня в квадрат с использованием арифметики индекса уровня». Вычисление . 43 (2). Спрингер-Верлаг : 171–185. ISSN 0010-485X .
Ценднер, Эберхард (лето 2008 г.). «Компьютерная арифметика: логарифмические системы счисления» (PDF) (сценарий лекции) (на немецком языке). Йенский университет имени Фридриха Шиллера . стр. 21–22. Архивировано (PDF) из оригинала 9 июля 2018 г. Проверено 9 июля 2018 г. [1]
Хейс, Брайан (сентябрь – октябрь 2009 г.). «Высшая арифметика» . Американский учёный . 97 (5): 364–368. дои : 10.1511/2009.80.364 . Архивировано из оригинала 9 июля 2018 г. Проверено 9 июля 2018 г. [2] . Также перепечатано в: Хейс, Брайан (2017). «Глава 8: Высшая арифметика». Защита от дурака и другие математические размышления (1-е изд.). Массачусетский технологический институт Пресс . стр. 113–126. ISBN 978-0-26203686-3 . ISBN 0-26203686-X .

Внешние ссылки

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

[Clenshaw_1984-1] Кленшоу, Чарльз Уильям; Олвер, Фрэнк Уильям Джон (1984). «За пределами плавающей точки» . Журнал АКМ . 31 (2): 319–328. дои : 10.1145/62.322429 .

[Clenshaw_1988-2] Кленшоу, Чарльз Уильям; Тернер, Питер Р. (1 октября 1988 г.) [16 сентября 1986 г., 4 июня 1987 г.]. «Симметричная система индексов уровней» . Журнал IMA численного анализа . 8 (4). Издательство Оксфордского университета , Институт математики и ее приложений: 517–526. дои : 10.1093/иманум/8.4.517 . ISSN 0272-4979 . OCLC 42026743 . Проверено 10 июля 2018 г.

[1]

[2]