Быстрое возведение в степень, являющуюся степенью двойки
существуют ли способы возводить число (мне нужно комплексное) в степень, являющуюся степенью двойки быстрее, чем за лог? Типа Z^(2^1000) быстрее, чем за 1000 операций
Ну, есть так называемые гипероператоры, например, тетрация. Как это реализовано на машинном уровне - быстрее 1000 операций или нет - не знаю. Возможно, с квантовым компьютером это действительно займет меньше 1000 операций. Но в квантоовм программировании не разбираюсь
x^y = exp(y*lnx)
Чтобы быстро найти степень, которая представляет стпень двойки, нужно единицу сдвигать влево побитово. Это компиляторы делают очень быстро.
2^k = 1 << k
Вообще-то мат. сопроцессор "умеет" экспоненты и логарифмы, так что если с компилятором все хорошо, то обычный метод x^y=ln(y*e^x) должен пахать достаточно быстро. С комплексными числами наверняка тоже есть какой-то способ, сходу не придумаю.
a^{2^n}={a^{2^{n-1}}}^2 - раскручивай
Только при таких показателях степени или длинная арифметика, а это долго, или жуткая потеря точности, тогда может попроще функции с похожим поведением найти? Или, в конце концов, при наличии памяти, посчитать заранее и готовыми таблицами пользоваться?