Программирование, 2022, № 6, стр. 14-21

АЛГОРИТМ ВЫЧИСЛЕНИЯ КОРРЕКТНО ОКРУГЛЕННОГО ЗНАЧЕНИЯ ЭКСПОНЕНТЫ С ДВОЙНОЙ ТОЧНОСТЬЮ С ИСПОЛЬЗОВАНИЕМ АРИФМЕТИКИ РАСШИРЕННОЙ ДВОЙНОЙ ТОЧНОСТИ

А. Н. Годунов a*

a ФГУ Федеральный научный центр Научно-исследовательский институт системных исследований Российской академии наук
117218 Москва, Нахимовский просп., 36, корп. 1, Россия

* E-mail: nkag@niisi.ras.ru

Поступила в редакцию 01.06.2022
После доработки 29.06.2022
Принята к публикации 04.07.2022

Полный текст (PDF)

Аннотация

Использование функций, вычисляющих корректно округленное значение экспоненты позволяет, с одной стороны, получить наилучшее приближение, а с другой стороны, обеспечить переносимость (portability) программ. В статье предлагается алгоритм вычисления корректно округленного значения экспоненты, когда аргумент и значение функции являются числами двойной точности, а вычисления производятся с использованием чисел расширенной двойной точности. Дано формальное описание алгоритма. Представленный алгоритм реализован в виде функции на языке Си, проведено его тестирование и измерены временные характеристики. Проведено сравнение с другими алгоритмами.

1. ВВЕДЕНИЕ

Корректно округленное значение экспоненты есть результат округления математически точного значения экспоненты. Использование функций, вычисляющих корректно округленное значение экспоненты позволяет, с одной стороны, получить наилучшее приближение, а с другой стороны, обеспечить переносимость (portability) программ. Вычисление корректно округленного значения экспоненциальной функции рекомендовано стандартом IEEE 754 [1]. Если $x$ – число двойной точности, не равное нулю, то ${{e}^{x}}$ – трансцендентное число. В силу этого вычислить на компьютере точное значение экспоненты для ненулевого аргумента невозможно. Так как корректно округленное значение экспоненты – кусочно-постоянная функция, то можно ограничиться вычислением приближенного значения экспоненты. При этом погрешность вычисления экспоненты должна быть меньше, чем расстояние между точным значением экспоненты и ближайшей точкой разрыва функции округления.

Значения аргумента, для которых расстояние между точным значением экспоненты и ближайшей точкой разрыва функции округления минимально, считаются наиболее трудными (worst cases) для вычисления корректно округленного значения экспоненты. В. Лефевр, Ж.-М. Мюллер [2] были первыми, кто произвел поиск трудных случаев для вычисления корректно округленного значения экспоненциальной функции и других элементарных функций. В дальнейшем эта работа была продолжена В. Лефевром [3] и автором [4]. Результаты этих работ определили требования к точности вычисления экспоненты для получения корректно округленного значения этой функции.

В статье предлагается алгоритм вычисления корректно округленного значения экспоненциальной функции. Аргумент и значение функции – плавающие числа двойной точности, но при вычислениях используются плавающие числа расширенной двойной точности. Обычно для вычисления корректно округленного значения экспоненты с двойной точностью используется арифметика двойной точности. Единственным исключением, известным автору, является функция Лаутера (Lauter) [8], написанная на ассемблере и оптимизированная для процессора Intel Itanium. Эта функция использует числа расширенной двойной точности при вычислениях. Реализация предлагаемого алгоритма на языке Си (и поэтому мобильная) требует существенно меньше времени на вычисление корректно округленного значения экспоненты, чем функция Лаутера.

2. ПРЕДВАРИТЕЛЬНЫЕ СВЕДЕНИЯ

В этом разделе даны основные обозначения, определения и используемые результаты. Напомним, что для представления чисел двойной точности используется основание 2 и 53-битная мантисса. При вычислениях мы используем арифметику расширенной двойной точности: основание 2, длина мантиссы 64 бита.

Стандарт IEEE 754 [1] определяет следующие режимы округления: округление к ближайшему, округление к плюс бесконечности, округление к минус бесконечности и округление к нулю. Предусмотрено два вида режима округления к ближайшему: roundTiesToAway (к большему, если ближайших два) и roundTiesToEven (к числу с четной мантиссой, если ближайших два).

Предлагаемый алгоритм вычисляет корректно округленное значение ${{e}^{x}}$ для всех режимов округления, но при вычислениях используется только округление к ближайшему (roundTiesToEven). Так как ${{e}^{x}}$ всегда положительно, то округление к 0 эквивалентно округлению к минус бесконечности. В силу этого мы не будем рассматривать округление к 0. Если $x$ – алгебраическое число не равное 0, то ${{e}^{x}}$ – трансцендентное число. Поэтому при округлении ${{e}^{x}}$ оба вида округления к ближайшему эквивалентны.

Определение 2.1. Пусть $X$ – арифметическое выражение, $x$ – точное значение $X$, а $x{\kern 1pt} *$ – вычисленное значение $X$. Величину $\Delta (x) = x{\kern 1pt} *$ – x будем называть абсолютной погрешностью вычисления.

Погрешность вычисления обусловлена ошибками округления. Если $x$ – действительное число, то через $\langle x\rangle $ будем обозначать округленное значение $x$ в режиме округления к ближайшему (roundTiesToEven) при использовании арифметики плавающих чисел расширенной двойной точности.

Определение 2.2. Пусть $p$ и $q$ – целые числа такие, что $p \geqslant q$. Множества $B_{{p,q}}^{ + }$, $B_{{p,q}}^{ - }$ и ${{B}_{{p,q}}}$ мы определяем следующим образом:

$B_{{p,q}}^{ + }$множество всех чисел вида

$x = {{b}_{p}} \cdot {{2}^{p}} + {{b}_{{p - 1}}} \cdot {{2}^{{p - 1}}} + \ldots + {{b}_{q}} \cdot {{2}^{q}},$
где каждое из чисел ${{b}_{p}},{{b}_{{p - 1}}}, \ldots ,{{b}_{q}}$ равно 0 или 1;

