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


Сегодня речь зайдет о возведении числа в степень, какую именно? Ответ для различных алгоритмов будет разниться. Однако, давайте договоримся - мы будем рассматривать исключительно множество рациональных чисел, таким образом про комплексные числа мы в этой статье говорить не будем.

Зачастую возвести число в степень достаточно просто, для этого потребуется функция power, которая любезно все сделает за вас. Но что делать, если такой функции у вас нет? А вдруг скорость стандартной функции power вас не устраивает? Давайте самостоятельно попробуем написать функцию, которая бы возводила числа в произвольную степень.


"Математический" алгоритм

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

Математическое обоснование. Давайте займемся математикой, а именно попробуем преобразовать выражение a в степени b. Для этого мы совершим с виду неприметную операцию, воспользуемся тождеством x = exp( ln(x) ). Таким образом мы получим a^b = exp( ln( a^b ) ). Теперь по свойству логарифма вынесем показатель степени (у нас это b), получим a^b = exp( b * ln(a) ).

Формула:

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


"Быстрый" алгоритм

Однако, существует альтернативный алгоритм возведения числа в натуральную степень.

long fast_power(long value, long power){
	long result = 1;
	while (power > 0){
		if (power%2 == 1){
			result *= value;
		}
		value *= value;
		power /= 2;
	}
	return result;
}
.cpp .pas .py

Трассировка

call fast_power(2,10);
result = 1
-> While power>0 
 -> If (power%2 == 1)
  result = 2
 value = 4
 power = 5
-> While power>0 
 -> If (power%2 == 1)
  result = 8
 value = 16
 power = 2
-> While power>0 
 value = 256
 power = 1
-> While power>0 
 -> If (power%2 == 1)
  result = 2048
 value = 65536
 power = 0
return 2048;

Анализ

Для доказательства состоятельно алгоритма сравним его с обыкновенным алгоритмом (цикличным) по количеству операций. Данные для "быстрого" возведения были получены экспериментально.

График зависимости количества операций от показателя степени. Быстрое возведение, циклическое возведение. На оси OX отмечается размер массива, на оси OY количество операций для получения значения.


сравнение "циклического" "быстрого" возведения в степень


Тот же график, но ось OY взята логарифмической(log plot).


Материалы

↑ Расскажите друзьям о статье


Comments system Cackle

© EduNow.su — материалы подлежат полному/частичному копированию при указании прямой ссылки на источник. (Сегодня 29.05.17)