В16-ом коде: FF FF FF 85

 

Алгоритм “Быстрая степень”

Рассмотрим возведение aⁿ, где n- целое, положительное число. Алгоритм основан на двоичном представлении показателя n.

 

n= n_k*2^k + n_k-1*2^k-1 +. . . . n_i*2ⁱ+. . . .n₁*2¹+ n₀+2⁰

 

Вычисление этого произведения представляется тремя параллельными процессами:

· вычисление n_i– цифр двоичного представления показателя n,они получаются как остатки от деления на 2 сначала n,а потомчастных от делений, пока не получится частное, равное нулю, остатки в порядке получения n₀ n₁ n₂ . . .n_k-1 n_k(см. перевод целого в двоичную систему).

· параллельно с этим процессом строятся степени: a=a*a

.

· Кроме того, происходит накопление произведения в некоторой переменной p (в начале p=1;): если остаток n_iравен нулю, соответствуюшая степень не учитываертся в произведении, если n_i ≠0, то p=p* ,т.е. в этом алгоритме (быстром!) не все степени вычисляются, а из вычисленных не все учитываются.

p=1 а n |_2

a¹ n₀ | n|_2

a² n₁| n

. . . . . . .

p=p* ,если n_i ≠0

. . . . . .

, n_k-1 |n |_2

a2^k n_k | 0

Пример. Найти a¹⁸.

18=10010₂, т.е.в произведении строятся степени a¹, a², a⁴, a⁸, a¹⁶,

а учитываются две, p=1* a²* a¹⁶

 

#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;

}

Результаты: