[an error occurred while processing this directive]
|
Но немного. И исключая экзотику м.б.
Странное дело, сколько пользовался возведением в степень с использованием разложения показателя, но никогда не знал, что это алгоритм Монтгомери-). Когда-то сам его придумал. Хотя потом и встречал в книжках, но без упоминания Монтгомери. В общем как у Ильфа, Петрова - "Какой удар со стороны классика":-)
Но есть быстрее, с точки зрения числа умножений, алгоритмы.
Пример. От фонаря. Возведение в 14 степень. Разложение потребует 3 раза в квадрат и 3 умножения. Итого 6.
С другой стороны x^14=x^8*x^6; x^8=x^6*x^2; x^6=x^4*x^2; x^4=x^2*x^2;
x^2=x*x. Итого 5. Но с промежут. запоминанием x^2,x^6.
В общем ищется оптимальный путь. Кто придумал - не знаю.
E-mail: info@telesys.ru