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

Переработаны реализации на C/C++
(Переработаны реализации на C/C++)
: <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++]] ==
<source lang = cpp>
'''C:''' Типы <code>Real</code> и <code>Integer</code> должны быть заданы как:
int power(int t, int k) // возведение t в степень k
<source lang = cpp"c">
{
typedef double Real; /* Вместо double можно подставить другой вещественный тип */</source>
int res = 1;
typedef int Integer; /* Вместо int можно подставить любой другой целочисленный тип */</source>
while (k)
 
{
'''C++:''' Обе нижеприведённые функции следует предварить строкой:
if (k & 1)
<source lang="cpp">template <typename Real, typename Integer></source>
res *= t;
 
t *= t;
Цикл:
k >>= 1;
<source lang = cpp"c">
}
#include <math.h>
return res;
 
Real fastPower(Real base, Integer exponent) {
if (base == (Real)0) { /* Сравнение вещественного числа с 0 не вполне корректно, но взято для простоты */
if (k & 1!exponent)
return NAN;
if (exponent < (Integer)0)
return INFINITY;
if (n == 0) return 1(Real)0;
{}
if (exponent < (Integer)0) {
exponent = -exponent;
base = (Real)1 / base;
}
Real power = (Real)1;
while (kexponent) {
if (exponent & (Integer)1)
respower *= tbase;
exponent >>= (Integer)1;
base *= base;
}
return respower;
}
</source>
 
Рекурсия:
== [[w:C++|C++]] ==
<source lang="c">
Рекурсивная реализация:
#include <math.h>
<source lang = cpp>
 
int binpow (int a, int n) {
Real _fastPower(Real base, Integer exponent) {
if (n == 0) return 1;
if (!exponent)
if (n % 2 == 1) return binpow (a, n-1) * a;
return (Real)1;
else {
if int(exponent b = binpow& (a, n/2Integer)1);
return b_fastPower(base, (Integer)(exponent - 1)) * bbase;
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;
else {}
if (exponent < (Integer)0) {
exponent = -exponent;
base = (Real)1 / base;
}
return _fastPower(base, exponent);
}
</source>
74

правки