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

Question

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

Что будет использовать эффективная математическая библиотека?

(Когда я искать его, я просто получить результаты, относящиеся к алгоритмам, которые работают в экспоненциальное время.)

Answer 1

Для маленького экспонента Python использует бинарное возведение (тип потенцирования пути возведения в квадрате), как можно увидеть на линии 2874 от http://svn.python.org/view/python/trunk/Objects/longobject.c?view=markup&pathrev=65518

Для более крупных экспонент использует 2^5-мерное возведение в степень (альтернативный тип возведения в степень возведения в квадрат).

Если вам нужны только самые значащие цифры результата, вы можете очень быстро вычислить x^y = exp (y * log (x)).

Если вы заботитесь только о наименее значимых цифрах результата (например, для конкурса программирования), то вы можете рассчитать показатель по модулю некоторого значения M. Например, команда python pow (x, y, 1000) будет вычислить последние 3 цифры x по значению y. Это делается путем возведения в степень методом квадратизации, но обратите внимание, что это может быть намного быстрее, чем вычисление полного результата, потому что оно гарантирует, что промежуточные числа никогда не будут больше M.

В качестве дополнительного поворота (если вы только интересуются наименьшими значащими цифрами), вы можете использовать теорему Эйлера http://en.wikipedia.org/wiki/Euler%27s_theorem, чтобы уменьшить размер экспоненты.

Answer 2

Если у вас есть данное натуральное число и и данный вход т, чтобы вычислить и^т можно применить следующий алгоритм

q = m; 
prod = 1; 
current = u; 
while q > 0 do 
    if (q mod 2) = 1 then // detects the 1s in the binary expression of m 
      prod = current * prod; // picks up the relevant power 
      q--; 
    endif 
current = current * current; // u^i -> u^(2*i) 
q = q div 2 
enddo 

output = prod; 

Так в основном, если у вас есть, позволяет сказать, и^23 вы конвертировать 23 в двоичный -> 10111 (база 2) Тогда вы получите u^23 = u^16 * u^4 * u^2 * u^1 (no u^8, так как 2 цифры слева направо равны 0)

сложность O (журнал (м)) или O (п), если учесть, п ​​логарифмически (м) _10 + 1

Answer 3

Проблема со всеми приведенными выше двоичными методами заключается в том, что они ограничены только целыми числами. Если под «возведением в степень» вы подразумеваете вычисление функции e^x, то лучшее, что я видел, это степенные ряды, которые сходятся быстро, и полиномиальные, рациональные или приближения Паде, которые действительны в ограниченном диапазоне.

Одно можно сказать наверняка: если вы найдете алгоритм молниеносного алгоритма для e^x до 96 десятичных знаков, вы также найдете более быстрый способ вычисления журналов (по Newton-Raphson). Фактически, Ньютон-Рафсон сходится квадратично, поэтому вы удваиваете количество цифр точности в своем журнале с каждой итерацией. Это был фаворит Нейт Гроссман из UCLA в первые дни.

В дни калькуляторов с четырьмя балками я использовал e^x = (1 + x/1024)^10. Конечно, это ломается для x очень большого или очень маленького, но вы можете понять, почему он работает. Если у вас есть кнопка с квадратным корнем, вы можете отменить эту идею, чтобы получить логарифмы. Но для экспоненциальной функции вам не нужен квадратный корень.

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