查看“︁Stein 算法”︁的源代码

[[分类:整除理论]]
[[分类:数论算法]]
{{InfoBox
|name=Stein算法
|eng_name=Stein's algorithm
|aliases=binary Euclidean algorithm,binary GCD algorithm
}}
{{非标准翻译}}
<ins>Stein</ins>算法('''Stein's algorithm''')，是[[辗转相除法]]在进行[[大数运算]]时的一种工程实现。

主要思想是由于大数的高精度带余除法是一个复杂度较高的计算，约去只在一个操作数中含有的质因数。由于硬件上用移位代替除法是常见且高效的手段，且容易判定是否整除，通常的优化中仅对 2 进行处理，单步内也用减法代替辗转相除单步的带余除法转化成带 2 的，因此也称为二进制最大公因数算法。

== 算法 ==

=== 原理 ===

<math>
\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>

=== 伪代码 ===

<syntaxhighlight>
过程 Stein算法
别名 steins_algorithm
参数 a, b : 整数 // 被求最大公因数的两个数
返回 : 自然数 // 最大公因数

令 r ← 1

循环
当 b ≠ 0 时
执行
    如果 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 那么
        令 b ← b - a
继续循环

令 r ← r a

返回 r
</syntaxhighlight>

实现中，判断整除 2 使用[[按位与]]运算实现，除以 2 使用[[右移]]运算， r 也处理成[[左移]]运算，此外只有减法运算，和普通的运算相同。


{{整除与质数}}