更相减损术
| 更相减损术 | |
|---|---|
| 术语名称 | 更相减损术 |
| 英语名称 | |
更相减损术是出自《九章算术》的一种求两个正整数最大公因数的算法，与 Euclid 算法（辗转相除法）等价，只是以反复相减替代带余除法。计算机计算除法的操作比减法要复杂，但在商比较大时，由于重复减法所需重复次数更多，除法通常更加快捷，现在一般以 Euclid 算法视为主要方法。更相减损只在每一步中的两数都比较接近时才更优。人工计算时，由于除数复杂时除法比减法复杂度高很多，在两数接近时更相减损术比辗转相除法更容易执行，可以混合两种算法的步骤，根据每步的数据特征选择操作。
原理
若整数 [math]\displaystyle{ a, b }[/math] 有公因数 [math]\displaystyle{ d }[/math]，则 [math]\displaystyle{ d \mid a }[/math] 且 [math]\displaystyle{ d \mid b }[/math]，于是 [math]\displaystyle{ d \mid |a-b| }[/math]。因此 [math]\displaystyle{ \operatorname{gcd}(a, b) = \operatorname{gcd}(|a-b|, \min(a, b)) }[/math]。
反复用较大数减去较小数，两数逐渐减小，直至相等。此时这个相等的数即为最大公因数。
算法
对两个正整数 [math]\displaystyle{ a, b }[/math]（不失一般性可设 [math]\displaystyle{ a \ge b }[/math]）：
原始流程
- 若 [math]\displaystyle{ a, b }[/math] 皆为偶数，可先不断同除以 2（“可半者半之”），记录公因子 [math]\displaystyle{ 2^k }[/math]，最后乘回。
- 从 [math]\displaystyle{ a, b }[/math]（或约去 2 后的数）出发，设 [math]\displaystyle{ a \ge b }[/math]。
- 若 [math]\displaystyle{ a = b }[/math]，此即最大公因数（“等数”），停止。
- 若 [math]\displaystyle{ a \gt b }[/math]，令 [math]\displaystyle{ a \leftarrow a - b }[/math]，返回第 3 步。
辗转相减可连续进行，即用 [math]\displaystyle{ a }[/math] 不断减 [math]\displaystyle{ b }[/math] 直至差小于 [math]\displaystyle{ b }[/math]，等价于 [math]\displaystyle{ a \bmod b }[/math]。
伪代码
过程 更相减损术
别名 gengxiangjiansun_algorithm
参数 a, b : 正整数 // 求最大公因数的两数
返回 : 正整数 // 最大公因数
循环 当 a ≠ b 时
如果 a > b 那么
令 a ← a - b
否则
令 b ← b - a
继续循环
返回 a原文方法
以上仅包含“更相减损”步骤，但是在《九章算术·方田》约分术中，求取最大公因数的全过程应如下。
过程 约分术求等数过程
别名 yuefen_dengshu_algorithm
参数 a, b : 正整数 // 求最大公因数的两数
返回 : 正整数 // 最大公因数
令 g ← 1
循环 当 a 为偶数 且 b 为偶数 时
令 a ← a / 2
令 b ← b / 2
令 g ← 2g
继续循环
循环 当 a ≠ b 时
如果 a > b 那么
令 a ← a - b
否则
令 b ← b - a
继续循环
返回 ag与辗转相除法的关系
更相减损术的连续相减等价于辗转相除法中一次带余除法：若 [math]\displaystyle{ a = qb + r }[/math]，用更相减损连续减去 [math]\displaystyle{ q }[/math] 次 [math]\displaystyle{ b }[/math] 即得 [math]\displaystyle{ r }[/math]。两者本质完全相同，相减是相除的底层分解，而相除是相减的合并步骤。
当两数相差悬殊时，辗转相除法的除法跳步远快于减损；但当两数接近时，减法反而免去除法开销。二进制 GCD（Stein 算法）某种程度上综合了二者优势。
琐事
历史
更相减损术记载于《九章算术·方田》约分术中，是中国古代数学求最大公约数（称为“等数”）的标准方法。
约分按：约分者，物之数量，不可悉全，必以分言之。分之为数，繁则难用。设有四分之二者，繁而言之，亦可为八分之四；约而言之，则二分之一也。虽则异词，至于为数，亦同归尔。法实相推，动有参差，故为术者，先治诸分。
术曰：可半者半之；不可半者，副置分母子之数，以少减多，更相减损，求其等也。以等数约之。等数约之，即除也。其所以相减者，皆等数之重叠，故以等数约之。
——《九章算术》 西汉 ・《九章算术注》 魏 刘徽 [1]