Реализации алгоритмов/Быстрое возведение в степень: различия между версиями
DannyS712 (обсуждение | вклад) м <source> -> <syntaxhighlight> (phab:T237267) |
|||
Строка 6: | Строка 6: | ||
==[[w:C (язык программирования)|C]]/[[w:C++|C++]]== |
==[[w:C (язык программирования)|C]]/[[w:C++|C++]]== |
||
'''C:''' Подключение математической библиотеки (для работы со значениями NAN, INF и соответствующими функциями): |
'''C:''' Подключение математической библиотеки (для работы со значениями NAN, INF и соответствующими функциями): |
||
< |
<syntaxhighlight lang="c">#include <math.h></syntaxhighlight> |
||
Тип <code>Real</code> должен быть задан как: |
Тип <code>Real</code> должен быть задан как: |
||
< |
<syntaxhighlight lang="c">typedef double Real; /* Вместо double можно подставить другой вещественный тип */</syntaxhighlight> |
||
'''C++:''' Подключение математической библиотеки (для работы со значениями NAN, INFINITY и сопутствующим функциями): |
'''C++:''' Подключение математической библиотеки (для работы со значениями NAN, INFINITY и сопутствующим функциями): |
||
< |
<syntaxhighlight lang="c"> |
||
#include <сmath> |
#include <сmath> |
||
using namespace std; |
using namespace std; |
||
</syntaxhighlight> |
|||
</source> |
|||
Каждую нижеприведённую функцию следует предварять строкой: |
Каждую нижеприведённую функцию следует предварять строкой: |
||
< |
<syntaxhighlight lang="cpp">template <typename Real></syntaxhighlight> |
||
Цикл: |
Цикл: |
||
< |
<syntaxhighlight lang="c"> |
||
Real fastPower(Real base, int exponent) { |
Real fastPower(Real base, int exponent) { |
||
if (isnan(base)) /* Если основание = неопределённость: */ |
if (isnan(base)) /* Если основание = неопределённость: */ |
||
Строка 59: | Строка 59: | ||
return exponent & 1 ? base : (Real)0; /* 0 в положительной степени = 0 (в нечётной сохраняет знак −, если он есть) */ |
return exponent & 1 ? base : (Real)0; /* 0 в положительной степени = 0 (в нечётной сохраняет знак −, если он есть) */ |
||
} |
} |
||
</syntaxhighlight> |
|||
</source> |
|||
Рекурсия: |
Рекурсия: |
||
< |
<syntaxhighlight lang="c"> |
||
static Real _fastPower(Real base, int exponent) { |
static Real _fastPower(Real base, int exponent) { |
||
if (!exponent) |
if (!exponent) |
||
Строка 100: | Строка 100: | ||
return exponent & 1 ? base : (Real)0; /* 0 в положительной степени = 0 (в нечётной сохраняет знак −, если он есть) */ |
return exponent & 1 ? base : (Real)0; /* 0 в положительной степени = 0 (в нечётной сохраняет знак −, если он есть) */ |
||
} |
} |
||
</syntaxhighlight> |
|||
</source> |
|||
==[[w:C_Sharp|C#]]== |
==[[w:C_Sharp|C#]]== |
||
Строка 107: | Строка 107: | ||
Цикл: |
Цикл: |
||
< |
<syntaxhighlight lang="csharp"> |
||
static double FastPower(double @base, int exponent) |
static double FastPower(double @base, int exponent) |
||
{ |
{ |
||
Строка 149: | Строка 149: | ||
return (exponent & 1) != 0 ? @base : 0.0; // 0 в положительной степени = 0 (в нечётной сохраняет знак −, если он есть) |
return (exponent & 1) != 0 ? @base : 0.0; // 0 в положительной степени = 0 (в нечётной сохраняет знак −, если он есть) |
||
} |
} |
||
</syntaxhighlight> |
|||
</source> |
|||
Рекурсия: |
Рекурсия: |
||
< |
<syntaxhighlight lang="csharp"> |
||
private static double _FastPower(double @base, int exponent) |
private static double _FastPower(double @base, int exponent) |
||
{ |
{ |
||
Строка 194: | Строка 194: | ||
return (exponent & 1) != 0 ? @base : 0.0; // 0 в положительной степени = 0 (в нечётной сохраняет знак −, если он есть) |
return (exponent & 1) != 0 ? @base : 0.0; // 0 в положительной степени = 0 (в нечётной сохраняет знак −, если он есть) |
||
} |
} |
||
</syntaxhighlight> |
|||
</source> |
|||
==[[w:Паскаль (язык программирования)|Pascal]]== |
==[[w:Паскаль (язык программирования)|Pascal]]== |
||
Строка 202: | Строка 202: | ||
Цикл: |
Цикл: |
||
< |
<syntaxhighlight lang="pascal"> |
||
function FastPower(base: Real; exponent: Integer): Real; |
function FastPower(base: Real; exponent: Integer): Real; |
||
var power: Real; |
var power: Real; |
||
Строка 249: | Строка 249: | ||
FastPower := 0 |
FastPower := 0 |
||
end; |
end; |
||
</syntaxhighlight> |
|||
</source> |
|||
Рекурсия: |
Рекурсия: |
||
< |
<syntaxhighlight lang="pascal"> |
||
function FastPower(base: Real; exponent: Integer): Real; |
function FastPower(base: Real; exponent: Integer): Real; |
||
function _fastPower(base: Real; exponent: Integer): Real; |
function _fastPower(base: Real; exponent: Integer): Real; |
||
Строка 298: | Строка 298: | ||
FastPower := 0 |
FastPower := 0 |
||
end; |
end; |
||
</syntaxhighlight> |
|||
</source> |
|||
== [[w:Python|Python]] == |
== [[w:Python|Python]] == |
||
< |
<syntaxhighlight lang = python> |
||
def fast_pow(x, y): |
def fast_pow(x, y): |
||
if y == 0: |
if y == 0: |
||
Строка 311: | Строка 311: | ||
if y % 2: |
if y % 2: |
||
p *= x |
p *= x |
||
return p</ |
return p</syntaxhighlight> |
||
== [[w:JavaScript (язык программирования)|JavaScript]] == |
== [[w:JavaScript (язык программирования)|JavaScript]] == |
||
< |
<syntaxhighlight lang=javascript> |
||
function faststep (val, step, mod) { |
function faststep (val, step, mod) { |
||
mod = parseInt(mod); |
mod = parseInt(mod); |
||
Строка 343: | Строка 343: | ||
return s; |
return s; |
||
} |
} |
||
</syntaxhighlight> |
|||
</source> |
|||
{{BookCat}} |
{{BookCat}} |
Версия от 15:58, 16 апреля 2020
Используется представление числа xm:
- .
Реализации
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
JavaScript
function faststep (val, step, mod) {
mod = parseInt(mod);
s = 1; v = step; c = val;
while (v != 0) {
flag = 0;
if (v%2 == 1) {
if (!mod)
s = s*c;
else
s = (s*c) % mod;
v = (v-1)/2;
if (!mod)
c = c*c;
else
c = (c*c) % mod;
flag = 1;
}
else {
v = v/2;
}
if (!flag)
if (!mod)
c = c*c;
else
c = (c*c) % mod;
}
return s;
}