通过2的幂进行计算
编辑
这是用Ruby写的上述算法的非递归实现。
由于低级语言会将 n=n/2 隐式向0取整，n=n-1 对那些语言来说，就是冗余的步骤了。
n[0]是n的二进制表示的最右边的位，所以如果它是1，则该数是奇数，如果它是零，则该数是偶数。它也是以2为模n的余数。
def power(x,n)
result = 1
while n.nonzero?
if n[0].nonzero?
result *= x
n -= 1
end
x *= x
n /= 2
end
return result
end
运行实例：计算 310
编辑
parameter x = 3
parameter n = 10
result := 1
Iteration 1
n = 10 -> n is even
x := x2 = 32 = 9
n := n / 2 = 5
Iteration 2
n = 5 -> n is odd
-> result := result * x = 1 * x = 1 * 32 = 9
n := n - 1 = 4
x := x2 = 92 = 34 = 81
n := n / 2 = 2
Iteration 3
n = 2 -> n is even
x := x2 = 812 = 38 = 6561
n := n / 2 = 1
Iteration 4
n = 1 -> n is odd
-> result := result * x = 32 * 38 = 310 = 9 * 6561 = 59049
n := n - 1 = 0
return result
运行实例：计算 310
编辑
result := 3
bin := "1010"
Iteration for digit 2:
result := result2 = 32 = 9
1010bin - Digit equals "0"
Iteration for digit 3:
result := result2 = (32)2 = 34 = 81
1010bin - Digit equals "1" --> result := result*3 = (32)2*3 = 35 = 243
Iteration for digit 4:
result := result2 = ((32)2*3)2 = 310 = 59049
1010bin - Digit equals "0"
return result
JavaScript-Demonstration: http://home.mnet-online.de/wzwz.de/temp/ebs/en.htm （页面存档备份，存于互联网档案馆）
幂的乘积的计算
编辑
平方求幂也可用于计算2个或多个幂的乘积。
如果基础群或半群是可交换的，那么常常可以通过同时计算乘积来减少乘法的次数。
例子
编辑
式子 a7×b5 可以分三步计算：
((a)2×a)2×a （计算 a7 需要四次乘法）
((b)2)2×b （计算 b5 需要三次乘法）
(a7)×(b5) （计算二者乘积需要一次乘法）
所以总共需要八次乘法。
更快的解法是同时计算这两个幂
((a×b)2×a)2×a×b
总共只需要6次乘法。注意 a×b 计算了两次；结果可以在第一次计算后存储，这将乘法计数减少到5次。
有数字的例子：
27×35 = ((2×3)2×2)2×2×3 = (62×2)2×6 = 722×6 = 31,104
如果至少有两个指数大于1的话，同时计算幂就会比单独计算减少乘法次数。
使用变换
编辑
如果表达式在计算前进行变换，上面的例子 a7×b5 也可以只用5次乘法就计算出来：
a7×b5 = a2×(ab)5 其中 ab := a×b
ab := a×b（一次乘法）
a2×(ab)5 = ((ab)2×a)2×ab（四次乘法）
这个变换可以推广成下面的方案：
对于计算 aA×bB×...×mM×nN
首先：定义 ab := a×b, abc = ab×c, ...
然后：计算变换后的表达式 aA−B×abB−C×...×abc..mM−N×abc..mnN
在计算之前进行变换通常会减少乘法计数，但在某些情况下也会增加计数（请参见下面最后一个示例），因此在使用变换后的表达式进行计算之前，最好检查一下乘法的次数。
例子
编辑
对于下面的表达式，表中显示了分开计算每个幂，在不进行变换的情况下同时进行计算，以及在变换后同时进行计算的乘法次数。
例子
a7×b5×c3
a5×b5×c3
a7×b4×c1
分开计算
[((a)2×a)2×a] × [((b)2)2×b] × [(c)2×c]（11次乘法）
[((a)2)2×a] × [((b)2)2×b] × [(c)2×c]（10次乘法）
[((a)2×a)2×a] × [((b)2)2] × [c]（8次乘法）
同时计算
((a×b)2×a×c)2×a×b×c（8次乘法）
((a×b)2×c)2×a×b×c（7次乘法）
((a×b)2×a)2×a×c（6次乘法）
变换
a := 2 ab := a×b abc := ab×c（2次乘法）
a := 2 ab := a×b abc := ab×c（2次乘法）
a := 2 ab := a×b abc := ab×c（2次乘法）
之后的计算
(a×ab×abc)2×abc（4次乘法 ⇒ 总共6次）
(ab×abc)2×abc（3次乘法 ⇒ 总共5次）
(a×ab)2×a×ab×abc（5次乘法 ⇒ 总共7次）