Быстрое возведение в степень, являющуюся степенью двойки

Question

Быстрое возведение в степень, являющуюся степенью двойки

Iv Iv Знаток (302), закрыт 6 лет назад

существуют ли способы возводить число (мне нужно комплексное) в степень, являющуюся степенью двойки быстрее, чем за лог? Типа Z^(2^1000) быстрее, чем за 1000 операций

Answer 1

Ну, есть так называемые гипероператоры, например, тетрация. Как это реализовано на машинном уровне - быстрее 1000 операций или нет - не знаю. Возможно, с квантовым компьютером это действительно займет меньше 1000 операций. Но в квантоовм программировании не разбираюсь

Answer 2

a^{2^n}={a^{2^{n-1}}}^2 - раскручивай
Только при таких показателях степени или длинная арифметика, а это долго, или жуткая потеря точности, тогда может попроще функции с похожим поведением найти? Или, в конце концов, при наличии памяти, посчитать заранее и готовыми таблицами пользоваться?

Answer 3

Вообще-то мат. сопроцессор "умеет" экспоненты и логарифмы, так что если с компилятором все хорошо, то обычный метод x^y=ln(y*e^x) должен пахать достаточно быстро. С комплексными числами наверняка тоже есть какой-то способ, сходу не придумаю.

Answer 4

impressive_i Мыслитель (5215) 6 лет назад

x^y = exp(y*lnx)
Чтобы быстро найти степень, которая представляет стпень двойки, нужно единицу сдвигать влево побитово. Это компиляторы делают очень быстро.
2^k = 1 << k

Iv IvЗнаток (302) 6 лет назад

Мне нужно не 2 в степень возводить, а комплексное число в степень, являющуюся степенью двойки

impressive_i Мыслитель (5215) Для более удобного возведения в степень комплексного числа его можно перевести в показательную степень или использовать формулу Эйлера. z = x + i*y |z| = sqrt(x^2 + y^2) fi = arg(z) = arctg(y/x) z = |z| * exp(i*fi) z^k = |z|^k * exp(i*k*fi)