$B_{{p,q}}^{ - } = \{ x\,{\text{|}}\, - x \in B_{{p,q}}^{ + }\} $;

${{B}_{{p,q}}} = B_{{p,q}}^{ + } \cup B_{{p,q}}^{ - }$.

Определение 2.3. Пусть $n$, $m$, $p$ и $q$ – целые числа такие, что $n \geqslant m > p > q$. Множество ${{T}_{{n,m,p,q}}}$ мы определяем следующим образом:

$\begin{gathered} {{T}_{{n,m,p,q}}} = \{ ({{t}_{1}},{{t}_{2}},{{t}_{3}})\,{\text{|}}\,{{t}_{1}} \in {{B}_{{n,m}}},{{t}_{2}} \in {{B}_{{m - 1,p}}}, \\ {\text{|}}{{t}_{2}}{\text{|}} \leqslant {{2}^{{m - 1}}},{{t}_{3}} \in {{B}_{{p - 1,q}}},{\text{|}}{{t}_{3}}{\text{|}} \leqslant {{2}^{{p - 1}}}\} . \\ \end{gathered} $

Определение 2.4. Пусть $n$ – целое, а $x$ – действительное числа. Тогда ${{R}_{n}}(x)$ есть ближайшее к $x$ число вида $m \cdot {{2}^{n}}$, где m – целое. В случае неоднозначности выбираем четное $m$.

Если $n$ – целое, а $x$ – действительное число, то

${\text{|}}{{R}_{n}}(x) - x{\text{|}} \leqslant {{2}^{{n - 1}}}.$

Если $n$ – целое, а $x$ – число расширенной двойной точности такие, что ${\text{|}}x{\text{|}}{{ < 2}^{{n + 62}}}$, и вычисление $x + 3 \cdot {{2}^{{n + 62}}}$ не приводит к переполнению, то

${{R}_{n}}(x) = \langle x + 3 \cdot {{2}^{{n + 62}}}\rangle - 3 \cdot {{2}^{{n + 62}}}.$

Теорема 2.1 (алгоритм Fast2Sum [7]). Пусть $x$ и $y$ – машинные числа такие, что ${\text{|}}x{\text{|}} \geqslant {\text{|}}y{\text{|}}$. Если их сложение не ведет к переполнению, то существуют такие машинные числа z и zz, что $z = \langle x + y\rangle $ и $x + y = z + zz$. Эти числа могут быть получены следующим образом:

$z: = \langle x + y\rangle ;$
$w: = \langle z - x\rangle ;$
$zz: = \langle y - w\rangle .$

Алгоритм Fast2Sum был предложен Деккером. Ниже мы будем использовать следующую нотацию для алгоритма Fast2Sum:

$(z,zz) \leftarrow Fast2Sum(x,y).$

Следующее определение введено В. Лефевром и Ж.-М. Мюллером (см. [2] и [7]).

Определение 2.5. Пусть $a$ и $b$ – действительные числа, которые имеют одинаковый знак и не равны нулю, и $q$ – целое, такие что ${{2}^{q}} \leqslant {\text{|}}a{\text{|,}}$ ${\text{|}}b{\text{|}}{{ < 2}^{{q + 1}}}$. Расстоянием между мантиссами $a$ и $b$ мы будем называть величину

$\frac{{{\text{|}}a - b{\text{|}}}}{{{{2}^{q}}}}.$

Теорема 2.2 (В. Лефевр, Ж.-М. Мюллер [7]). Пусть $x$ – число двойной точности и $y$ – его экспонента. Пусть, далее, $y{\kern 1pt} *$ – приближенное значение $y$ такое, что расстояние между мантиссами $y$ и $y{\kern 1pt} *$ ограничено $\varepsilon $. Тогда в следующих случаях

если ${\text{|}}x{\text{|}} \geqslant {{2}^{{ - 30}}}$ и $\varepsilon \leqslant {{2}^{{ - 113}}}$,

если ${{2}^{{ - 54}}} \leqslant {\text{|}}x{\text{|}}{{ < 2}^{{ - 30}}}$ и $\varepsilon \leqslant {{2}^{{ - 158}}}$

округление y* эквивалентно округлению y для любого из рассматриваемых режимов округления.

Приведем две модификации теоремы 2.2. Первая относится ко всем рассматриваемым режимам округления.

Теорема 2.3. Пусть $x$ – число двойной точности и y – его экспонента. Пусть, далее, $y{\kern 1pt} *$ – приближенное значение $y$, такое что расстояние между мантиссами $y$ и $y{\kern 1pt} *$ ограничено $\varepsilon $. Тогда в следующих случаях

${\text{|}}x{\text{|}} \geqslant {{2}^{{ - 37}}}$ и $\varepsilon \leqslant 1.33 \cdot {{2}^{{ - 113}}}$,

${{2}^{{ - 44}}} \leqslant {\text{|}}x{\text{|}}{{ < 2}^{{ - 37}}}$ и $\varepsilon \leqslant 1.33 \cdot {{2}^{{ - 134}}}$,

${{2}^{{ - 49}}} \leqslant {\text{|}}x{\text{|}}{{ < 2}^{{ - 44}}}$ и $\varepsilon \leqslant 1.33 \cdot {{2}^{{ - 149}}}$,

${{2}^{{ - 54}}} \leqslant {\text{|}}x{\text{|}}{{ < 2}^{{ - 49}}}$ и $\varepsilon \leqslant 1.33 \cdot {{2}^{{ - 158}}}$

округление $y{\kern 1pt} *$ эквивалентно округлению $y$ для любого из рассматриваемых режимов округления.

Доказательство следует из данных, приведенных в приложении A работы [4]. Вторая модификация относится к режимам округления к ближайшему (см. [4], теорема 6.1).

Теорема 2.4. Пусть $x$ – число двойной точности такое, что ${\text{|}}x{\text{|}} \geqslant {{2}^{{ - 54}}}$, а $y$ – его экспонента. Пусть, далее, $y{\kern 1pt} *$ – приближенное значение $y$, такое что расстояние между мантиссами $y$ и $y{\kern 1pt} *$ ограничено $1.67 \cdot {{2}^{{ - 112}}}$. Тогда для режимов округления к ближайшему округленное значение $y{\kern 1pt} *$ равно округленному значению $y$.

