Реализации алгоритмов/Быстрое возведение в степень

Используется представление числа x^m:

$x^{m}=x^{m_{0}}\cdot \left(x^{2}\right)^{m_{1}}\cdot \left(x^{2^{2}}\right)^{m_{2}}\cdot \left(x^{2^{3}}\right)^{m_{3}}\cdot \dots \cdot \left(x^{2^{k}}\right)^{m_{k}}$.

Реализации

C/C++

C: Подключение математической библиотеки (для работы со значениями NAN, INF и соответствующими функциями):

#include <math.h>

Тип Real должен быть задан как:

typedef double Real; /* Вместо double можно подставить другой вещественный тип */

C++: Подключение математической библиотеки (для работы со значениями NAN, INFINITY и сопутствующим функциями):

#include <сmath>

using namespace std;

Каждую нижеприведённую функцию следует предварять строкой:

template <typename Real>

Цикл:

Real fastPower(Real base, int exponent) {
	if (isnan(base))	/* Если основание = неопределённость: */
		return NAN;		/* Неопределённость в любой степени = неопределённость */
	if (isinf(base)) {	/* Если основание = бесконечность: */
		if (!exponent)	/* При возведении бесконечности в степень 0 */
			return NAN;	/* получается неопределённость. */
		if (exponent < 0)    				/* При возведении бесконечности в отрицательную степень получается 0, */
			return exponent & 1
				? copysign((Real)0, base)	/* условно сохраняющий знак основания (+0 или −0) при нечётной степени, */
				: (Real)0;					/* и беззнаковый при чётной. */
		return exponent & 1	/* В положительной степени бесконечность остаётся бесконечностью. */
			? base			/* В нечётной степени она сохраняет свой знак, */
			: INFINITY;		/* а в чётной становится строго положительной. */
	}
	if (base != (Real)0) { /* Сравнение вещественного числа с 0 не вполне корректно, но взято для простоты */
		/* Возведение в степень конечного ненулевого основания: */
		Real power = (Real)1;
		if (exponent < 0) {			/* Возведение в отрицательную степень */
			exponent = -exponent;	/* эквивалентно возведению в такую же положительную степень */
			base = (Real)1 / base;	/* обратного основанию числа (1 / основание). */
		}
		while (exponent) {		/* Пока текущее значение показателя степени не равно 0: */
			if (exponent & 1)	/* Если оно нечётно, */
				power *= base;	/* результат умножается на текущее значение основания. */
			exponent >>= 1;		/* Показатель степени делится на 2. */
			base *= base;		/* Основание возводится в квадрат. */
		}
		return power;
	}
	/* Возведение в степень нулевого основания: */
	if (!exponent)
		return NAN;			                /* 0 в степени 0 = неопределённость */
	if (exponent < 0)
		return copysign(INFINITY, base);	/* 0 в отрицательной степени = бесконечность */
	return exponent & 1	? base : (Real)0;	/* 0 в положительной степени = 0 (в нечётной сохраняет знак −, если он есть) */
}

Рекурсия:

static Real _fastPower(Real base, int exponent) {
	if (!exponent)
		return (Real)1;
	if (exponent & 1)
		return _fastPower(base, exponent - 1) * base;
	base = _fastPower(base, exponent >> 1);
	return base * base;
}

Real fastPower(Real base, int exponent) {
	if (isnan(base))	/* Если основание = неопределённость: */
		return NAN;		/* Неопределённость в любой степени = неопределённость */
	if (isinf(base)) {	/* Если основание = бесконечность: */
		if (!exponent)	/* При возведении бесконечности в степень 0 */
			return NAN;	/* получается неопределённость. */
		if (exponent < 0)    				/* При возведении бесконечности в отрицательную степень получается 0, */
			return exponent & 1
				? copysign((Real)0, base)	/* условно сохраняющий знак основания (+0 или −0) при нечётной степени, */
				: (Real)0;					/* и беззнаковый при чётной. */
		return exponent & 1	/* В положительной степени бесконечность остаётся бесконечностью. */
			? base			/* В нечётной степени она сохраняет свой знак, */
			: INFINITY;		/* а в чётной становится строго положительной. */
	}
	if (base != (Real)0) { /* Сравнение вещественного числа с 0 не вполне корректно, но взято для простоты */
		if (exponent < 0) {
			exponent = -exponent;
			base = (Real)1 / base;
		}
		return _fastPower(base, exponent);
	}
	/* Возведение в степень нулевого основания: */
	if (!exponent)
		return NAN;							/* 0 в степени 0 = неопределённость */
	if (exponent < 0)
		return INFINITY;					/* 0 в отрицательной степени = бесконечность */
	return exponent & 1	? base : (Real)0;	/* 0 в положительной степени = 0 (в нечётной сохраняет знак −, если он есть) */
}

