Является ли вычисление в 2 ** раза быстрее, чем exp (x)?

12

Простите за наивность, которая будет очевидна в том, как я задаю этот вопрос, а также в том, что я его задаю.

Математики обычно используют поскольку это самая простая / хорошая база в теории (из-за исчисления). Но компьютеры, кажется, делают все в двоичном формате, так что на машине быстрее вычислять, чем ?exp2**xMath::exp(x)

isomorphismes
источник
7
О каком номере ты говоришь? Целое число произвольного размера? Фиксированный размер с плавающей точкой? Произвольная точность с плавающей точкой?
Жиль "ТАК - перестань быть злым"
@ Жиль: Это хороший момент. Я не понял, разница была важна.
изоморфизм
3
Я видел на некоторых карманных калькуляторах Casio, что регистрация и мощность числа не-e намного медленнее, чем ln / exp
phuclv
2
Чтобы рискнуть быть тупым, вы пробовали синхронизировать их обоих и увидеть, что быстрее? Или вы говорите о скорости в смысле сложности ? O(f(n))
Jmite
1
Язык отвечает за выбор самого быстрого пути и хорошо с этим справится. Только в том случае, если требуется максимальная скорость, и измерения показали, что это имеет отношение к производительности, если вы беспокоитесь о такого рода вещах
vonbrand

Ответы:

18

Поскольку это CS, а не Stackoverflow, я собираюсь предположить, что вы задаете вопрос о числовом анализе, и (для простоты), в частности, IEEE-754 с плавающей запятой. В этом случае ответ на ваш вопрос частично зависит от того, что вы подразумеваете под «проще», и частично от деталей системы.

Ни один из современных процессоров, о которых я знаю, не имеет встроенной инструкции, которая делает именно то, что вы ожидаете, либо для операции (которую отныне мы будем называть , ее обычное имя в C), либо для ( ). Они оба реализованы с использованием библиотечных функций.2 хexexp2xexp2

Как и в случае со всеми числовыми методами для трансцендентных операций, следует рассмотреть несколько особых случаев:

exp(NaN) = NaN
exp(+Inf) = +Inf
exp(-Inf) = 0

Однако есть еще одна вещь, которая делает задачу несколько менее сложной: полезный домен довольно мал. Для двоичного 32: переполнение, exp(x)если или около того, и переполнение, если или около того. Необычно для трансцендентных операций, мы также можем игнорировать субнормальный случай, так как он неотличим от if субнормальный. Все вышеперечисленное также верно, за исключением того, что домен немного отличается.x<104x>88.7exp(x)1.0xexp2

Ваша интуиция права в том, что большинство реализаций вычисляют . Однако стоимость этого умножения на тривиальна по сравнению с остальными вычислениями . Типичный метод использует предварительно вычисленную таблицу с элементами:ex=2x/ln2 K1ln2exp2K

exp2(x)=2n×T[j]×P(y)

