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

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

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

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

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

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

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

$\begin{Bmatrix} s_{k}=x \\ s_{i}=s_{i+1} \cdot x^{m_{i}} \\ 0 \le i \le k-1 \end{Bmatrix}$

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

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

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

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

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

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

Категория: Алгоритмы

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

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

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

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

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

Views

Навигация

Участие

Поиск