Приблизительно е ^ х

Question

Я бы хотел приблизить функцию e ^x .

Можно ли сделать это, используя подход с несколькими типами сплайнов? т.е. между x ₁ и x ₂ , затем

y ₁ = a ₁ x + b ₁ , между x ₂ и x ₃ ,

затем

y ₂ = a ₂ x + b ₂

и т.д.

Это для выделенного оборудования fpga, а не процессора общего назначения. Как таковой, я должен создать функцию сам. Точность гораздо менее важна. Кроме того, я не могу позволить себе более одной схемы умножения и / или нескольких смен / сумматоров. Также я хочу что-то намного меньшее, чем CORDIC-функция, на самом деле размер имеет решающее значение.

Answer 1

Как насчет такой стратегии, которая использует формулу

e ^x = 2 ^{x / ln (2)}

1. Предварительный расчет 1/ln(2)
2. Умножьте эту константу на ваш аргумент (1 умножение)
3. Используйте двоичные сдвиги, чтобы поднять 2 до целой части степени (в формате exp + mantissa)
4. Корректировка на основе дробного остатка степени 2 (вероятно, второго умножения)

Я понимаю, что это не полное решение, но оно требует только одного умножения и сводит оставшуюся проблему к аппроксимации дробной степени 2, которую проще реализовать в аппаратном обеспечении.

Кроме того, если ваше приложение достаточно специализировано, вы можете попытаться заново вывести весь числовой код, который будет работать на вашем оборудовании, чтобы он находился в системе счисления с базовым числом e и реализовал вашу плавающую точку аппаратное обеспечение для работы в базе e . Тогда никакого преобразования не требуется вообще.

Answer 2

Если x является целым числом, вы можете просто умножить e на себя снова и снова.

Если x не является целым числом, вы можете вычислить e ^{floor (x)} , используя вышеуказанный метод, а затем умножить на небольшой поправочный член. Этот поправочный член может быть легко рассчитан с использованием ряда методов аппроксимации. Один из таких способов таков:

e ^f ≈ 1 + f(1 + f/2(1 + f/3(1 + f/4))), где f - дробная часть x

Это происходит из-за (оптимизированного) расширения ряда мощности e ^x , что очень точно для малых значений x. Если вам нужно больше точности, просто добавьте больше терминов к серии.

Этот math.stackexchange вопрос содержит несколько дополнительных умных ответов.

РЕДАКТИРОВАТЬ: Обратите внимание, что существует более быстрый способ расчета e ⁿ , называемый возведением в квадрат путем возведения в квадрат .

Answer 3

Прежде всего, что мотивирует это приближение? Другими словами, что именно не так с простым exp(x)?

Тем не менее, типичная реализация exp(x) - это

• Найдите целое число k и число с плавающей запятой r, чтобы x=k*log(2) + r и r находились в диапазоне от -0,5 * log (2) до 0,5 * log (2).
• С этим уменьшением exp(x) равно 2 ^k *exp(r).
• Расчет 2 ^k совсем несложно.
• Стандартные реализации exp(x) используют алгоритм типа Ремеса, чтобы придумать минимаксный многочлен, который приближается к exp(r).
• Вы можете сделать то же самое, но использовать полином уменьшенного порядка.

Вот кикер: независимо от того, что вы делаете, шансы очень высоки, что ваша функция будет намного, намного медленнее, чем просто вызов exp(). Большая часть функциональности exp() реализована в математическом сопроцессоре вашего компьютера. Реализация этой функциональности в программном обеспечении, даже с пониженной точностью, будет на порядок медленнее, чем просто использование exp().

Answer 4

Для оборудования у меня есть отличное решение для вас, если вам нужно, чтобы оно было точным на уровне битов. (Иначе просто сделайте приближение как выше). Тождество: exp (x) = cosh (x) + sinh (x), гиперболический синус и косинус. Суть в том, что гиперболический синус и косинус могут быть вычислены с использованием техники CORIC, и, что лучше всего, они являются одной из функций FAST CORDIC, то есть они выглядят почти как умножение, а не как деление!

Это означает, что для области множителя массива вы можете вычислить показатель степени с произвольной точностью всего за 2 цикла!

Посмотрите на метод CORDIC - это УДИВИТЕЛЬНО для аппаратной реализации.

Еще один аппаратный подход заключается в использовании небольшой таблицы в сочетании с формулой, упомянутой другими: exp (x + y) = exp (x) * exp (y). Вы можете разбить число на небольшие битовые поля - скажем, 4 или 8 бит за раз - и просто найти показатель степени для этого битового поля. Вероятно, эффективен только для узких вычислений, но это другой подход.

