Быстрое возведение в степень

2016-09-11T06:08:40Z

216.252.79.20: /* Функция быстрого возведения в степень */

'''Алгоритм быстрого возведения в степень''' — алгоритм, предназначенный для возведения числа ''x'' в натуральную степень ''n'' за меньшее число умножений, чем это требуется в определении.

Пусть <tex>m=(m_{k}m_{k-1}...m_{1}m_{0})_2</tex> — двоичное представление степени ''n''. Тогда <tex>n=m_{k} \cdot 2^{k}+m_{k-1} \cdot 2^{k-1}+...+m_{1} \cdot 2+m_{0}</tex>, где <tex>m_{k}=1, m_{i} \in \{ 0,1 \}</tex> и <tex>x^{n}=x^{((...((m_{k} \cdot 2+m_{k-1}) \cdot 2+m_{k-2}) \cdot 2+...) \cdot 2+m_{1}) \cdot 2 + m_{0}}</tex>. <br>

== Функция быстрого возведения в степень ==
'''function''' Power(value, pow: '''int'''): '''int'''
'''int''' result = 1
'''while''' (pow > 0)
'''if''' pow '''mod''' 2 == 1
result *= value
value *= value
pow /= 2;
'''return''' result;

== Ссылки ==
* [http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.24.8878&rep=rep1&type=pdf BinPow and 2^k-ary pow]
* [http://cr.yp.to/bib/2003/joye-ladder.pdf Montgomerry Ladder]

Викиконспекты - Вклад участника [ru]

Быстрое возведение в степень