3. ОСОБЫЕ СЛУЧАИ

Положим

$\begin{gathered} {{x}_{{ovr}}} = 0x1.62e42fefa39efp + {\text{9}} \approx 709.78, \\ {{x}_{{dnrm}}} = - 0x1.6232bdd7abcd2p + {\text{9}} \approx - 708.40, \\ \end{gathered} $
$\begin{gathered} {{x}_{{zero1}}} = - 0x1.74385446d71c3p + {\text{9}} \approx - 744.44, \\ {{x}_{{zero2}}} = - 0x1.74910d52d3051p + {\text{9}} \approx - 745.13. \\ \end{gathered} $

Пусть $x$ – число двойной точности. С помощью непосредственных вычислений было получено следующее. Если $x > {{x}_{{ovr}}}$, то корректно округленное значение ${{e}^{x}}$ равно $ + \infty $ при всех видах округления, кроме округления к $ - \infty $. При округлении к $ - \infty $ оно равно $(2 - {{2}^{{ - 52}}}) \cdot {{2}^{{1023}}}$.

Если ${{x}_{{dnrm}}} \leqslant x \leqslant {{x}_{{ovr}}}$, то при всех видах округления корректно округленное значение ${{e}^{x}}$ есть нормализованное число двойной точности.

Если $x < {{x}_{{dnrm}}}$, то при всех видах округления корректно округленное значение ${{e}^{x}}$ есть ненормализованное число или 0.

Если $x < {{x}_{{zero1}}}$, то ${{e}^{x}}{{ < 2}^{{ - 1074}}}$ (наименьшее положительное ненормализованное число). Поэтому корректно округленное значение ${{e}^{x}}$ равно 0 в режиме округления к $ - \infty $. В случае округления к $ + \infty $ оно равно ${{2}^{{ - 1074}}}$.

Если $x < {{x}_{{zero2}}}$, то ${{e}^{x}}{{ < 2}^{{ - 1075}}}$. Поэтому в режиме округления к ближайшему и к $ - \infty $ корректно округленное значение ${{e}^{x}}$ равно 0. В случае округления к $ + \infty $ оно равно ${{2}^{{ - 1074}}}$.

4. АЛГОРИТМ

Предлагаемый алгоритм вычисления корректно округленного значения экспоненты состоит из нескольких (под)алгоритмов, которые реализуют стадии сокращения аргумента, аппроксимации и восстановления. Рассматриваемые алгоритмы используют при вычислениях арифметику расширенной двойной точности, а в результате их применения мы получаем корректно округленное значение экспоненты двойной точности.

4.1. Сокращение аргумента

Предполагается, что предварительно отфильтровываются нечисловые, а также слишком большие и слишком малые значения аргумента, которые обрабатываются отдельно. Детальное описание этого шага можно найти в [5]. Далее мы предполагаем, что аргумент принадлежит отрезку $[{{x}_{{zero2}}},{{x}_{{ovr}}}]$.

Стадия сокращения аргумента состоит из четырех шагов (алгоритмы 4.1, 4.2, 4.3 и 4.4). Алгоритм 4.1 для сокращения аргумента использует равенство

${{e}^{x}}{{ = 2}^{n}} \cdot {{e}^{{x - n \cdot \ln 2}}}.$

Величину $\ln 2$ мы аппроксимируем тройкой $l = ({{l}_{1}},{{l}_{2}},{{l}_{3}}) \in {{T}_{{ - 1, - 40, - 77, - 130}}}$. Путем непосредственных вычислений получаем

(4.1)
$\begin{gathered} {\text{|}}{{l}_{1}}{\text{|}} < 0.694,\quad {\text{|}}{{l}_{2}}{\text{|}} < 1.517 \cdot {{2}^{{ - 43}}}, \\ {\text{|}}{{l}_{3}}{\text{|}} < 1.851 \cdot {{2}^{{ - 79}}}, \\ {\text{|}}\ln 2 - ({{l}_{1}} + {{l}_{2}} + {{l}_{3}}){\text{|}} < 1.901 \cdot {{2}^{{ - 137}}}. \\ \end{gathered} $

Константу $1{\text{/}}\ln 2$ аппроксимируем числом расширенной двойной точности $\tilde {l}$:

(4.2)
$\left| {\frac{1}{{\ln 2}} - \tilde {l}} \right| \leqslant {{2}^{{ - 64}}}.$

Алгоритм 4.1. Сокращение аргумента. Шаг 1

1: m0$ \leftarrow $ R0(x$\tilde {l}$)

2: x0, 1$ \leftarrow $ xm0l1$ \triangleright $ x0, 1 вычисляется точно,            |x0, 1| < 0.5 ⋅ ln2 + 1.596 ⋅ 2–33

3: x0, 2$ \leftarrow $m0l2     $ \triangleright $ x0, 2 вычисляется точно

4: x0, 3$ \leftarrow $m0l3     $ \triangleright $ x0, 3 вычисляется точно

Теорема 4.1. Пусть $x$ – плавающее число двойной точности такое, что ${{x}_{{zero2}}} \leqslant x \leqslant {{x}_{{ovr}}}$, числа ${{m}_{0}}$, ${{x}_{{0,1}}}$, ${{x}_{{0,2}}}$ и ${{x}_{{0,3}}}$ получены с помощью алгоритма 4.1. Тогда ${{m}_{0}}$ – целое число, ${{x}_{{0,1}}}$ и ${{x}_{{0,2}}}$ – плавающие числа двойной точности, а ${{x}_{{0,3}}}$ – плавающее число расширенной двойной точности, и справедливы следующие равенства и неравенства:

