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