Викиучебник

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

Интерактивная навигация по истории
← Предыдущая правкаСледующая правка →
Содержимое удалено Содержимое добавлено
ВизуальныйВики-текст
Новые реализации на C/C+, C# и Pascal с поддержкой специальных значений NaN, Inf и подробными комментариями
Строка 3:
: <math>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} </math>.
 
=Реализации==
==[[w:C (язык программирования)|C]]/[[w:C++|C++]]==
'''C:''' Подключение математической библиотеки (для работы со значениями NAN, INF и соответствующими функциями):
'''C:''' Типы <code>Real</code> и <code>Integer</code> должны быть заданы как:
<source lang="c">#include <math.h></source>
 
Тип <code>Real</code> должен быть задан как:
<source lang="c">typedef double Real; /* Вместо double можно подставить другой вещественный тип */</source>
 
'''C++:''' Подключение математической библиотеки (для работы со значениями NAN, INFINITY и сопутствующим функциями):
<source lang="c">
#include <сmath>
typedef double Real; /* Вместо double можно подставить другой вещественный тип */
 
typedef int Integer; /* Вместо int можно подставить любой другой целочисленный тип */
using namespace std;
</source>
 
'''C++:'''Каждую Обенижеприведённую нижеприведённые функциифункцию следует предваритьпредварять строкой:
<source lang="cpp">template <typename Real, typename Integer></source>
 