$x = {{m}_{0}} \cdot \ln 2 + ({{x}_{{0,1}}} + {{x}_{{0,2}}} + {{x}_{{0,3}}}) - {{\delta }_{0}},$
${\text{где}}\quad {\text{|}}{{m}_{0}}{\text{|}} < 1.051 \cdot {{2}^{{10}}},\quad {\text{|}}{{\delta }_{0}}{\text{|}} < 1.998 \cdot {{2}^{{ - 127}}},$
${\text{|}}{{x}_{{0,1}}}{\text{|}} < 0.5 \cdot \ln 2 + 1.596 \cdot {{2}^{{ - 33}}},$
${\text{|}}{{x}_{{0,2}}}{\text{|}} < 1.595 \cdot {{2}^{{ - 33}}},\quad {{x}_{{0,2}}} \in {{B}_{{ - 33, - 77}}},$
${\text{|}}{{x}_{{0,3}}}{\text{|}} < 1.946 \cdot {{2}^{{ - 69}}},\quad {{x}_{{0,3}}} \in {{B}_{{ - 69, - 130}}}.$

В силу ограничений по объему статьи мы не приводим здесь доказательства теорем или ограничиваемся только основными идеями доказательств. Полные доказательства будут опубликованы позже.

Следующие три шага сокращения аргумента используют равенство

${{e}^{x}} = (1 + v) \cdot {{e}^{{x - \ln (1 + v)}}}.$

При этом мы выбираем значение $v$ так, чтобы величина $x - \ln (1 + v)$ была по возможности малой, а мантисса числа $v$ была короткой.

На втором шаге для поиска величин $1 + v$ и $\ln (1 + {v})$ мы используем таблицу ${{W}_{1}}$, которая создается заранее следующим образом. Для каждого $n$ в диапазоне от –89 до 89 мы находим ближайшее к $n \cdot {{2}^{{ - 8}}}$ число вида $\ln (1 + m \cdot {{2}^{{ - 8}}})$. Элемент номер n таблицы ${{W}_{1}}$ содержит плавающее число

$\begin{gathered} {{W}_{1}}[n].{{w}_{0}} = 1 + m \cdot {{2}^{{ - 8}}} = 1 + v, \\ {\text{где}}\quad v = m \cdot {{2}^{{ - 8}}} \\ \end{gathered} $
и пару чисел расширенной двойной точности, аппроксимирующие $\ln (1 + m \cdot {{2}^{{ - 8}}})$:

${\text{|}}\ln (1 + m \cdot {{2}^{{ - 8}}}) - ({{W}_{1}}[n].{{w}_{1}} + {{W}_{1}}[n].{{w}_{2}}){\text{|}} < {{2}^{{ - 129}}}.$

Алгоритм 4.2. Сокращение аргумента. Шаг 2

1: n1$ \leftarrow $ R0(x0, 1 ⋅ 28)

2: M1$ \leftarrow $ W1[n1].w0

3: x1, 1$ \leftarrow $ x0, 1W1[n1].w1$ \triangleright $ вычисляется точно,           |x1, 1| < 1.175 ⋅ 2–8

4: x1, 2$ \leftarrow $W1[n1].w2

В начале второго шага мы находим ближайшее к ${{x}_{{0,1}}}$ число вида $n \cdot {{2}^{{ - 8}}}$. Далее с помощью таблицы W1 мы находим ближайшую к $n \cdot {{2}^{{ - 8}}}$ величину вида $\ln (1 + m \cdot {{2}^{{ - 8}}})$. Более точно, мы находим пару чисел расширенной двойной точности, аппроксимирующие $\ln (1 + m \cdot {{2}^{{ - 8}}})$.

Теорема 4.2. Пусть $x$ – плавающее число двойной точности такое, что ${{x}_{{zero2}}} \leqslant x \leqslant {{x}_{{ovr}}}$, числа ${{m}_{0}}$, ${{x}_{{0,1}}}$, ${{x}_{{0,2}}}$ и ${{x}_{{0,3}}}$ получены с помощью алгоритма 4.1, а числа ${{M}_{1}}$, ${{x}_{{1,1}}}$ и ${{x}_{{1,2}}}$ получены с помощью алгоритма 4.2.

Тогда ${{x}_{{1,1}}}$ и ${{x}_{{1,2}}}$ – плавающие числа расширенной двойной точности, и справедливы следующие равенства и неравенства:

$x = {{m}_{0}} \cdot \ln 2 + \ln ({{M}_{1}}) + {{x}_{{1,1}}} + {{x}_{{0,2}}} + {{x}_{{1,2}}} + {{x}_{{0,3}}}$
$ - {{\delta }_{0}} - {{\delta }_{1}},\quad {\text{где}}\quad {\text{|}}{{\delta }_{0}}{\text{|}} < 1.998 \cdot {{2}^{{ - 127}}},\quad |{{\delta }_{1}}| \leqslant {{2}^{{ - 129}}},$
${{M}_{1}} = 1 + {{v}_{1}},\quad {{v}_{1}} = {{m}_{1}} \cdot {{2}^{{ - 8}}},\quad - 75 \leqslant {{m}_{1}} \leqslant 106,$
${\text{|}}{{x}_{{1,1}}}{\text{|}} < 1.175 \cdot {{2}^{{ - 8}}},\quad {{x}_{{1,1}}} \in {{B}_{{ - 8, - 64}}},\quad если\quad x \geqslant {{2}^{{ - 12}}},$
${\text{|}}{{x}_{{1,2}}}{\text{|}} \leqslant {{2}^{{ - 65}}},\quad {{x}_{{1,2}}} \in {{B}_{{ - 65, - 128}}}.$

Третий шаг аналогичен второму. На этом шаге мы используем таблицу ${{W}_{2}}$, содержащую элементы с номерами от –75 до 75. Эта таблица позволяет нам аппроксимировать числа вида $n \cdot {{2}^{{ - 14}}}$ числами вида $\ln (1 + m \cdot {{2}^{{ - 14}}})$.

Алгоритм 4.3. Сокращение аргумента. Шаг 3

1: n2$ \leftarrow $ R0(x1, 1 ⋅ 214)

2: M2$ \leftarrow $ M1W2[n2].w0$ \triangleright $ вычисляется точно,           0.703 < M2 < 1.421, M2B0, –22

3: x2, 1$ \leftarrow $ x1, 1W2[n2].w1$ \triangleright $ вычисляется точно,           |x2, 1| < 0.675 ⋅ 2–14

4: x2, 2$ \leftarrow $W2[n2].w2

