0x7FDE623822FC16E6: магическая константа для двойного числа с плавающей запятой.

0x7fde623822fc16e6магическаяконстантадлядвойногочисласплавающейзапятой

0x7FDE 623822 FC 17 E6: магическая константа для двойного числа с плавающей запятой

РЕДАКТИРОВАТЬ: Я никогда не ожидал, что этот пост вызовет такой интерес. Чтобы быть ясным, использование константа – очень плохая идея почти во всех ситуациях, которые я могу придумать. Даже инструкции вроде RCPSS должны использоваться только людьми, которые убеждены, что компромиссы того стоят (или нет другого выбора). Вычитание из константы выше еще хуже и обрабатывает еще меньше угловых случаев.

Я работал над специализированным алгоритмом дискретной оптимизации и perf говорит мне, что он тратит 25% времени на одну инструкцию деления (двойное число с плавающей запятой): алгоритм должен многократно вычислять x 1 для пары сотен тысяч значений в векторе. Если бы знаменатель был постоянным, это было бы просто ускорить. К сожалению, похоже, что единственный способ сокращения обратных величин состоит в вычислении приближения и его уточнении с помощью пары шагов Ньютона-Рафсона .

Удивительно, но все же можно добиться значительного ускорения, когда используются до 3 шагов уточнения: блок деления занимает много места, поэтому, в отличие от него, можно добиться значительного ускорения. умножения и сложения, аппаратные деления редко могут выполняться параллельно. Т.е. каждое деление занимает пару циклов (около 7 – , согласно таблицам Агнера Фога ) и должен дождаться полного вычисления предыдущего деления. Поскольку я делю большое количество значений одно за другим, я ищу хорошую пропускную способность, а не задержку, и может быть полезно выполнять больше операций, если они выполняются параллельно или в конвейере.

Хрестоматийный способ вычисления аппроксимации обратного, вероятно, заключается в использовании аппаратной поддержки. Включено x [-64] , это будет RCPSS , который вычисляет 14 битовое приближение для обратной величины одного числа с плавающей запятой. Для моего случая использования мне также нужно преобразовать в двойные ( CVTSD2SD и CVTSS2SD ). Моя машина Westmere может отправлять одну из этих инструкций за цикл.

Но опять же, похоже, что можно было бы сделать что-то вроде классического быстрый обратный квадратный корень . Просто взяв противоположное значение поля экспоненты, мы получим достойное приближение: double float на x (и на большинстве других машин) представлены как

 знак: экспонента: значащая 1 бит:  биты: 52 бит (и неявная начальная 1) 

Показатель степени подписан, но представлен в виде чисел без знака с положительным смещением: показатель степени 0 представлен как 1022, и – 1 по 1022, 1 по 1023 и т. д. Максимальное смещенное значение для нормального числа равно (2047 используется для бесконечностей и NaN). Итак, чтобы получить противоположное значение показателя степени, достаточно вычесть его из 2047 . Это дает нам небольшую точность, которая, хотя и достаточна для гарантии сходимости шагов Ньютона-Рафсона, отнюдь не полезна.

Вместо этого было бы интересно также использовать мантиссу, чтобы получить еще пару бит точности от вычитания, например, to-double ( a from-double ( x )). Шаги Ньютона-Рафсона могут расходиться, если исходное предположение слишком велико, поэтому константа a должна иметь форму 2047 2 64 b , где b ∈ [0,2521]. Я построил график максимальной ошибки для диапазона входных данных (2 25 равноудаленные значения между 0 и 3), и он выглядит одномодальным (уменьшается до достижения глобального минимума, затем увеличивается ).

PIC

PIC

Я хочу минимизировать функцию, которая кажется одномодальной, но не (априори) дифференцируемой и довольно дорогостоящая в вычислении. Это казалось идеальным приложением для поиска золотого сечения (чтобы избежать проблем с ошибками округления с плавающей запятой, я использовал исчерпывающий поиск, когда диапазон уменьшился до пары тысяч значений). Я подождал пару секунд, и мой REPL выплюнул 0x7FDE FC 17 E6 для наилучшего значения a : максимальная относительная погрешность после 3 шагов составляет порядка 4 12 11 ( 52 бит), а в среднем около 1 11 12 . Скорость сходимости методов Ньютона-Рафсона является квадратичной, поэтому магическая константа дает чуть более 4 (!!) битов точности после одного вычитания.

В конце концов, пройдя RCPSS по-прежнему быстрее, поскольку первоначальное предположение почти в 3 раза точнее, но на другой машине без аппаратной поддержки приблизительных обратных величин или на которой шаги Ньютона-Рафсона выполняются быстрее, может быть полезно сохранить 0x7FDE 623822 FC 17 E6 в уме. Конечно, до сих пор это, кажется, было нечасто: я не могу найти эту константу или какое-либо близкое к ней значение в Google.

Leave a comment

Your email address will not be published. Required fields are marked *