Вычисление полномочий (например, 2^11) быстро [дублирующийся]
6 ответов
Для этого есть обобщенный алгоритм, но в языках, где есть смещение битов, есть гораздо более быстрый способ вычислить мощность 2. Вы просто вставили 1 << exp (предполагая, что ваш оператор сдвига битов - это <<, как это делается в большинстве языков, поддерживающих эту операцию).
Я предполагаю, что вы ищете обобщенный алгоритм и просто выбрали неудачную базу в качестве примера. Приведу этот алгоритм на языке Python.
def intpow(base, exp):
if exp == 0:
return 1
elif exp == 1:
return base
elif (exp & 1) != 0:
return base * intpow(base * base, exp // 2)
else:
return intpow(base * base, exp // 2)
В основном это приводит к тому, что экспоненты могут быть вычислены во времени log2 exp. Это алгоритм "разделяй и властвуй". :-) Как говорил кто-то другой экспонентация путем квадрата .
Если вы подключите к этому свой пример, вы увидите, как он работает и связан с уравнением, которое вы даете:
intpow(2, 13)
2 * intpow(4, 6)
2 * intpow(16, 3)
2 * 16 * intpow(256, 1)
2 * 16 * 256 == 2^1 * 2^4 * 2^8
Используйте битовое смещение. Ex. 1 << 11 возвращает 2^11.
Вы можете использовать возведение в степень возведением в квадрат . Это также известно как «возведение в квадрат и умножение» и также работает для оснований! = 2.
Степень двойки - простая. В двоичном формате 2 ^ 13 - это единица, за которой следует 13 нулей.
Вы бы использовали битовый сдвиг, который является встроенным оператором во многих языках.
Если вы не ограничиваетесь двумя способностями, то:
k^2n = (k^n)^2
Самый быстрый бесплатный алгоритм, который мне известен, принадлежит Филиппу С. Пэну, доктору философии , а исходный код можно найти здесь .
Он использует декомпозицию на основе таблиц, с помощью которой можно сделать функцию exp (), которая в 2-10 раз быстрее, а затем встроенная функция exp () процессора Pentium (R).