Теорема 4.3. Пусть x – плавающее число двойной точности такое, что ${{x}_{{zero2}}} \leqslant x \leqslant {{x}_{{ovr}}}$, числа ${{m}_{0}}$, ${{M}_{2}}$, ${{x}_{{0,2}}}$, ${{x}_{{0,3}}}$, ${{x}_{{1,2}}}$, ${{x}_{{2,1}}}$ и ${{x}_{{2,2}}}$ получены путем последовательного применения алгоритмов 4.1, 4.2 и 4.3. Тогда ${{x}_{{2,1}}}$ – плавающее число двойной точности, ${{x}_{{2,2}}}$ – плавающее число расширенной двойной точности, и справедливы следующие равенства и неравенства:

$\begin{gathered} x = {{m}_{0}} \cdot \ln 2 + \ln ({{M}_{2}}) + ({{x}_{{2,1}}} + {{x}_{{0,2}}}) \\ \, + ({{x}_{{1,2}}} + {{x}_{{2,2}}} + {{x}_{{0,3}}}) - ({{\delta }_{0}} + {{\delta }_{1}} + {{\delta }_{2}}),\quad где \\ \end{gathered} $
${{M}_{2}} = {{M}_{1}} \cdot (1 + {{v}_{2}}),\quad {{v}_{2}} = {{m}_{2}} \cdot {{2}^{{ - 14}}},$
$ - 75 \leqslant {{m}_{2}} \leqslant 75,$
$0.703 < {{M}_{2}} < 1.421,\quad {{M}_{2}} \in {{B}_{{0, - 22}}},$
${\text{|}}{{x}_{{2,1}}}{\text{|}} < 0.675 \cdot {{2}^{{ - 14}}},$
${{x}_{{2,1}}} \in {{B}_{{ - 15, - 67}}},\quad если\quad x \geqslant {{2}^{{ - 15}}},$
${\text{|}}{{x}_{{2,2}}}{\text{|}} \leqslant {{2}^{{ - 65}}},\quad {{x}_{{2,2}}} \in {{B}_{{ - 65, - 128}}},\quad {\text{|}}{{\delta }_{2}}{\text{|}} \leqslant {{2}^{{ - 129}}}.$

На четвертом шаге таблицы не применяются, а величины $v$ и $\ln (1 + v)$ вычисляются. Для поиска величины $v$ мы используем приближение $x \approx \ln $(1 + + x). Положим ${{v}_{3}} = 3 \cdot {{R}_{{ - 30}}}\left( {\frac{1}{3} \cdot {{x}_{2}}} \right),$ где ${{x}_{2}} = {{x}_{{2,1}}}$ + + x0,2. Величина ${{v}_{3}}$ имеет короткую мантиссу, делится точно на 3 и ${{x}_{2}} \approx \ln (1 + {{v}_{3}})$. Для вычисления $\ln (1 + {{v}_{3}})$ мы используем следующее приближение

(4.3)
$\begin{array}{*{20}{c}} {\ln (1 + v) \approx v - 0.5 \cdot {{v}^{2}} + \frac{{{{v}^{3}}}}{3} + {{v}^{4}} \cdot {{P}_{3}}(v).} \end{array}$

Полином ${{P}_{3}}$ был найден с помощью пакета Sollya [6]:

${{P}_{3}}(v) = {{a}_{0}} + v \cdot ({{a}_{1}} + v \cdot ({{a}_{2}} + v \cdot {{a}_{3}})),$
${{a}_{0}} = {\text{ - }}0xf.ffffffffffffffdp - 6,$
${{a}_{1}} = 0xc.cccccccccccccc1p - 6,$
${{a}_{2}} = - 0xa.aaaaaae49a3c83p - 6,$
${{a}_{3}} = 0x9.249249728e270fdp - 6.$

Погрешность приближения (4.3) на интервале $[ - 0.677 \cdot {{2}^{{ - 14}}},0.677 \cdot {{2}^{{ - 14}}}]$ не превышает $1.495 \cdot {{2}^{{ - 123}}}.$

Используя (4.3), получаем

