求幂快速算法
我们来探讨一下快速计算 $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 次乘法运算。
其中二进制算法设计是最简单的，临时变量少，耗用空间少；
因子法则需要分解因子，且存在递归问题；
加法链则需要构造出这个链，且需要的临时变量较多。 现在的问题是：真正具有实际应用价值的算法是什么？
因为我们在计算 $x^n$ 时，不能一味追求乘法次数的最小化，
我们还要考虑大数乘法的特性，比如尽可能用平方等。
比如计算 $x^55$，二进制法和因子法平方运算用到的均为5次，而加法链却仅有4次。
一般来说，我们看到的实作代码基本都是基于二进制算法的，不知另外的算法的应用场合有哪些？是模幂算法吗？ 我觉得可以混合用
用二进制法转化成小整数
对低于某范围的使用加法链 我也在考虑混合使用的问题。
但对加法链暂不考虑，因为中间临时结果不知哪些还需要。
我主要考虑什么情况下因式法占优的问题？以及如何结合二进制法利用的问题？ 如果采取混合法
我建议把数字表成大的进制
256进制就是个好主意 更大的进制可能比较适合于模幂运算，也许就是常说的“滑动窗口”法。
因为这里说的 $x^n$ 中的 $n$ 受运算规模的影响，不可能太大，甚至不足32bit，
所以采用大进制并不适用，反而需要因准备更多的临时数据而浪费空间。 难折中的 大家还可以一起来讨论这个问题：
如何用尽可能少的乘法次数（包含平方运算）快速计算：$\prod_{r=1}^{m}{x_r^r}$ ？ 也许能构造个混合链出来
比如，能否限定只保存当前的10个幂次
而用这10个幂次能达到超越二进制的效果？？
即针对确定的幂构造一个特定长度的幂序列
使得这个序列能简化计算？？
页:
[1]