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

Question

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

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

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

Answer 1

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

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

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

Интересно, есть ли какая-то инверсия алгоритма AGM, которая могла бы выполнять экспоненциальную функцию ... Хммм ....

Answer 2

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

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

Answer 3

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

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;

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

Сложность O (log (m)) или O (n), если вы считаете n логарифмом (m) _10 + 1