Stein 算法
| Stein算法 | |
|---|---|
| 术语名称 | Stein算法 |
| 英语名称 | Stein's algorithm |
| 别名 | 二进制最大公因数算法, binary Euclidean algorithm, binary GCD algorithm |
Stein 算法(Stein's algorithm)，是辗转相除法在进行大数运算时的一种工程实现。
主要思想是由于大数运算的高精度带余除法是一个复杂度较高的计算，约去只在一个操作数中含有的质因数可以方便地进行简化。由于硬件上用移位代替除法是常见且高效的手段，且很容易判定是否被 2 整除，通常的优化中仅对 2 进行处理，单步内也用减法代替辗转相除单步的带余除法转化成 2 的倍数，因此也称为二进制最大公因数算法(binary GCD algorithm)。
Stein 算法基本只用于大数运算中。在常见长度上，普通辗转相除法步数更少，一般来说执行更快；在大数运算，或者早期缺少简单除法能力的硬件环境中，由于除法代价更高， Stein 算法可以避免昂贵运算，从而获得显著的性能提升。
算法
原理
[math]\displaystyle{ \operatorname{gcd}(a, b) = \begin{cases} 2 \operatorname{gcd}\left(\frac{a}{2}, \frac{b}{2}\right) &, 2 \mid a, 2 \mid b \\ \operatorname{gcd}\left(\frac{a}{2}, b\right) &, 2 \mid a, 2 \not\mid b \\ \operatorname{gcd}\left(a, \frac{b}{2}\right) &, 2 \not\mid a, 2 \mid b \\ \operatorname{gcd}\left(a, a - b\right) &, 2 \not\mid a, 2 \not\mid b \end{cases} }[/math]
伪代码
过程 Stein算法
别名 steins_algorithm
参数 a, b : 整数 // 被求最大公因数的两个数
返回 : 自然数 // 最大公因数
令 r ← 1
令 a ← |a|, b ← |b|
循环
当 b ≠ 0 时
执行
依 2 | a 和 2 | b 的真值选择分支
满足 2 | a 且 2 | b 则
令 a ← a / 2, b ← b / 2, r ← 2 r
满足 2 | a 且 非 2 | b 则
令 a ← a / 2
满足 非 2 | a 且 2 | b 则
令 b ← b / 2
满足 非 2 | a 且 非 2 | b 则
如果 a > b 那么
令 a ← (a - b) / 2 ❶
否则
令 b ← (b - a) / 2 ❶
结束分支
继续循环
令 r ← r a
返回 r❶ 此处与上述原理表述略有差别，为了更快结束算法，应保留差和较小数，而且可以确认差是偶数、较小数是奇数，可以直接按照一奇一偶的步骤直接把差除以 2 。
实现中，判断被 2 整除使用按位与运算实现，除以 2 使用右移运算， r 也处理成左移运算，此外只有减法运算，和普通的运算相同。
琐事
九章算术中的类似算法
高中教学中，《九章算术・方田》中对“约分”问题的算法中，第二步提及的更相减损作为“更相减损术”单独提出，只强调原本更相减损的步骤。但更相减损只是原书算法的第二步，第一步是类似 Stein 算法中不断除以 2 的步骤。与 Stein 算法的区别是不会对每个循环都进行约去 2 的操作。
约分按：约分者，物之数量，不可悉全，必以分言之。分之为数，繁则难用。设有四分之二者，繁而言之，亦可为八分之四；约而言之，则二分之一也。虽则异词，至于为数，亦同归尔。法实相推，动有参差，故为术者，先治诸分。
术曰：可半者半之；不可半者，副置分母子之数，以少减多，更相减损，求其等也。以等数约之。等数约之，即除也。其所以相减者，皆等数之重叠，故以等数约之。
——《九章算术》 西汉 ・《九章算术注》 魏 刘徽 [1]