Как рассчитываются показатели?

Question

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

Я специально ищу алгоритм pow(), используемый для чисел с плавающей запятой с двойной точностью.

Answer 1

У меня была возможность взглянуть на реализацию fdlibm. Замечания описывают алгоритм, используемый:

*     n 
* Method: Let x = 2 * (1+f) 
*  1. Compute and return log2(x) in two pieces: 
*    log2(x) = w1 + w2, 
*   where w1 has 53-24 = 29 bit trailing zeros. 
*  2. Perform y*log2(x) = n+y' by simulating muti-precision 
*   arithmetic, where |y'|<=0.5. 
*  3. Return x**y = 2**n*exp(y'*log2) 

с последующим перечислением всех особых случаев обрабатываются (0, 1, инф, наны).

Наиболее интенсивные разделы кода, после обработки специального корпуса, включают вычисления и 2**. И в них нет петель. Таким образом, несмотря на сложность примитивов с плавающей запятой, это выглядит как асимптотически постоянный алгоритм.

Эксперты с плавающей точкой (из которых я не один) могут комментировать. :-)

Answer 2

Обычный подход, чтобы приподнять к Ь, для целого показателя, выходит что-то вроде этого:

result = 1 
while b > 0 
    if b is odd 
    result *= a 
    b -= 1 
    b /= 2 
    a = a * a 

Это, как правило, логарифмический в размере экспоненте. Алгоритм основан на инвариантном «a^b * result = a0^b0», где a0 и b0 - начальные значения a и b.

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

Редактировать: Поскольку, кажется, есть некоторый интерес, вот версия без дополнительного умножения.

result = 1 
while b > 0 
    while b is even 
    a = a * a 
    b = b/2 
    result = result * a 
    b = b - 1 

Answer 3

Если бы я писал функцию pow, нацеленную на Intel, я бы возвратил exp2 (log2 (x) * y). Микрокод Intel для log2, несомненно, быстрее, чем что-либо, что я мог бы кодировать, даже если бы я мог вспомнить свой первый год исчисления и численный анализ градиентной школы.

Answer 4

Если они не обнаружили лучший способ сделать это, я считаю, что приближенные значения для тригонометрии, логарифмические и экспоненциальные функции (для экспоненциального роста и распада, например), как правило, рассчитаны с использованием арифметических правил и ряд Тейлора разложений для получения приблизительного результата с точностью до требуемой точности. (См. Любую книгу исчисления для получения подробных сведений о степенных сериях, сериях Тейлора и расширениях функций серии Maclaurin.) Обратите внимание, что прошло какое-то время, так как я сделал все это, поэтому я не мог сказать вам, например, точно, как рассчитать количество терминов в серии, которую вы должны включить, гарантирует ошибку, которая достаточно мала, чтобы быть незначительной при вычислении с двойной точностью.

Например, разложение в ряд Тейлора/Маклорена для е^х такова:

 +inf [ x^k ]   x^2 x^3  x^4  x^5 
e^x = SUM [ --- ] = 1 + x + --- + ----- + ------- + --------- + .... 
     k=0 [ k! ]   2*1 3*2*1 4*3*2*1 5*4*3*2*1 

Если взять все условия (к от 0 до бесконечности), это разложение является точным и полным (нет ошибка).

Однако, если вы не принимаете все условия, выходящие на бесконечность, но вы остановитесь после того, как скажете 5 терминов или 50 терминов или что-то еще, вы произведите приблизительный результат, который отличается от фактического значения функции e^x остаток, который довольно легко рассчитать.

Хорошая новость для экспонента является то, что она сходится красиво и члены его разложения по полиномам довольно легко кодировать итеративно, так что вы мощи (повтор, Might - помните, это было каким-то время), даже не нужна чтобы предварительно вычислить, сколько терминов вам необходимо для гарантии вашей ошибки, меньше точности, потому что вы можете проверить размер вклада на каждой итерации и остановиться, когда она станет достаточно близкой к нулю. На практике я не знаю, является ли эта стратегия жизнеспособной или нет - я должен попробовать. Есть важные детали, о которых я давно забыл. Например: точность машины, ошибка машины и ошибка округления и т. Д.

Также обратите внимание, что если вы не используете e^x, но вы делаете рост/распад с другой базой, например 2^x или 10^x , изменяется аппроксимирующая полиномиальная функция.

Answer 5

Вы можете использовать exp (n * ln (x)) для расчета x ⁿ. Оба x и n могут быть числами с двойной точностью, с плавающей запятой. Естественный логарифм и экспоненциальная функция могут быть рассчитаны с использованием рядов Тейлора. Здесь вы найдете формулы: http://en.wikipedia.org/wiki/Taylor_series