Answer 5

http://martin.ankerl.com/2007/02/11/optimized-exponential-functions-for-java/ с использованием метода Шраудольфа (http://nic.schraudolph.org/pubs/Schraudolph99.pdf) в Java:

public static double exp(double val) {
    final long tmp = (long) (1512775 * val) + (1072693248 - 60801);
    return Double.longBitsToDouble(tmp << 32);
}

и https://math.stackexchange.com/a/56064 (ищите приближенное Паде).

Answer 6

Или вы можете просто сделать pow(M_E, x) в C. (На некоторых платформах не определено M_E; на них вам, возможно, придется вручную указать значение e , которое приблизительно равно 2.71828182845904523536028747135266249775724709369995.)

(Как указывает Дэвид в комментариях, exp(x) будет более эффективным, чем pow(M_E, x). Опять же, мозг еще не включен.)

Есть ли у вас случай использования, когда вычисление e ^x является проверенным узким местом? Если нет, вы должны сначала написать код для удобства чтения; Только попробуйте такие виды оптимизации, если очевидный подход слишком медленный.

Answer 7

Это не запрошенная вами гладкая сплайн-интерполяция, но она эффективна в вычислительном отношении:

float expf_fast(float x) {
   union { float f; int i; } y;
   y.i = (int)(x * 0xB5645F + 0x3F7893F5);
   return (y.f);
}

График вывода

Answer 8

Это не подходит для пользовательских ПЛИС, но стоит упомянуть.

http://www.machinedlearnings.com/2011/06/fast-approximate-logarithm-exponential.html

И исходный код:

https://code.google.com/archive/p/fastapprox/downloads

«Более быстрая» реализация включает в себя только 3 шага (умножение, добавление, преобразование float в int) и окончательное приведение обратно к float.По моему опыту, это точность на 2%, что может быть достаточно, если вы не заботитесь о фактическом значении, но используете значение в итерации максимизации правдоподобия.

Answer 9

Конечно, это «возможно». Есть несколько вопросов.

1. Каково ваше требование к точности?

2. Готовы ли вы использовать сплайны более высокого порядка?

3. Сколько памяти вы готовы потратить на это? Линейная функция через достаточно малые интервалы будет приближать экспоненциальную функцию с любой необходимой степенью точности, но для этого может потребоваться ОЧЕНЬ маленький интервал.

Edit:

Учитывая предоставленную дополнительную информацию, я провел быстрый тест. Уменьшение диапазона всегда можно использовать для экспоненциальной функции. Таким образом, если я хочу вычислить exp (x) для ЛЮБОГО x, тогда я могу переписать задачу в виде ...

y = exp(xi + xf) = exp(xi)*exp(xf)

где xi - целая часть x, а xf - дробная часть. Целая часть проста. Вычислите xi в двоичном виде, затем повторяющиеся квадраты и умножения позволяют вычислить exp (xi) за относительно небольшое количество операций. (Другие трюки с использованием степеней 2 и других интервалов могут дать вам еще большую скорость для голодных.)

Теперь осталось только вычислить exp (xf). Можем ли мы использовать сплайн с линейными сегментами для вычисления exp (xf) в интервале [0,1] только с 4 линейными сегментами с точностью до 0,005?

Этот последний вопрос решается с помощью функции, которую я написал несколько лет назад, которая будет аппроксимировать функцию со сплайном заданного порядка с точностью до фиксированного допуска к максимальной ошибке. Этот код требовал 8 сегментов за интервал [0,1] для достижения требуемого допуска с помощью кусочно-линейной функции сплайна. Если бы я решил уменьшить интервал до [0,0,5], я мог бы теперь достичь предписанного допуска.

Так что ответ прост. Если вы хотите сделать уменьшение диапазона, чтобы уменьшить x до интервала [0.0.5], затем выполните соответствующие вычисления, тогда да, вы можете достичь требуемой точности с помощью линейного сплайна в 4 сегмента.

В конце концов, вам всегда будет лучше, если использовать жестко запрограммированную экспоненциальную функцию. Все операции, упомянутые выше, будут, безусловно, медленнее, чем то, что обеспечит ваш компилятор, если IF exp (x) доступен.

Answer 10

Вольфрам предлагает несколько хороших способов аппроксимации его в терминах серий и т. Д .:

• страница Wolfram для e ^x

Страница Википедии на Серия Тейлора также показывает пример расширения e ^x около 0: