Быстрая логистическая функция

Question

Я ищу способ реализовать быструю логистическую функцию. Классическое определение логистической функции:

y(x) = 1 / (1 + (1/e^x)), где ^ - возведение в степень.

или равно: y(x) = (e^x) / (e^x + 1)

Однако моя специальная логистическая функция имеет базу E вместо e, поэтому:

y(x) = E^x / (E^x + 1)

E и x в моем случае - 32-разрядное целое число с фиксированной точкой в ​​базе 2 типа 16.16. E как можно ближе к реальной константе е.

Какой самый быстрый алгоритм для такой функции? Я бы предпочел не искать таблицы. Что-то вроде битовых манипуляций должно быть идеальным.

---

ОБНОВЛЕНИЕ:

Интуитивно я чувствую, что существует очень быстрый и простой метод, основанный на формуле Эйлера:

e^(i*x) = cos(x) + i*sin(x)

где я - мнимая единица.

Answer 1

Помните о переполнении и недостаточном количестве.Код exp(x)/(1 + exp(x)) будет переполнен при больших положительных значениях x, даже если результат будет приблизительно равен 1. Этого можно избежать, используя 1/(1 + exp(-x)).Это приведет к недостаточному значению к 0 для больших отрицательных значений x, но это может быть приемлемо в зависимости от вашего контекста, поскольку точный результат в этом случае почти равен нулю.Если ваш код вызывается для больших положительных или отрицательных значений x, вы можете сэкономить немного времени, возвращая 0 или 1 для значений, которые в любом случае будут представлены как 0 или 1, и избегайте вызова exp.Таким образом, ваш код может выглядеть примерно так:

if (x > positive cutoff) return 1;
if (x < negative cutoff) return 0;
return 1 / (1 + exp(-x))

То, что это на самом деле более эффективно, зависит от вашей конкретной среды и от того, как часто вы получаете аргументы после предельных значений.

Answer 2

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

Стандартный способ вычисления таких функций - использовать некоторую специальную логику, чтобы вы могли толькодолжны представлять функцию в некотором диапазоне [a, b], аппроксимировать ее рациональной функцией - один многочлен делится на другой, а затем исправлять все, что вам нужно было сделать, чтобы уменьшить диапазон.Источник exp (x) в http://www.netlib.org/fdlibm/e_exp.c, кажется, следует этому образцу.

Это дает вам приближение exp (x) в форме a (x) / b (x).Вы на самом деле хотите 1 / (1 + exp (-x)).Вы должны быть в состоянии изменить реализацию a (x) / b (x), чтобы заставить его выполнять b (-x) / (a ​​(-x) + b (-x)), чтобы у вас было простоодна инструкция деления, внутри переставленной exp (x), вместо одной инструкции деления внутри и одной снаружи.

Это сэкономит вам кое-что, в зависимости от того, насколько дороже деление на вашей машине - это можетбыть заметным, если ваш внутренний цикл действительно на 90% вызывает логистическую функцию.Модель сокращения диапазона плюс рациональная аппроксимация настолько прочно укоренились, что я сомневаюсь, что вы будете делать намного лучше, не жертвуя при этом большой точностью, хотя, если вы прибегаете к целым числам, вы можете быть готовы к этому.

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

Answer 3

Силам нелегко конвертировать в битовые смены, потому что

E^x = 2^log2(E^x) = 2^(x*log2(E))

и это даст вам дробное число бит для сдвига. Вы можете вычислить x * log2 (E) и затем разложить мощность на сумму отдельных битовых сдвигов, но это вряд ли будет так же быстро, как таблица поиска, за которой следует пара итераций метода Ньютона. Опять же, это зависит от того, насколько дорогими являются арифметические операции с фиксированной точкой.

Answer 4

Что-то вроде битовых манипуляций должно быть идеальным

Взгляните на: http://www.schraudolph.org/pubs/Schraudolph99.pdf