1.快速求幂算法

在这篇文章我会展示怎样通过求一个数的幂的基本思路，来引导我们发现一些抽象的东西比如半群和含幺半群。

有一个很有名的对一个数求幂的算法,也就是说,求一个数x的n次方或者这样简单表示：x^n。Donald Knuth在TAOCP的4.63节 求幂值中提出这个算法。

这个算法很简单的实现就是x乘以自己n次，但是在这里当然会提供一种比这种方式更快的算法。正在谈论的算法通常被称作二进制法(binary method)、梯度求幂(the powering ladder)或者反复平方法(repeated-squaring algorithm)

假设我们想计算2^23，在这里x = 2，n = 23，这个算法首先把23表示成二进制的形式10111。扫描这个二进制数(10111)每当遇到0或1，则相应的求x的平方或者乘以x。

这个方法有一个问题就是它扫描二进制表示的数是从左到右进行的，但是对于计算机通常以相反的方向能够更容易实现，因此Knuth提出一个替代的算法。

一个出自TAOCP的4.63节的算法A的简单实现如下：

这个函数需要两个整数，$x和$n然后返回$x的$n次幂作为结果。

首先创建一个辅助变量$y并且初始化为1，把它作为乘法的主体。

然后函数在每次循环迭代的时候扫描$n的二进制表示的数。如果遇到1则$y乘上$x，然后赋值回$y。每次循环都会计算$x的平方，并且把它赋值回$x。

遇到1意味着当前$n的值不能被2整除，换句话说就是，$n % 2 == 1。

同样的每次循环$n都会折半，然后向下取整得到结果。当$n等于0的时候，我们结束循环并且返回$y的值。

函数power能够这样被调用:

我能想象你现在就像这个gif中的男孩。

尽管这个算法看起来像一个 “呵呵，真有意思” (无语了，你别说了，我根本不关心)的故事，实际上当它用来计算非常的大数时时十分高效的。例如有很多的素数测试算法都是依赖这个算法的不同变式。

2.增加一些抽象

到目前为止还没有什么意想不到的事情发生，但是如果我们注意到求一个数的幂实际上和一个数自乘多次是等价的，我们也可以看到乘法实际上等价于自加多次。举个例子2 * 5能够像这样被计算2 + 2 + 2 + 2 + 2。

我们能把这个算法转换成一种更普遍的形式使它能同样应用在乘法还有加法上吗?当然可以，我们仅仅需要改变几样东西。

在当前实现中，我们创建$y作为乘法的主体，并设置为1。如果我们想把算法用在加法上，我们需要把$y设置为0。因此我们仅需要改变函数的单位元素的值。

第二步要提供一个函数给我们的算法，它能够作乘法或者加法。为了实现这个目的我们会传递一个担当二元运算的函数。例如：一个需要两个参数的函数。这个函数需要遵循以下的规则。必须满足：a·（ b · c ） = (a · b ) · c。还要求返回结果的类型必须和两个输入参数的类型一致。

幸运的是加法和乘法都满足结合律，因此我们能够仅在一个函数中包含他们然后把它传递给我们的power算法。

这里是这个算法新的实现：

我们能够像这样调用它:

记住传递进我们算法的运算必须是可结合的,举个例子,减法不能被用在这里由于10 - ( 5 - 3) = 8但是(10 - 5 ) - 3 = 2。

3.附加更抽象的概念

从数学的角度说这个算法能够在任何满足结合律的代数结构中有效(在这个案例中就是整数的乘法和加法)，换言之，它能够用在半群中，引用一本关于群论的书。