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

Question

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

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

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

затем

y₂ = a₂ x + b₂

так далее

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

Answer 1

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

е ^х = 2 ^{х / лн (2)}

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

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

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

Answer 2

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

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

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

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

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

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

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^к*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

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

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

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

Answer 6

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

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

Выходной график

Answer 7

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);
}

и /questions/4653410/luchshij-sposob-vstavit-metku-vremeni-v-vim/4653414#4653414 (ищите приблизительный пример Паде).

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

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

• Страница Wolfram для^х

На странице Википедии Taylor Series также показан пример расширения e^x около 0:

Answer 10

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

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

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

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

Редактировать:

Учитывая предоставленную дополнительную информацию, я провел быстрый тест. Уменьшение диапазона всегда можно использовать для экспоненциальной функции. Таким образом, если я хочу вычислить 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 сегментах.

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