|
|
我们来探讨一下快速计算 $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 次乘法运算。
|
|
发表于 2024-1-16 05:56:50
发表于 2024-1-16 05:57:08
