Симметричная арифметика индекса уровня
Тип компьютерной арифметики

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

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

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

Определение

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

Х = е е е ⋯ е ф {\displaystyle X=e^{e^{e^{\cdots ^{e^{f}}}}}}

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

Х = 1234567 = е е е 0,9711308 {\displaystyle X=1234567=e^{e^{e^{0.9711308}}}}

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

х = ℓ + ф = 3 + 0,9711308 = 3.9711308. {\displaystyle x=\ell +f=3+0,9711308=3,9711308.}

Симметричная форма используется для разрешения отрицательных показателей степени, если величина X меньше 1. Берется sgn (log( X )) или sgn(| X | − | X | −1 ) и сохраняется (после подстановки +1 вместо 0 для обратного знака, поскольку для X  = 1 =  e 0 изображение 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 для обратного. Использование одного бита для знака позволяет представлять отрицательные числа.

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

ψ ( Х ) = { Х если  0 ≤ Х < 1 1 + ψ ( вн ⁡ Х ) если  Х ≥ 1 {\displaystyle \psi (X)={\begin{cases}X&{\text{if }}0\leq X<1\\1+\psi (\ln X)&{\text{if }}X\geq 1\end{cases}}}

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

φ ( х ) = { х если  0 ≤ х < 1 е φ ( х − 1 ) если  х ≥ 1 {\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 (весьма желательное свойство), поскольку:

г φ ( х ) г х | х = 1 = г φ ( е х ) г х | х = 0 . {\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 — обратный знак (мультипликативной инверсии или нет), как в следующих уравнениях:

с Х = знак ⁡ ( Х ) , г Х = знак ⁡ ( | Х | − | Х | − 1 ) , х = ψ ( макс ( | Х | , | Х | − 1 ) ) = ψ ( | Х | г Х ) {\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 мы имеем:

с 0 = + 1 , г 0 = + 1 , х = 0.0 , {\displaystyle s_{0}=+1,r_{0}=+1,x=0.0,\,}
с 1 = + 1 , г 1 = + 1 , х = 1.0. {\displaystyle s_{1}=+1,r_{1}=+1,x=1.0.\,}

Например,

Х = − 1 1234567 = − е − е е 0,9711308 {\displaystyle X=-{\dfrac {1}{1234567}}=-e^{-e^{e^{0.9711308}}}}

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

х = − φ ( 3.9711308 ) − 1 . {\displaystyle x=-\varphi (3.9711308)^{-1}.}

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

Ссылки

  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++».
Взято с "https://en.wikipedia.org/w/index.php?title=Арифметика_симметричного_уровня-индекса&oldid=1247825367"