Пусть задано некоторое число n, которое требуется возвести в натуральную степень p.
Приведенный ниже алгоритм, вычисляет результат за O(log p) операций.
Алгоритм:
- Получаем степень числа p в двоичном представлении.
- Установим начальный результат r 1, а n -- n0.
- Если последняя цифра двоичной записи степени числа равна 1, тогда присваиваем в качестве начального результата число, которое мы возводим в степень. В противном случае, результат останется равен единице.
- Проходим по двоичной записи справа налево начиная со второго елемента:
- возводим n0 в квадрат и сохраняем это значение.
- если встречаем единицу, вычисляем следующую операцию: r = (n0*r).
- r будет содержать конечный результат.
#include <stdio.h>
#include <stdlib.h>
#include <conio.h>
#include <math.h>
#define BIN_SIZE 32
int to_binary (int p, int *a)
{
int i,j, p0=p;
int a0[BIN_SIZE];
for (i=0; p0; p0>>=1, i++) a0[i]=(p0 & 1)?(1):(0);
for (j=0; j<i; j++) a[j]=a0[i-j-1];
return i; // length!
}
int in_power (int n, int p)
{
int n0=n,
r=1,
i,
a[BIN_SIZE];
if (p == 0) return r; // simple
if (p == 1) return n;
int len = to_binary(p,a);
if (a[len-1] == 1) r=n;
for (i=len-2; i>=0; i--)
{
n0=n0*n0;
if (a[i]) r=r*n0;
}
return r;
}
int main ()
{
clrscr();
int n, p;
printf("Write number: "); scanf("%d",&n);
printf("Write power: "); scanf("%d",&p);
printf("Result: %d\n", in_power(n,p));
return 0;
}