где - целая часть , таблица содержит значения для всех в диапазоне , а - некоторое полиномиальное приближение к (четвертого достаточно для двоичного кода32) ) в диапазоне . Часть дешева, поскольку она просто манипулирует экспонентой. это таблица соответствия. Так что , вероятно, будет дорогой частью операции.x T 2 j / K j [ 0 , K ) P 2 x [ 0 , 1nxT2j/Kj[0,K)P2x2нТП[0,1K)2nTP

Для полноты следует отметить, что в процессорах Intel x86 FPU есть инструкция f2xm1, которая вычисляет для в диапазоне . Однако на современном процессоре это довольно дорогая и не конвейерная инструкция, и вам не рекомендуется ее использовать. Как справедливо отмечает Раздел 3.8.5 Справочного руководства по оптимизации Intel :х [ - 1 , 1 ]2x1x[1,1]

Хотя x87 поддерживает трансцендентные инструкции, реализация трансцендентальной функции в библиотеке программного обеспечения может быть быстрее во многих случаях.

Изменить: в комментариях было указано, что я должен объяснить некоторые из новой терминологии, используемой в IEEE 754-2008. Некоторый язык изменился с 1985 и 1987 годов, и большинство людей гораздо лучше знакомы со старым жаргоном.

Термины «binary32» и «binary64» являются новыми именами для 32-разрядных и 64-разрядных двоичных чисел с плавающей запятой, которые старый стандарт называл «одинарными» и «двойными» соответственно.

Термин «субнормальное число» заменяет предыдущий термин «денормальное число» или «денормализованное число» .

Псевдоним
источник
когда вы говорите «субнормальный» - вы явно не имеете в виду «субгауссовский»; Вы имеете в виду «хуже, чем [эталон типичности]»?
изоморфизм
2
@isomorphismes Здесь «субнормальный» относится к тому, как реализованы числа с плавающей точкой. Смотрите ненормальные числа в Википедии.
Пол Манта
Кстати, я немного упростил «типичный метод». Возможно реализовать exp2 () и exp () с точностью ulp, используя только одно небольшое (и довольно простое для понимания) расширение для представленного здесь метода, но объяснение небольшого простого для понимания расширения, вероятно, удвоит длину ответ!
псевдоним
6

Если 2**xвы имеете в виду , то да. Мы можем использовать оператор левого сдвига , т.е. мы вычисляем . Это молниеносно, так как это примитивная машинная инструкция для каждого процессора, о котором я знаю. Это не может быть сделано с любой базой, кроме 2. Более того, целочисленное возведение в степень всегда будет быстрее, чем вещественное возведение в степень, поскольку числа с плавающей запятой умножаются дольше.2x<<1 << x

gardenhead
источник
4
не совсем. х может быть с плавающей запятой
phuclv
1
Извините, я неявно предположил, что является целым числом. x
садовник
Если xэто не целое число (скажем, 20.75), вы должны установить для мантиссы 2значение округления и показатель степени в xкачестве наиболее точной оценки (точное представление невозможно). Который тоже намного быстрее, чем `Pow '.
Деймон
1

Если 2**xэто функция от целых чисел, то я согласен с ответом Стивена, сдвиг дешевле. Но я обычно вижу это как 2^xи **для обозначения возведения в степень с плавающей точкой. В этом случае я ожидал бы сходную производительность между **и, ^так как оба expи pow(базовая операция для **) обе являются операциями трансцендентного приближения.

Тим
источник
Интересно, я не знал, что **это считается синонимом версии с плавающей запятой (и, глупый я, я забыл, что эти два будут разными).
изоморфизм
1

Поскольку 2 ^ x = e ^ (x * ln 2) и e ^ x = 2 ^ (x * log2 (e)), вы не ожидаете большой разницы.

Для x, близкого к нулю, обычно используют полином e ^ x = 1 + x + x ^ 2/2 + x ^ 3/6 ..., хорошо оптимизированный, чтобы обрезать как можно быстрее, сохраняя при этом небольшую ошибку округления , Очевидно, что 2 ^ x немного крошечнее, чтобы вычислить. «Х близко к 0» обычно будет значения х, где sqrt (1/2) <= e ^ x <= sqrt (2). Ограничение диапазона x гарантирует, что степень многочлена не должна быть выбрана слишком высокой.

Для больших x обычно вычисляют 2 ^ x, если x = x '+ x' ', где x' - целое число, а -0,5 <= x '' <= 0,5. Затем 2 ^ x 'будет рассчитываться путем построения числа с плавающей запятой с правильным битовым шаблоном, а 2 ^ x' '- с использованием метода e ^ x для малого x. Здесь 2 ^ x чуть быстрее. Более того, если x имеет большой размер (скажем, x = 100,3), просто умножение x на log2 (e) приведет к недопустимой ошибке округления (поскольку имеется намного меньше дробных битов), поэтому необходимо уделять больше внимания.

И, надеюсь, хорошая библиотечная функция позаботится о том, чтобы всякий раз, когда x <= y, e ^ x <= e ^ y и 2 ^ x <= 2 ^ y, независимо от ошибок округления. Достичь такого рода вещей может быть сложно.

gnasher729
источник
0

Вы должны понимать, что математика на компьютере выполняется по-разному с помощью различных программ, и мы надеемся, что у них будут последовательные ответы. Глядя на большинство программных продуктов, я думаю, что компьютеры ведут себя как хорошие компьютеры - и будут вычислять ответ в течение длительного времени даже для 0 ^ 0. Проблема в том, что в особых случаях используется «распознавание», которое не происходит бесплатно в цифровых компьютерах. Это означает, что только в тех случаях, когда получение ответа ускорит процесс, «больше всего» произойдет оптимизация. Но в тех случаях это произойдет очень хорошо. Также обратите внимание, что для получения правильного ответа может потребоваться несколько разных определений. Это называется уровнями оптимизации скорости, и это произошло в максимальной профессиональной степени в основе большинства программ, называемых GNU «C». Это связано с тем, что здесь в качестве показателей приемлемости качества используются небольшие различия во времени выполнения от программного обеспечения к программному обеспечению и от машины к машине. В других интерпретаторах обычно только в том случае, если в качестве побочного эффекта предыдущих вычислений возникает «нулевой флаг», будет выполняться ускоренное распознавание. например, 0 * x => C0.

отметка
источник