C#

Вместо double может быть использован другой вещественный, а вместо int — другой целочисленный тип. Префикс @ позволяет использовать base (ключевое слово в C#) как обычный идентификатор (для единообразия с реализациями на других языках).

Цикл:

static double FastPower(double @base, int exponent)
{
	if (double.IsNaN(@base))					// Если основание = неопределённость:
		return double.NaN;						// Неопределённость в любой степени = неопределённость
	if (double.IsInfinity(@base))				// Если основание = бесконечность:
	{
		if (exponent == 0)						// При возведении бесконечности в степень 0
			return double.NaN;					// получается неопределённость.
		if (exponent < 0)    					// При возведении бесконечности в отрицательную степень получается 0,
			return (exponent & 1) != 0
				? 1 / @base						// условно сохраняющий знак основания (+0 или −0) при нечётной степени,
				: 0.0;							// и беззнаковый при чётной.
		return (exponent & 1) != 0				// В положительной степени бесконечность остаётся бесконечностью.
			? @base								// В нечётной степени она сохраняет свой знак,
			: double.PositiveInfinity;			// а в чётной становится строго положительной.
	}
	if (@base != 0.0) // Сравнение вещественного числа с 0 не вполне корректно, но взято для простоты
	// Возведение в степень конечного ненулевого основания:
	{
		double power = 1.0;
		if (exponent < 0)						// Возведение в отрицательную степень
		{
			exponent = -exponent;				// эквивалентно возведению в такую же положительную степень
			@base = 1.0 / @base;				// обратного основанию числа (1 / основание).
		}
		while (exponent > 0)					// Пока текущее значение показателя степени не равно 0:
		{
			if ((exponent & 1) != 0)			// Если оно нечётно,
				power *= @base;					// результат умножается на текущее значение основания.
			exponent >>= 1;						// Показатель степени делится на 2.
			@base *= @base;						// Основание возводится в квадрат.
		}
		return power;
	}
	// Возведение в степень нулевого основания:
	if (exponent == 0)
		return double.NaN;						// 0 в степени 0 = неопределённость
	if (exponent < 0)
		return double.PositiveInfinity;			// 0 в отрицательной степени = бесконечность
	return (exponent & 1) != 0 ? @base : 0.0;	// 0 в положительной степени = 0 (в нечётной сохраняет знак −, если он есть)
}

Рекурсия:

private static double _FastPower(double @base, int exponent)
{
	if (exponent == 0)
		return 1.0;
	if ((exponent & 1) != 0)
		return _FastPower(@base, exponent - 1) * @base;
	@base = _FastPower(@base, exponent >> 1);
	return @base * @base;
}

static double FastPower(double @base, int exponent)
{
	if (double.IsNaN(@base))					// Если основание = неопределённость:
		return double.NaN;						// Неопределённость в любой степени = неопределённость
	if (double.IsInfinity(@base))				// Если основание = бесконечность:
	{
		if (exponent == 0)						// При возведении бесконечности в степень 0
			return double.NaN;					// получается неопределённость.
		if (exponent < 0)    					// При возведении бесконечности в отрицательную степень получается 0,
			return (exponent & 1) != 0
				? 1 / @base						// условно сохраняющий знак основания (+0 или −0) при нечётной степени,
				: 0.0;							// и беззнаковый при чётной.
		return (exponent & 1) != 0				// В положительной степени бесконечность остаётся бесконечностью.
			? @base								// В нечётной степени она сохраняет свой знак,
			: double.PositiveInfinity;			// а в чётной становится строго положительной.
	}
	if (@base != 0) // Сравнение вещественного числа с 0 не вполне корректно, но взято для простоты
	{
		if (exponent < 0)						// Возведение в отрицательную степень
		{
			exponent = -exponent;				// эквивалентно возведению в такую же положительную степень
			@base = 1.0 / @base;				// обратного основанию числа (1 / основание)
		}
		return _FastPower(@base, exponent);
	}
	// Возведение в степень нулевого основания:
	if (exponent == 0)
		return double.NaN;						// 0 в степени 0 = неопределённость
	if (exponent < 0)
		return double.PositiveInfinity;			// 0 в отрицательной степени = бесконечность
	return (exponent & 1) != 0 ? @base : 0.0;	// 0 в положительной степени = 0 (в нечётной сохраняет знак −, если он есть)
}

Pascal

Delphi, FreePascal

В нижеприведённых реализациях используются особые вещественные значения Nan (неопределённость вида 0/0 или 0⁰) и Infinity (бесконечность) и сопутствующие функции. Их необходимо импортировать из модуля Math: uses Math;

Цикл:

function FastPower(base: Real; exponent: Integer): Real;
var power: Real;
begin
	if IsNaN(base) then					{ Если основание = неопределённость: }
		FastPower := NaN				{ Неопределённость в любой степени = неопределённость }
	else if IsInfinite(base) then		{ Если основание = бесконечность: }
	begin
		if exponent = 0 then			{ При возведении бесконечности в степень 0 }
			FastPower := NaN			{ получается неопределённость. }
		else if exponent < 0 then		{ При возведении бесконечности в отрицательную степень получается 0, }
		begin
			if Odd(exponent) then
				FastPower := 1 / base	{ условно сохраняющий знак основания (+0 или −0) при нечётной степени, }
			else
				FastPower := 0			{ и беззнаковый при чётной. }
		end
		else if Odd(exponent) then		{ В положительной степени бесконечность остаётся бесконечностью. }
			FastPower := base			{ В нечётной степени она сохраняет свой знак, }
		else
			FastPower := Infinity		{ а в чётной становится строго положительной. }
	end
	else if base <> 0 then { Сравнение вещественного числа с 0 не вполне корректно, но взято для простоты }
	begin
		power := 1;
		if exponent < 0 then
		begin
			exponent := -exponent;
			base := 1 / base
		end;
		while exponent > 0 do
		begin
			if Odd(exponent) then
				power := power * base;
			exponent := exponent Shr 1;
			base := Sqr(base)
		end;
		FastPower := power
	end
	{ Возведение в степень нулевого основания: }
	else if exponent = 0 then
		FastPower := Nan
	else if exponent < 0 then
		FastPower := Infinity
	else
		FastPower := 0
end;

Рекурсия:

function FastPower(base: Real; exponent: Integer): Real;
	function _fastPower(base: Real; exponent: Integer): Real;
	begin
		if exponent = 0 then
			_fastPower := 1
		else if Odd(exponent) then
			_fastPower := _fastPower(base, exponent - 1) * base
		else
			_fastPower := Sqr(_fastPower(base, exponent Shr 1))
	end;
begin
	if IsNaN(base) then					{ Если основание = неопределённость: }
		FastPower := NaN				{ Неопределённость в любой степени = неопределённость }
	else if IsInfinite(base) then		{ Если основание = бесконечность: }
	begin
		if exponent = 0 then			{ При возведении бесконечности в степень 0 }
			FastPower := NaN			{ получается неопределённость. }
		else if exponent < 0 then		{ При возведении бесконечности в отрицательную степень получается 0, }
		begin
			if Odd(exponent) then
				FastPower := 1 / base	{ условно сохраняющий знак основания (+0 или −0) при нечётной степени, }
			else
				FastPower := 0			{ и беззнаковый при чётной. }
		end
		else if Odd(exponent) then		{ В положительной степени бесконечность остаётся бесконечностью. }
			FastPower := base			{ В нечётной степени она сохраняет свой знак, }
		else
			FastPower := Infinity		{ а в чётной становится строго положительной. }
	end
	else if base <> 0 then { Сравнение вещественного числа с 0 не вполне корректно, но взято для простоты }
	begin
		if exponent < 0 then
		begin
			exponent := -exponent;
			base := 1 / base
		end;
		FastPower := _fastPower(base, exponent)
	end
	{ Возведение в степень нулевого основания: }
	else if exponent = 0 then
		FastPower := Nan
	else if exponent < 0 then
		FastPower := Infinity
	else
		FastPower := 0
end;

Python

Рекурсивная версия:

def fast_pow(x, y):
    if y == 0:
        return 1
    if y == -1:
        return 1. / x
    p = fast_pow(x, y // 2)
    p *= p
    if y % 2:
        p *= x
    return p

Итеративная версия:

def fast_pow(x, y):
    s, v, c = 1, y, x
    while (v > 0):
        if (v % 2 == 1):
            s = s * c
        v = v >> 1
        c = c * c
    return s

JavaScript

Итеративная версия:

function faststep (val, step, mod) {
	let mod = parseInt(mod);
	let s = 1; let v = step; let c = val;
	while (v != 0) {
		if (v % 2 == 1) {
            s = s * c;
			if (mod)
				s = s % mod;
		}
		v = (v - (v % 2)) / 2;
		c = c * c;
		if (mod) 
			c = c % mod;	
	}
	return s;
}

Рекурсивная версия:

function fast_pow(x, y) {
  if (y == 0) 
    return 1;
  if (y == -1)
    return 1. / x;

  let p = fast_pow(x, Math.floor(y / 2));

  p *= p;
  if (y % 2) 
    p *= x;

  return p;
}