Быстрое возведение в степень — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Функция быстрого возведения в степень)
Строка 4: Строка 4:
  
 
== Функция быстрого возведения в степень ==
 
== Функция быстрого возведения в степень ==
Функция int '''Power'''(int value, int pow)
+
'''function''' Power(value, pow: '''int'''): '''int'''
1. int result = 1;
+
  '''int''' result = 1
2. while (pow) {
+
  '''while''' (pow > 0)
3.    if (pow & 1) result *= value;
+
    '''if''' pow '''mod''' 2 == 1
4.    value *= value;
+
      result *= value
5.    pow >>= 1;
+
    value *= value
6. }
+
    pow /= 2;
7. return result;
+
  '''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://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]
 
* [http://cr.yp.to/bib/2003/joye-ladder.pdf Montgomerry Ladder]

Версия 09:08, 11 сентября 2016

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

Пусть [math]m=(m_{k}m_{k-1}...m_{1}m_{0})_2[/math] — двоичное представление степени n. Тогда [math]n=m_{k} \cdot 2^{k}+m_{k-1} \cdot 2^{k-1}+...+m_{1} \cdot 2+m_{0}[/math], где [math]m_{k}=1, m_{i} \in \{ 0,1 \}[/math] и [math]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}}[/math].

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

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;

Ссылки