$\begin{gathered} ({{x}_{{2,1}}} + {{x}_{{0,2}}}) + ({{x}_{{0,3}}} + {{x}_{{1,2}}} + {{x}_{{2,2}}}) = \ln (1 + {{v}_{3}}) + \\ \, + (({{x}_{{2,1}}} + {{x}_{{0,2}}}) + ({{x}_{{0,3}}} + {{x}_{{1,2}}} + {{x}_{{2,2}}}) - \ln (1 + {{v}_{3}})) \approx \\ \, \approx \ln (1 + {{v}_{3}}) + {{x}_{{3,1}}} + {{x}_{{3,2}}},\quad {\text{где}} \\ \end{gathered} $
${{x}_{{3,1}}} = ({{x}_{2}} - {{v}_{3}}) + 0.5 \cdot v_{3}^{2} - v_{3}^{2} \cdot v_{3}^{'},$
${{x}_{{3,2}}} = (({{x}_{{0,3}}} + {{x}_{{1,2}}}) + {{x}_{{2,2}}}) - {v}_{3}^{4} \cdot {{P}_{3}}({{{v}}_{3}}).$

Алгоритм 4.4. Сокращение аргумента. Шаг 4

1: x2$ \leftarrow $ x2, 1 + x0, 2            $ \triangleright $ x2 вычисляется точно

2: ${v}_{3}^{'}$ $ \leftarrow $ R–30$\left( {\frac{1}{3} \cdot {{x}_{2}}} \right)$

3: ${{v}_{3}}$ $ \leftarrow $ 3 ⋅ ${v}_{3}^{'}$ $ \triangleright $ |${{v}_{3}}$| < 0.677 ⋅ 2–14, ${{v}_{3}}$B–15,–30

4: x3, 1$ \leftarrow $ (x2${{v}_{3}}$) + 0.5 $v_{3}^{2}$$v_{3}^{2}$${v}_{3}^{'}$                 $ \triangleright $ x3, 1           вычисляется точно, |x3, 1| < 1.210 ⋅ 2–29

5: x3, 2$ \leftarrow $ ((x0, 3 + x1, 2) + x2, 2) – $v_{3}^{4}$P3(${{v}_{3}}$)

6: $ \triangleright $ |x3, 2| < 1.821 ⋅ 2–61, Δ(x3, 2) < 1.219 ⋅ 2–123

7: M3$ \leftarrow $ M2 (1 + ${{v}_{3}}$) $ \triangleright $ M3 вычисляется точно, 0.703 < M3 < 1.421, M3B0, –52

Теорема 4.4. Пусть $x$ – плавающее число двойной точности такое, что ${{x}_{{zero2}}} \leqslant x \leqslant {{x}_{{ovr}}}$, числа ${{m}_{0}}$, ${{M}_{3}}$, ${{x}_{{3,1}}}$ и ${{x}_{{3,2}}}$ получены путем последовательного применения алгоритмов 4.1, 4.2, 4.3 и 4.4. Тогда справедливы следующие равенства и неравенства:

$\begin{gathered} x = {{m}_{0}} \cdot \ln 2 + \ln ({{M}_{3}}) + {{x}_{{3,1}}} + {{x}_{{3,2}}} - {{\delta }_{a}}, \\ где\quad 0.703 < {{M}_{3}} < 1.421,\quad {{M}_{3}} \in {{B}_{{0, - 52}}}, \\ \end{gathered} $
$\begin{gathered} {\text{|}}{{x}_{{3,1}}}{\text{|}} < 1.210 \cdot {{2}^{{ - 29}}},\quad {\text{|}}{{x}_{{3,2}}}{\text{|}} < 1.821 \cdot {{2}^{{ - 61}}}, \\ {\text{|}}{{\delta }_{a}}{\text{|}} < 1.436 \cdot {{2}^{{ - 122}}}. \\ \end{gathered} $

Из теоремы 4.4 следует, что

(4.4)
$\begin{array}{*{20}{c}} {{{e}^{x}}{{{ = 2}}^{{{{m}_{0}}}}} \cdot {{M}_{3}} \cdot {{e}^{{{{x}_{{3,1}}} + {{x}_{{3,2}}} - {{\delta }_{a}}}}}.} \end{array}$

Таким образом, в результате четырех шагов нам удалось сократить аргумент до величины меньшей $1.211 \cdot {{2}^{{ - 29}}}$. Так как числа ${{{v}}_{1}}$, ${{{v}}_{2}}$ и ${{{v}}_{3}}$ имеют короткие мантиссы, то M3 вычисляется точно и является числом двойной точности.

4.2. Вычисление значения функции

Алгоритмы 4.5 и 4.6 завершают вычисление корректно округленного значения экспоненты ${{e}^{x}}$. Если ${{x}_{{dnrm}}} \leqslant x \leqslant {{x}_{{ovr}}}$, то используется алгоритм 4.5, а если $\;{{x}_{{zero2}}} \leqslant x\; < {{x}_{{dnrm}}}$, то используется алгоритм 4.6.

Фактически каждый из этих алгоритмов описывает три алгоритма: один – для округления к ближайшему, второй – для округления к плюс бесконечности и третий – для округления к минус бесконечности (см. комментарии к алгоритмам). Например, в алгоритме 4.5 при округлении к ближайшему используется строка 21, а строки с 22 по 39 не используются. Сами алгоритмы используют при вычислениях только округление к ближайшему (roundTiesToEven).

Теорема 4.5. Пусть x – число двойной точности. Если ${{x}_{{dnrm}}} \leqslant x \leqslant {{x}_{{ovr}}}$, то алгоритмы 4.1, 4.2, 4.3, 4.4 и 4.5 вычисляют корректно округленное значение экспоненты ${{e}^{x}}$. Если $\;{{x}_{{zero2}}} \leqslant x < {{x}_{{dnrm}}}$, то алгоритмы 4.1, 4.2, 4.3, 4.4 и 4.6 вычисляют корректно округленное значение экспоненты ${{e}^{x}}$.

Полное доказательство теоремы 4.5 будет опубликовано позже.

5. ТЕСТИРОВАНИЕ И ВРЕМЕННЫЕ ХАРАКТЕРИСТИКИ

Предложенные выше алгоритмы были реализованы в виде функции crexp_e() на языке Си. Эта функция была протестирована на компьютере с процессором Core i7-2600K CPU, 3.4 ГГц и операционной системой Linux Fedora 20 Kernel 3.19.8. Для компиляции использовался компилятор gcc, версия 4.8.3, уровень оптимизации 3.

Для тестирования на каждом интервале $\left[ {{{x}_{{dnrm}}},{{x}_{{ovr}}}} \right]$ и $\left[ {{{x}_{{zero2}}},{{x}_{{dnrm}}}} \right)$ случайным образом было выбрано по 10,000,000,000 значений аргумента, для которых вычислялось значение функции crexp_e() при всех рассматриваемых режимах округления. Дополнительно функция тестировалась при малых значениях аргумента (${\text{|}}x{\text{|}}{{ < 2}^{{ - 28}}}$) и при значениях аргумента близких к ${{x}_{{dnrm}}}$. Для тестирования использовались также худшие случаи из [24, 7]. Для проверки корректности тестируемой функции использовались функции библиотеки CRlibm, версия 1.0beta4. Все тесты прошли успешно.

При оценке производительности время измерялось в тактах процессора. Реальная частота процессора при измерениях была равна номинальной – 3.4 ГГц. Все измеряемые функции работали в режиме округления к ближайшему.

Мы также рассматривали экспоненциальную функцию ОС Линукс. Более точно, мы использовали функцию __ieee754_exp() вместо exp(), чтобы избежать динамического вызова. Эта функция вычисляет корректно округленное значение экспоненты при округлении к ближайшему. При этом используется только арифметика двойной точности.

Мы также рассматривали функцию Лаутера [8], которая вычисляет корректно округленное значение экспоненциальной функции при всех рассматриваемых режимах округления. Функция Лаутера использует арифметику расширенной двойной точности, написана на ассемблере и оптимизирована для процессора Intel Itanium.

Алгоритм 4.5. ${{x}_{{dnrm}}} \leqslant x \leqslant {{x}_{{ovr}}}$

1:                                        $ \triangleright $ ex = ${{2}^{{{{m}_{0}}}}}$M3${{e}^{{{{x}_{{3,1}}} + {{x}_{{3,2}}} - {{\delta }_{a}}}}}$

2:                          $ \triangleright $ 0.703 < M3 < 1.421, M3B0, −52

3:                  $ \triangleright $ |x3, 1| < 1.210 ⋅ 2−29, |x3, 2| < 1.821 ⋅ 2−61,           |δa| < 1.436 ⋅ 2−122

4: M3, 1R−30(M3)

5: M3, 2M3M3, 1$ \triangleright $ M3 = M3, 1 + M3, 2

6: S1R−62(x3, 1) $ \triangleright $ S1 вычисляется точно,          |S1| < 1.211 ⋅ 2−29, S1B−29, −62

7: x3x3, 1 + x3, 2

8:                              $ \triangleright $ |x3| < 1.211 ⋅ 2−29, |Δ(x3)| ≤ 2−93

9: S2 ← ((x3, 1S1) + x3, 2) + $x_{3}^{2}$$\left( {0.5 + \frac{1}{{3!}} \cdot {{x}_{3}}} \right)$

10:             $ \triangleright $ |S2| < 1.985 ⋅ 2−59, |Δ(S2)| < 1.850 ⋅ 2−121

11:                                        $ \triangleright $ ${{e}^{{{{x}_{{3,1}}} + {{x}_{{3,2}}} - {{\delta }_{a}}}}}$ ≈ 1 + S1 + S2

12:            $ \triangleright $ ${{2}^{{ - {{m}_{0}}}}}$ex ≈ (M3, 1 + M3, 2) ⋅ (1 + S1 + S2) =            M3 + M3, 1S1 + M3, 2S1 + M3S2

13:    $ \triangleright $ |M3, 1S1| < 1.723 ⋅ 2−29, M3, 1S1B−29, −92

14:                                       $ \triangleright $ (211 − 1) + M3B11, −52

15: (Y, Y1) ← Fast2Sum(((211 − 1) + M3), M3, 1S1)

16:                      $ \triangleright $ |M3, 2S1 + M3S2| < 1.714 ⋅ 2−58,            |Δ(M3, 2S1 + M3S2)| < 1.815 ⋅ 2−120.

17: Y2Y1 + (M3, 2S1 + M3S2)

18:             $ \triangleright $ |Y2| < 1.054 ⋅ 2−53, |Δ(Y2)| < 1.227 ⋅ 2−117

19:                            $ \triangleright $ Округленные значения ex и            ${{2}^{{{{m}_{0}}}}}$ ⋅ ((Y − (211 − 1)) + Y2) равны

20:                            $ \triangleright $ Округление к ближайшему

21: y ← (Y + Y2) − (211 − 1)                                      $ \triangleright $            0.701 + (211 − 1) < Y + Y2 < 1.423 + (211 − 1)

22:                                               $ \triangleright $ Округление к +∞

23: yY − (211 − 1)                   $ \triangleright $ 0.702 ≤ y ≤ 1.422

24: if Y2 > 0 then

25:     if y ≥ 1 then

26:        yy + 2−52

27:     else

28:       yy + 2−53

29:     end if

30: end if

31:                                $ \triangleright $ Округление к −∞ или к 0

32:        yY − (211 − 1)

33: if Y2 < 0 then

34:     if y > 1 then

35:        yy − 2−52

36:     else

37:        yy − 2−53

38:     end if

39: end if

40: return y${{2}^{{{{m}_{0}}}}}$                          $ \triangleright $ Восстановление

Алгоритм 4.6. ${{x}_{{zero2}}} \leqslant x < {{x}_{{dnrm}}}$

1:                                        $ \triangleright $ ex = ${{2}^{{{{m}_{0}}}}}$M3${{e}^{{{{x}_{{3,1}}} + {{x}_{{3,2}}} - {{\delta }_{a}}}}}$

2:                          $ \triangleright $ 0.703 < M3 < 1.421, M3B0, −52

3:                        $ \triangleright $ |x3, 1| < 1.210 ⋅ 2−29, x3, 1B−29, −90,           |x3, 2| < 1.821 ⋅ 2−61, |δa| < 1.436 ⋅ 2−122

4: M3, 1R−30(M3)

5:                    $ \triangleright $ 0.702 < M3, 1 < 1.422, M3, 1B0, −30

6: $M_{3}^{'}$${{2}^{{{{m}_{0}}}}}$M3

7: $M_{{3,1}}^{'}$${{2}^{{{{m}_{0}}}}}$M3, 1

8: $M_{{3,2}}^{'}$$M_{3}^{'}$$M_{{3,1}}^{'}$

9:                                                   $ \triangleright $ $M_{3}^{'}$ = $M_{{3,1}}^{'}$ + $M_{{3,2}}^{'}$

10: S1R−62(x3, 1) $ \triangleright $ S1 вычисляется точно,            |S1| < 1.211 ⋅ 2−29, S1B−29, −62

11: x3x3, 1 + x3, 2

12:                            $ \triangleright $ |x3| < 1.211 ⋅ 2−29, |Δ(x3)| ≤ 2−93

13: S2 ← ((x3, 1S1) + x3, 2) + $x_{2}^{3}$$\left( {0.5 \cdot \frac{{{{x}_{3}}}}{{3!}}} \right)$

14:             $ \triangleright $ |S2| < 1.985 ⋅ 2−59, |Δ(S2)| < 1.850 ⋅ 2−121

15: Y1t2 + (t1 + (M3, 2S1 + M3S2))

16:                                         $ \triangleright $ ex$M_{3}^{'}$ ⋅ (1 + S1 + S2)

17:                                                             $ \triangleright $ 2−1011 + ex ≈            2−1011 + $M_{3}^{'}$ +$M_{{3,1}}^{'}$S1 + $M_{{3,2}}^{'}$S1 + $M_{3}^{'}$S2

18: (t0, t1) ← Fast2Sum($M_{3}^{'}$, $M_{{3,1}}^{'}$S1)

19:       $ \triangleright $ $M_{3}^{'}$, $M_{{3,1}}^{'}$S1, t0 и t1 вычисляются точно

20: (Y, t2) ← Fast2Sum(2−1011, t0)

21:     $ \triangleright $ YB−1011, −1074, Y и t2 вычисляются точно

22:                                                                          $ \triangleright $ ex ≈             (Y −2−1011) + (t2 + (t1 + ($M_{{3,2}}^{'}$S1 + $M_{3}^{'}$S2)))

23:                                                         $ \triangleright $ Округление

24: yY − (2−1011 − 2−1022)

25: $ \triangleright $ Округление к ближайшему

26: if (t2 + 2−1075) + (t1 + ($M_{{3,2}}^{'}$S1 + $M_{3}^{'}$S2)) < 0             then

27:  yy − 2−1074

28: else if (t2 − 2−1075) + (t1 + ($M_{{3,2}}^{'}$S1 + $M_{3}^{'}$S2)) >             0 then

29:  yy + 2−1074

30: end if

31:                                               $ \triangleright $ Округление к +∞

32: if t2 + (t1 + ($M_{{3,2}}^{'}$S1 +$M_{3}^{'}$S2)) > 0 then

33:  yy + 2−1074

34: end if

35:                                               $ \triangleright $ Округление к −∞

36: if t2 + (t1 + ($M_{{3,2}}^{'}$S1 +$M_{3}^{'}$S2)) < 0 then

37:  yy − 2−1074

38: end if

39: return y − 2−1022                            $ \triangleright $ Восстановление

Для сравнения мы также использовали функцию crexp_d(), которая реализует алгоритмы предложенные автором в [4]. Эта функция использует только арифметику двойной точности.

Таблицы 1 и 2 содержат результаты измерений (в тактах процессора). Максимальное время выполнения функций на указанных интервалах приведено в таблице 1. Таблица 2 содержит среднее время выполнения функций. Все измерения для всех функций кроме функции Лаутера были произведены автором. Данные, относящиеся к функции Лаутера, взяты из статьи Лаутера [8].

Таблица 1.

Максимальное время (нсек)

  $\left[ {{{x}_{{dnrm}}},{{x}_{{ovr}}}} \right]$ $\left[ {{{x}_{{zero2}}},{{x}_{{dnrm}}}} \right)$
crexp_e 141 156
crexp_d 219 220
Lauter 172 4578
CRlibm 735 1023
Linux 76 297 6160
Combined 185 157
Таблица 2.

Среднее время (нсек)

  $\left[ {{{x}_{{dnrm}}},{{x}_{{ovr}}}} \right]$ $\left[ {{{x}_{{zero2}}},{{x}_{{dnrm}}}} \right)$
crexp_e 141 156
crexp_d 188 195
Lauter 172 4578
CRlibm 85 1020
Linux 52 381
Combined 51 157

Как видно из таблицы 1, функция crexp_e() обладает наименьшим максимальным временем выполнения на обоих интервалах. Функция Лаутера требует на 22% больше времени на интервале $\left[ {{{x}_{{dnrm}}},{{x}_{{ovr}}}} \right]$ и в 30 раз больше времени на интервале $\left[ {{{x}_{{zero2}}},{{x}_{{dnrm}}}} \right)$.

Среднее время выполнения функции crexp_e() на интервале $\left[ {{{x}_{{zero2}}},{{x}_{{dnrm}}}} \right)$ также меньше, чем у других функций, представленных в таблице, но среднее время выполнения функции crexp_e() на интервале $\left[ {{{x}_{{dnrm}}},{{x}_{{ovr}}}} \right]$ больше, чем у функций CRlibm и Линукс. Среднее время можно снизить объединяя функции crexp_e() и __ieee754_exp() аналогично тому, как это сделано в [4]. Для этого нужно в функции __ieee754_exp() заменить вызов функции __slowexp() на вызов функции crexp_e() на интервале $\left[ {{{x}_{{dnrm}}},{{x}_{{ovr}}}} \right]$. При этом на интервале $\left[ {{{x}_{{zero2}}},{{x}_{{dnrm}}}} \right)$ вызывается только функция crexp_e(). Полученная таким образом функция (Combined) имеет лучшее среднее время выполнения на обоих интервалах $\left[ {{{x}_{{zero2}}},{{x}_{{dnrm}}}} \right)$ и $\left[ {{{x}_{{dnrm}}},{{x}_{{ovr}}}} \right]$, но максимальное время на интервале $\left[ {{{x}_{{dnrm}}},{{x}_{{ovr}}}} \right]$ увеличится. Отметим, что эта функция может использоваться только в режиме округления к ближайшему.

Список литературы

  1. IEEE Std. 754-2008 – IEEE Standard for Floating-Point Arithmetic. IEEE Std. 2018.

  2. Lefèvre V., Muller J.-M. Worst cases for correct rounding of the elementary functions in double precision. In Proceedings of the 15th IEEE Symposium on Computer Arithmetic. June 2001. P. 111–118.

  3. Lefèvre V. Hardest-to-Round Cases – Part 2 // Journées TaMaDi. Lyon. Oct. 2013. [Online]. Available: http://tamadiwiki.enslyon.fr/tamadiwiki/images/c/c1/Lefevre2013.pdf.

  4. Godunov A. Algorithms for Calculating Correctly Rounded Exponential Function in Double-Precision Arithmetic // IEEE Transactions on Computers. V. 69. № 5. P. 1–12. July 2020. https://doi.org/10.1109/TC.2020.2972901

  5. Daramy-Loirat C., Defour D., de Dinechin F., Gallet M., Gast N., Lauter C.Q., Muller J.-M. “CR-LIBM, a library of correctly rounded elementary functions in double-precision”, LIP, Research Report, 2006, https://hal-enslyon. archives-ouvertes.fr/ensl-01529804.

  6. Chevillard S., Joldeş M., Lauter C. Sollya: An Environment for the Development of Numerical Codes. In Mathematical Software – ICMS 2010. P. 28–31, Heidelberg, Germany, September 2010, Springer.

  7. Muller J.-M. Elementary Functions: Algorithms and Implementation. Birkhauser. 2005.

  8. Lauter C. A correctly rounded implementation of the exponential function on the Intel Itanium architecture // INRIA, Research Report, RR-5024, 2003. [Online]. Available: https://hal.inria.fr/inria-00071560/document

Дополнительные материалы отсутствуют.