Цикл:
<source lang="c">
Real fastPower(Real base, int exponent) {
#include <math.h>
if (isnan(base)) /* Если основание = неопределённость: */
 
return NAN; /* Неопределённость в любой степени = неопределённость */
Real fastPower(Real base, Integer exponent) {
if (isinf(base)) { /* Если основание = бесконечность: */
if (base == (Real)0) { /* Сравнение вещественного числа с 0 не вполне корректно, но взято для простоты */
if (!exponent) /* При возведении бесконечности в степень 0 */
if (!exponent)
return NAN; /* получается неопределённость. */
return NAN;
if (exponent < 0) /* При возведении бесконечности в отрицательную степень получается 0, */
if (exponent < (Integer)0)
return exponent & 1
return INFINITY;
? copysign((Real)0, base) /* условно сохраняющий знак основания (+0 или −0) при нечётной степени, */
return (Real)0;
: (Real)0; /* и беззнаковый при чётной. */
}
return exponent & 1 /* В положительной степени бесконечность остаётся бесконечностью. */
if (exponent < (Integer)0) {
? base /* В нечётной степени она сохраняет свой знак, */
exponent = -exponent;
: INFINITY; /* а в чётной становится строго положительной. */
base = (Real)1 / base;
}
}
if (base != (Real)0) { /* Сравнение вещественного числа с 0 не вполне корректно, но взято для простоты */
Real power = (Real)1;
/* Возведение в степень конечного ненулевого основания: */
while (exponent) {
Real power = (Real)1;
if (exponent & (Integer)1)
if (exponent < 0) { /* Возведение в отрицательную степень */
power *= base;
exponent = -exponent; /* эквивалентно возведению в такую же положительную степень */
exponent >>= (Integer)1;
base = (Real)1 / base; /* обратного основанию числа (1 / основание). */
base *= base;
}
}
while (exponent) { /* Пока текущее значение показателя степени не равно 0: */
return power;
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 (в нечётной сохраняет знак −, если он есть) */
}
</source>
Строка 43 ⟶ 63 :
Рекурсия:
<source lang="c">
static Real _fastPower(Real base, int exponent) {
#include <math.h>
if (!exponent)
return (Real)1;
if (exponent & 1)
return _fastPower(base, exponent - 1) * base;
base = _fastPower(base, exponent >> 1);
return base * base;
}
 
Real _fastPowerfastPower(Real base, Integerint exponent) {
if (isnan(base)) /* Если основание = неопределённость: */
if (!exponent)
return NAN; /* Неопределённость в любой степени = неопределённость */
return (Real)1;
if (isinf(base)) { /* Если основание = бесконечность: */
if (exponent & (Integer)1)
if (!exponent) /* При возведении бесконечности в степень 0 */
return _fastPower(base, (Integer)(exponent - 1)) * base;
return NAN; /* получается неопределённость. */
base = _fastPower(base, (Integer)(exponent >> 1));
if (exponent < 0) /* При возведении бесконечности в отрицательную степень получается 0, */
return base * base;
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 (в нечётной сохраняет знак −, если он есть) */
}
</source>
 
==[[w:C_Sharp|C#]]==
Real fastPower(Real base, Integer exponent) {
Вместо <code>double</code> может быть использован другой вещественный, а вместо <code>int</code> — другой целочисленный тип.
if (base == (Real)0) { /* Сравнение вещественного числа с 0 не вполне корректно, но взято для простоты */
Префикс <code>@</code> позволяет использовать <code>base</code> (ключевое слово в C#) как обычный идентификатор (для единообразия с реализациями на других языках).
if (!exponent)
 
return NAN;
Цикл:
if (exponent < (Integer)0)
<source lang="csharp">
return INFINITY;
static double FastPower(double @base, int exponent)
return (Real)0;
{
}
if (double.IsNaN(@base)) // Если основание = неопределённость:
if (exponent < (Integer)0) {
return double.NaN; // Неопределённость в любой степени = неопределённость
exponent = -exponent;
if (double.IsInfinity(@base)) // Если основание = бесконечность:
base = (Real)1 / base;
{
}
if (exponent == 0) // При возведении бесконечности в степень 0
return _fastPower(base, exponent);
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 (в нечётной сохраняет знак −, если он есть)
}
</source>
Рекурсия:
<source lang="csharp">
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)
== [[w:Си# (язык программирования)|Язык Си#]] ==
{
<source lang = cpp>
if (double.IsNaN(@base)) // Если основание = неопределённость:
static int Pow(int a, int b)
return double.NaN; // Неопределённость в любой степени = неопределённость
{
if (double.IsInfinity(@base)) // Если основание = бесконечность:
int re = 1;
{
while (b != 0)
if (exponent == 0) // При возведении бесконечности в степень 0
{
return double.NaN; // получается неопределённость.
if (b % 2 == 1) re *= a; a *= a; b >>= 1;
if (exponent < 0) // При возведении бесконечности в отрицательную степень получается 0,
}
return (exponent & 1) != 0
return re;
? 1 / @base // условно сохраняющий знак основания (+0 или −0) при нечётной степени,
}
: 0.0; // и беззнаковый при чётной.
static int Pow2(int a, int b)//Int32-версия
return (exponent & 1) != 0 // В положительной степени бесконечность остаётся бесконечностью.
{
? @base // В нечётной степени она сохраняет свой знак,
if (b > 2 && (a > 1 || a < -1))
: double.PositiveInfinity; // а в чётной становится строго положительной.
{
}
bool sgn = false;
if (@base != 0) // Сравнение вещественного числа с 0 не вполне корректно, но взято для простоты
if (a < 0) {if(a==-2 && b==31) return 0-0x80000000; if (b % 2 != 0) sgn = true; a = -a; }
{
if (a < 1291)
if (exponent < 0) // Возведение в отрицательную степень
{
{
if (a > 215) { if (b > 3) throw new OverflowException();
exponent = -exponent; // эквивалентно возведению в такую же положительную степень
else return sgn ? -pow[a + 406] : pow[a + 406]; }
@base = 1.0 / @base; // обратного основанию числа (1 / основание)
else
}
{
return _FastPower(@base, exponent);
if (ind[a] + b - 3 >= ind[a + 1]) throw new OverflowException();
}
else return sgn ? -pow[ind[a] + b] : pow[ind[a] + b];
// Возведение в степень нулевого основания:
}
if (exponent == 0)
}
return double.NaN; // 0 в степени 0 = неопределённость
else throw new OverflowException();
if (exponent < 0)
}
return double.PositiveInfinity; // 0 в отрицательной степени = бесконечность
else
return (exponent & 1) != 0 ? @base : 0.0; // 0 в положительной степени = 0 (в нечётной сохраняет знак −, если он есть)
{
}
if (b == 2) return checked(a * a);
if (b == 1) return a;
if (b == 0) return 1;//0^0 тоже принято за 1
if (a == 1) return 1;
if (a == 0 && b > 0) return 0;
if (a == -1) return b % 2 == 0 ? 1 : -1;
throw new InvalidOperationException();//деление на 0 или рациональное число
}
}
значения массива Ind
int z = 0; Console.Write("0,0,-3,");
for (int i = 3; i < 31; i++) z++; Console.Write((z - 3) + ",");
for (int i = 3; i < 20; i++) z++; Console.Write((z - 3) + ",");
for (int i = 3; i < 16; i++) z++; Console.Write((z - 3) + ",");
for (int i = 3; i < 14; i++) z++; Console.Write((z - 3) + ",");
for (int x = 6; x < 8; x++) { for (int i = 3; i < 12; i++) { z++; } Console.Write((z - 3) + ","); }
for (int i = 3; i < 11; i++) z++; Console.Write((z - 3) + ",");
for (int x = 9; x < 11; x++) { for (int i = 3; i < 10; i++) { z++; } Console.Write((z - 3) + ","); }
for (int x = 11; x < 15; x++) { for (int i = 3; i < 9; i++) { z++; } Console.Write((z - 3) + ","); }
for (int x = 15; x < 22; x++) { for (int i = 3; i < 8; i++) { z++; } Console.Write((z - 3) + ","); }
for (int x = 22; x < 36; x++) { for (int i = 3; i < 7; i++) { z++; } Console.Write((z - 3) + ","); }
for (int x = 36; x < 74; x++) { for (int i = 3; i < 6; i++) { z++; } Console.Write((z - 3) + ","); }
for (int x = 74; x < 215; x++) { for (int i = 3; i < 5; i++) { z++; } Console.Write((z - 3) + ","); }
значения массива pow
for (int i = 3; i < 31; i++) Console.Write(Pow(2, i) + ",");
for (int i = 3; i < 20; i++) Console.Write(Pow(3, i)+",");
for (int i = 3; i < 16; i++) Console.Write(Pow(4, i) + ",");
for (int i = 3; i < 14; i++) Console.Write(Pow(5, i) + ",");
for (int x = 6; x < 8; x++) for (int i = 3; i < 12; i++) Console.Write(Pow(x, i) + ",");
for (int i = 3; i < 11; i++) Console.Write(Pow(8, i) + ",");
for (int x = 9; x < 11; x++) for (int i = 3; i < 10; i++) Console.Write(Pow(x, i) + ",");
for (int x = 11; x < 15; x++) for (int i = 3; i < 9; i++) Console.Write(Pow(x, i) + ",");
for (int x = 15; x < 22; x++) for (int i = 3; i < 8; i++) Console.Write(Pow(x, i) + ",");
for (int x = 22; x < 36; x++) for (int i = 3; i < 7; i++) Console.Write(Pow(x, i) + ",");
for (int x = 36; x < 74; x++) for (int i = 3; i < 6; i++) Console.Write(Pow(x, i) + ",");
for (int x = 74; x < 216; x++) for (int i = 3; i < 5; i++) Console.Write(Pow(x, i) + ",");
for (int x = 216; x < 1291; x++) for (int i = 3; i < 4; i++) Console.Write(Pow(x, i) + ",");
</source>
 
== [[w:Паскаль (язык программирования)|ПаскальPascal]] ==
===[[w:Delphi|Delphi]], [[w:FreePascal|FreePascal]]===
<source lang = pascal>
В нижеприведённых реализациях используются особые вещественные значения <code>Nan</code> (неопределённость вида 0/0 или 0⁰) и <code>Infinity</code> (бесконечность) и сопутствующие функции. Их необходимо импортировать из модуля Math:
//Синтаксис - Delphi
<code>uses Math;</code>
function power(Val, Pwr: integer): integer; {возведение числа Val в степень Pwr}
begin
if Val = 0 then
Result := 0
else
if Pwr = 0 then
Result := 1
else
if Pwr = 1 then
Result := Val
else
begin
Result := 1;
while Pwr > 0 do
begin
if (Pwr and 1) = 1 then
Result := Result * Val;
 
Цикл:
Pwr := Pwr shr 1;
<source lang="pascal">
Val := Val * Val;
function FastPower(base: Real; exponent: Integer): Real;
end;
var power: Real;
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
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;
</source>
Рекурсия:
 
<source lang="pascal">
 
function FastPower(base: Real; exponent: Integer): Real;
<source lang=pascal>
function _fastPower(base: Real; exponent: Integer): Real;
//возведение в любую степень, даже под корень (корень степени N = степень 1/N)
begin
function power(Val,Pwr:Real):Real; {возведение числа Val в степень Pwr}
if exponent = 0 then
begin
_fastPower := 1
Power:=Exp(Pwr*Ln(Val));
else if Odd(exponent) then
end;
_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;
</source>
 
Источник — https://ru.wikibooks.org/wiki/Реализации_алгоритмов/Быстрое_возведение_в_степень