Алгоритм быстрого возведения в степень

Материал из Википедии — свободной энциклопедии

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

Алгоритм не всегда оптимален. Например, при n=15 требуется 6 умножений, хотя на самом деле возведение в 15-ую степень можно выполнить за 5 умножений.

[править] Теоретические основы алгоритма

Пусть  — двоичное представление степени n. Тогда , где и .

Таким образом, алгоритм быстрого возведения в степень сводится к мультипликативному аналогу схемы Горнера.

[править] Псевдокод

s := x;
for  i := k–1 downto  0  do
  begin
    s := s*s;
    if (n[s] = 1) then
       s := s*x;
  end;

[править] Программная реализация

Используется представление числа x^m:

.

int power(int t, int k) {
// exponentiate integer t to power k
  int res = 1;
  while (k) {
        if (k & 1) res *= t;
        t *= t;
        k >>= 1;
  }
  return res;
}

[править] Оценка сложности

Чтобы узнать, сколько умножений потребуется для возведения числа x в степень n алгоритмом быстрого возведения в степень, нужно произвести вычисления по следующей формуле: k = H + 2(E − 1), где H — количество нулей, а E — количество единиц в двоичной записи числа n.

Так, для возведения числа в сотую степень этим алгоритмом потребуется всего лишь 8 умножений.

Таким образом количество умножений равно O(lnn).

[править] Обобщение

Пусть пара (S, *) — полугруппа, то есть S — произвольное множество, на котором задана бинарная операция * такая, что:

• Для любых элементов a и b из S справедливо: (a * b) так же из S. (замкнутость)
• Для любых элементов a, b и c из S справедливо: ((a * b) * c) = (a * (b * c)). (ассоциативность)

Мы можем назвать операцию * умножением и определить операцию возведения в натуральную степень:

Для вычисления значений aⁿ можно использовать алгоритм быстрого возведения в степень.

[править] Литература

• Валицкас А. И. Конспект лекций по дисциплине: Элементы абстрактной и компьютерной алгебры. //Тобольск, ТГПИ им. Д. И. Менделеева, 2004.