幂

类别：算法	组件类型：函数

原型

template <class T, class Integer>
inline T power(T x, Integer n);

template <class T, class Integer, class MonoidOperation>
T power(T x, Integer n, MonoidOperation op);

描述

的第一个版本幂返回x求幂于nth 幂；也就是说，它返回x * x ... * x，其中x重复n时代。[1]如果n == 0，那么它返回identity_element(multiplies<T>()).

的第二个版本幂就像第一个版本一样，但它使用了任意 Monoid Operation 来代替multiplies<T>，返回identity_element(op)当n == 0.

重要说明: 幂不假设乘法满足交换律，但它确实依赖乘法满足结合律这一关键事实。如果您已定义*或MonoidOperation为非结合运算符，那么幂 将给您错误的结果。 [2]

定义

对类型的要求

• multiplies<T>是 Monoid Operation 的模型。
• Integer是一个整数类型。

• MonoidOperation是 Monoid Operation 的模型。
• TisMonoidOperation'的论证类型。
• n是一个整数类型。

先决条件

• n >= 0.

复杂度

示例

int main() {
  cout << "2 ** 30 = " << power(2, 30) << endl;
}

说明

[1]这是一个概念性描述幂'的返回值是什么；它不是如何幂实际实现。如果幂以这种方式实现，那么它将需要n-1乘法，这将极大地降低效率。Power使用“俄罗斯农民算法”实现，该算法仅需要O(log n)乘法。请参见高德纳 (D. E. Knuth, The Art of Computer Programming. 第 2 卷：半数值算法，艾迪生-韦斯利，1981 年) 来讨论第 4.6.3 节中问题。

[2]请参见 Monoid Operation 要求来讨论结合性。

[3]实际上，这不是可能的乘法最小次数：可以利用仅五个乘法来计算x'的第十五次方power(x, 15)使用六个。

另请参见