Реализации алгоритмов/Быстрое возведение в степень: различия между версиями
Содержимое удалено Содержимое добавлено
Переработаны реализации на C/C++ |
|||
Строка 3: | Строка 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>. |
: <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:''' Типы <code>Real</code> и <code>Integer</code> должны быть заданы как: |
|||
int power(int t, int k) // возведение t в степень k |
|||
⚫ | |||
{ |
|||
typedef double Real; /* Вместо double можно подставить другой вещественный тип */</source> |
|||
int res = 1; |
|||
typedef int Integer; /* Вместо int можно подставить любой другой целочисленный тип */</source> |
|||
⚫ | |||
⚫ | |||
'''C++:''' Обе нижеприведённые функции следует предварить строкой: |
|||
⚫ | |||
<source lang="cpp">template <typename Real, typename Integer></source> |
|||
⚫ | |||
t *= t; |
|||
Цикл: |
|||
k >>= 1; |
|||
⚫ | |||
⚫ | |||
#include <math.h> |
|||
⚫ | |||
Real fastPower(Real base, Integer exponent) { |
|||
if (base == (Real)0) { /* Сравнение вещественного числа с 0 не вполне корректно, но взято для простоты */ |
|||
⚫ | |||
return NAN; |
|||
if (exponent < (Integer)0) |
|||
return INFINITY; |
|||
⚫ | |||
⚫ | |||
if (exponent < (Integer)0) { |
|||
exponent = -exponent; |
|||
base = (Real)1 / base; |
|||
⚫ | |||
Real power = (Real)1; |
|||
⚫ | |||
if (exponent & (Integer)1) |
|||
⚫ | |||
exponent >>= (Integer)1; |
|||
base *= base; |
|||
⚫ | |||
⚫ | |||
} |
} |
||
</source> |
</source> |
||
Рекурсия: |
|||
== [[w:C++|C++]] == |
|||
<source lang="c"> |
|||
Рекурсивная реализация: |
|||
#include <math.h> |
|||
⚫ | |||
int binpow (int a, int n) { |
|||
Real _fastPower(Real base, Integer exponent) { |
|||
⚫ | |||
if (!exponent) |
|||
if (n % 2 == 1) return binpow (a, n-1) * a; |
|||
return (Real)1; |
|||
else { |
|||
if (exponent & (Integer)1) |
|||
return |
return _fastPower(base, (Integer)(exponent - 1)) * base; |
||
base = _fastPower(base, (Integer)(exponent >> 1)); |
|||
⚫ | |||
return base * base; |
|||
} |
|||
Real fastPower(Real base, Integer exponent) { |
|||
if (base == (Real)0) { /* Сравнение вещественного числа с 0 не вполне корректно, но взято для простоты */ |
|||
if (!exponent) |
|||
return NAN; |
|||
if (exponent < (Integer)0) |
|||
return INFINITY; |
|||
return (Real)0; |
|||
⚫ | |||
if (exponent < (Integer)0) { |
|||
exponent = -exponent; |
|||
base = (Real)1 / base; |
|||
} |
|||
return _fastPower(base, exponent); |
|||
} |
} |
||
</source> |
</source> |
Версия от 19:42, 5 августа 2019
Используется представление числа xm:
- .
Реализации=
C/C++
C: Типы Real
и Integer
должны быть заданы как:
typedef double Real; /* Вместо double можно подставить другой вещественный тип */
typedef int Integer; /* Вместо int можно подставить любой другой целочисленный тип */</source>
C++: Обе нижеприведённые функции следует предварить строкой:
template <typename Real, typename Integer>
Цикл:
#include <math.h>
Real fastPower(Real base, Integer exponent) {
if (base == (Real)0) { /* Сравнение вещественного числа с 0 не вполне корректно, но взято для простоты */
if (!exponent)
return NAN;
if (exponent < (Integer)0)
return INFINITY;
return (Real)0;
}
if (exponent < (Integer)0) {
exponent = -exponent;
base = (Real)1 / base;
}
Real power = (Real)1;
while (exponent) {
if (exponent & (Integer)1)
power *= base;
exponent >>= (Integer)1;
base *= base;
}
return power;
}
Рекурсия:
#include <math.h>
Real _fastPower(Real base, Integer exponent) {
if (!exponent)
return (Real)1;
if (exponent & (Integer)1)
return _fastPower(base, (Integer)(exponent - 1)) * base;
base = _fastPower(base, (Integer)(exponent >> 1));
return base * base;
}
Real fastPower(Real base, Integer exponent) {
if (base == (Real)0) { /* Сравнение вещественного числа с 0 не вполне корректно, но взято для простоты */
if (!exponent)
return NAN;
if (exponent < (Integer)0)
return INFINITY;
return (Real)0;
}
if (exponent < (Integer)0) {
exponent = -exponent;
base = (Real)1 / base;
}
return _fastPower(base, exponent);
}
Язык Си#
static int Pow(int a, int b)
{
int re = 1;
while (b != 0)
{
if (b % 2 == 1) re *= a; a *= a; b >>= 1;
}
return re;
}
static int Pow2(int a, int b)//Int32-версия
{
if (b > 2 && (a > 1 || a < -1))
{
bool sgn = false;
if (a < 0) {if(a==-2 && b==31) return 0-0x80000000; if (b % 2 != 0) sgn = true; a = -a; }
if (a < 1291)
{
if (a > 215) { if (b > 3) throw new OverflowException();
else return sgn ? -pow[a + 406] : pow[a + 406]; }
else
{
if (ind[a] + b - 3 >= ind[a + 1]) throw new OverflowException();
else return sgn ? -pow[ind[a] + b] : pow[ind[a] + b];
}
}
else throw new OverflowException();
}
else
{
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) + ",");
Паскаль
//Синтаксис - Delphi
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;
Val := Val * Val;
end;
end;
end;
//возведение в любую степень, даже под корень (корень степени N = степень 1/N)
function power(Val,Pwr:Real):Real; {возведение числа Val в степень Pwr}
begin
Power:=Exp(Pwr*Ln(Val));
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;
}