Алгоритм “Быстрая степень”
Рассмотрим возведение an, где n- целое, положительное число. Алгоритм основан на двоичном представлении показателя n.
n= nk*2k + nk-1*2k-1 +. . . . ni*2i+. . . .n1*21+ n0+20
Вычисление этого произведения представляется тремя параллельными процессами:
· вычисление ni– цифр двоичного представления показателя n,они получаются как остатки от деления на 2 сначала n,а потомчастных от делений, пока не получится частное, равное нулю, остатки в порядке получения n0 n1 n2 . . .nk-1 nk(см. перевод целого в двоичную систему).
· параллельно с этим процессом строятся степени: a=a*a
.
· Кроме того, происходит накопление произведения в некоторой переменной p (в начале p=1;): если остаток niравен нулю, соответствуюшая степень не учитываертся в произведении, если ni ≠0, то p=p* ,т.е. в этом алгоритме (быстром!) не все степени вычисляются, а из вычисленных не все учитываются.
p=1 а n |_2
a1 n0 | n|_2
a2 n1| n
. . . . . . .
p=p* ,если ni ≠0
. . . . . .
, nk-1 |n |_2
a2k nk | 0
Пример. Найти a18.
18=100102, т.е.в произведении строятся степени a1, a2, a4, a8, a16,
а учитываются две, p=1* a2* a16
#include <iostream>
using namespace std;
// функция возведения a в степень n
double power (double a, int n)
{double p=1;
while (n!=1)
{if (n&1) p*=a; // анализ очередной двоичной цифры
a*=a; //в переменной a получается очередная степень
n>>=1; // сдвиг n
}
return p*a;
}
// Рекурсивный вариант функции возведения a в степень n
double powerR (double a, int n)
{if (n==0) return 1;
if (n==1) return a;
if (n&1) return powerR (a*a, n>>1)*a;
else return powerR (a*a, n>>1);
}
int main (){
cout<<power(2.0,18)<<endl;
cout<<powerR(2.0,18)<<endl;
return 0;
}
Результаты: