求幂快速算法

gxqcn

我们来探讨一下快速计算 $x^n$ 的算法，其中 $x$ 和 $n$  都是给定的正整数，要求结果完全精确。

逐次乘的算法首先是被排除的，因为它不是快速算法，这里的快速算法要求用尽可能少的乘法次数（包含有平方的次数）来得到最终结果。

在 Donald E.Knuth 所著述的《计算机程序涉及艺术 Vol2 半数值算法》提到了以下几种算法：

• 二进制算法
  一般又分为将指数从左至右扫描和从右至左扫描两种模式。
  与书中的观点不同的是，我本人更倾向于用前者，因为乘法时所用的乘数可以固定为原底数。
  
  
• 因子法
  它是以 $n$ 的因子分解为基础的。
  如果 $n=pq$，其中 $p$ 是 $n$ 的最小素因子，而且 $q>1$，则我们可以首先计算 $x^p$ 而后对这个量作乘方到 $q$ 次幂来计算 $x^n$.
  如果 $n$ 为素数，则我们可以计算 $x^(n-1)$ 并乘以 $x$；当然，如果 $n=1$，我们全然无须进行计算。
  对于任何给定的 $n$，反复应用这些规则，就可以完成计算 $x^n$ 的过程。
  
  它的算法步骤为：
  1、$n==1 ?$ 是，则返回；
  2、$n$为素数吗？是，则计算 $y=x^(n-1)$，然后再计算 $y*x$；
  3、取 $n$ 的最小素因子 $p$，先计算 $y=x^p$，而后再计算 $y^(n/p)$
  
  例如，要计算 $x^55$，我们首先计算 $y=x^5=x^4x=(x^2)^2x$；然后我们构造 $y^11=y^10y=(y^2)^5y$
  全过程需要8次乘法，而二进制法需要9次。
  平均来说，因子法比二进制法更好些，但也有一些例外，比如 n=33 是最小的例外。
  
  
• 加法链
  它是构造一个最短的递增序列，首项为1，末项为n，除了首项1以外，其它各项均可由其前面的某两项之和表达（“某两项”允许自身重复）。
  不如要计算 $x^55$，可构造 ${ 1, 2, 3, 6, 12, 15, 27, 54, 55 }$，序长为 9，代表需要 8 次乘法运算。
  
  

gxqcn

其中二进制算法设计是最简单的，临时变量少，耗用空间少；
因子法则需要分解因子，且存在递归问题；
加法链则需要构造出这个链，且需要的临时变量较多。

gxqcn

现在的问题是：真正具有实际应用价值的算法是什么？

因为我们在计算 $x^n$ 时，不能一味追求乘法次数的最小化，
我们还要考虑大数乘法的特性，比如尽可能用平方等。

比如计算 $x^55$，二进制法和因子法平方运算用到的均为5次，而加法链却仅有4次。

一般来说，我们看到的实作代码基本都是基于二进制算法的，不知另外的算法的应用场合有哪些？是模幂算法吗？

无心人

我觉得可以混合用

用二进制法转化成小整数
对低于某范围的使用加法链

gxqcn

我也在考虑混合使用的问题。

但对加法链暂不考虑，因为中间临时结果不知哪些还需要。

我主要考虑什么情况下因式法占优的问题？以及如何结合二进制法利用的问题？

无心人

如果采取混合法
我建议把数字表成大的进制

256进制就是个好主意

gxqcn

更大的进制可能比较适合于模幂运算，也许就是常说的“滑动窗口”法。

因为这里说的 $x^n$ 中的 $n$ 受运算规模的影响，不可能太大，甚至不足32bit，
所以采用大进制并不适用，反而需要因准备更多的临时数据而浪费空间。

无心人

难折中的

gxqcn

大家还可以一起来讨论这个问题：

如何用尽可能少的乘法次数（包含平方运算）快速计算：$\prod_{r=1}^{m}{x_r^r}$ ？

无心人

也许能构造个混合链出来

比如，能否限定只保存当前的10个幂次
而用这10个幂次能达到超越二进制的效果？？

即针对确定的幂构造一个特定长度的幂序列
使得这个序列能简化计算？？