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

Алгоритм, в общем-то, простой, но менее полезным от этого он не становится. Замечательных особенностей у него две. Первая — если возводить число в неотрицательную степень n по определению, то сложность полученного решения будет O (n) (здесь и в дальнейшем, если нет ремарки, считаем, что на хранение одного числа уходит константное количество памяти, а арифметические операции выполняются за константное время), тогда как данный алгоритм справится за O (log n). Вторая замечательная особенность заключается в том, что для того чтобы алгоритм работал, основание степени не обязательно должно быть числом, достаточно чтобы это основание было из множества S с определённой над ним операцией * со всего двумя свойствами.

  1. Если a и b принадлежат S, то и a * b принадлежит S. Это свойство замкнутости.
  2. Должно выполняться свойство ассоциативности, иными словами должно всегда выполняться следующее равенство (a * b) * c = a * (b * c).

В алгебре определённую выше пару (S, *) называют полугруппой (но это так, для справки).

Идея алгоритма проста, зачем считать то, что уже подсчитано? Пользуясь тем, что верно следующее: 1, если n чётное, иначе 2,

Получаем рекуррентное соотношение (возведение в степень представляем по этому же соотношению и так далее). Расписав всё до конца, начнём считать полученную формулу с конца. Получим следующий итерационный процесс:

  1. Если n кратно 2, умножаем буферную переменную на саму себя и делим n на 2.
  2. Если n не кратно 2, то умножаем переменную результата на объект, который мы возводим в степень, и уменьшаем на 1 n.

Делаем мы это, пока n не станет равным нулю, начальные значения для буферной переменной – объект, который возводим в степень, для переменной результата – единица. Ну и результат по завершению процесса будет лежать в переменной результата.

В коде это выглядит так:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
double fast_power(double a, unsigned int n)
{
  double res = 1, buff = a;

  while(n)
    {
      if(n % 2 == 0)
        {
          buff *= buff;
          n /= 2;
        }
      else
        {
          res *= buff;
          --n;
        }
    }

  return res;
}

_____________________________________

Интересно про что вам хотелось бы почитать? Есть вариант писать про геометрию, либо про строковые алгоритмы, либо про алгоритмы на графах. Последние две темы, думаю, лично для будут очень полезны, так как по ним писал, на мой взгляд мало.

Метки: , ,
Google Bookmarks Digg Reddit del.icio.us Ma.gnolia Technorati Slashdot Yahoo My Web News2.ru БобрДобр.ru RUmarkz Ваау! Memori.ru rucity.com МоёМесто.ru Mister Wong

2 thoughts


    1. Александр, www.kalimdor.ru/life/vozvrashhenie.html . Если в кратце, я уже давно слез с темы и то что знаю, уже давно не актуально. Единственное, я подумываю коснуться тем коллаборативного поиска и классификации информации. Первое, например, позволяет создать рекомендательную систему для магазина.

Напишите комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *