更相减损法查看源代码讨论查看历史
| 更相减损法 | |
|---|---|
更相减损法，是出自《九章算术》的一种求最大公约数的算法，它原本是为约分而设计的，但它适用于任何需要求最大公约数的场合。又名"更相减损术"，辗转相减法，等值算法，尼考曼彻斯法。它广泛应用在数学和计算机上。[1]
概述
古法探源
更相减损法,又称"等值算法"
"关于约分问题,实质是如何求分子,分母最大公约数的问题.《九章算术》中介绍了这个方法,叫做"更相减损术",即"可半者半之，不可半者，副置分母、子之数，以少减多，更相减损，求其等也。以等数约之。"
翻译成现代语言如下:[2]
第一步:任意给定两个正整数;判断它们是否都是偶数。若是，则用2约简;若不是则执行第二步。
第二步:以较大的数减较小的数，接着把所得的差与较小的数比较，并以大数减小数。继续这个操作，直到所得的减数和差相等为止。
则第一步中约掉的若干个2与第二步中等数的乘积就是所求的最大公约数。
其中所说的"等数"，就是最大公约数。求"等数"的办法是"更相减损"法。所以更相减损法也叫等值算法。
数学家刘徽对此法进行了明确的注解和说明,是一个实用的数学方法,中学生应该掌握它。
今有九十一分之四十九,问约之得几何?
我们用(91,49)表示91和49的最大公约数.按刘徽所说,分别列出分子,分母,"以少减多,更相减损,求其等也,以等数约之,等数约之,即除也,其所以相减者皆等数之重叠,故以等数约之."译文如下:约分的法则是:若分子、分母均为偶数时，可先被2除，否则，将分子与分母之数列在它处，然后以大数减小数，辗转相减，求它们的最大公约数，用最大公约数去约简分子与分母。其与古希腊欧几里德所著的《几何原本》中卷七第一个命题所论的相同。列式如下:
91≡42(mod49)
49≡7(mod42)
7│42
这里得到的7就叫做"等数",91和49都是这等数的重叠(即倍数),故7为其公约数.而7和7的最大公约数就是7,(7,7)=7,所以 (91,49)=(42,7)=(7,7)=7
更相减损术在现代仍有理论意义和实用价值.吴文俊教授说:"在我国,求两数最大公约数即等数,用更相减损之术,将两数以小减大累减以得之,如求24与15的等数,其逐步减损如下表所示: (24,15)->(9,15)->(9,6)->(3,6)->(3,3)
每次所得两数与前两数有相同的等数,两数之值逐步减少,因而到有限步后必然获得相同的两数,也即所求的等数,其理由不证自明.
这个寓理于算不证自明的方法,是完全构造性与机械化的尽可以据此编成程序上机实施".吴先生的话不仅说明了此法的理论价值,而且指明学习和研究的方向.
更相减损法很有研究价值,它奠定了我国渐近分数,不定分析,同余式论和大衍求一术的理论基础，望能仔细品味。
比较其他算法
辗转相除法
(1)两者都是求最大公因数的方法，计算上辗转相除法以除法为主，更相减损术以减法为主，计算次数上辗转相除法计算次数相对较少，特别当两个数字大小区别较大时计算次数的区别较明显。
(2)从结果体现形式来看，辗转相除法体现结果是以相除余数为0则得到，而更相减损术则以减数与差相等而得到。
更相损减法在两数相差较大时，时间复杂度容易退化成O(N)，而辗转相除法可以稳定在O(logN)。但辗转相除法需要试商，这就使得在某些情况下，使用更相损减法比使用辗转相除法更加简单。而stein算法便由此出现。
Stein算法
(部分内容出自CSDN博主Holmofy) 辗转相除法是计算两个数最大公约数的传统算法，无论从理论还是从实际效率上都是很好的。但是却有一个致命的缺陷，这个缺陷在素数比较小的时候一般是感觉不到的，只有在大素数时才会显现出来:一般实际应用中的整数很少会超过64位(当然已经允许128位了)，对于这样的整数，计算两个数之间的模是很简单的。对于字长为32位的平台，计算两个不超过32位的整数的模，只需要一个指令周期，而计算64位以下的整数模，也不过几个周期而已。但是对于更大的素数，这样的计算过程就不得不由用户来设计，为了计算两个超过64位的整数的模，用户也许不得不采用类似于多位数除法手算过程中的试商法，这个过程不但复杂，而且消耗了很多CPU时间。对于现代密码算法，要求计算128位以上的素数的情况比比皆是，比如说RSA加密算法至少要求500bit密钥长度，设计这样的程序迫切希望能够抛弃除法和取模。
Stein算法很好的解决了辗转相除法中的这个缺陷，Stein算法只有整数的移位和加减法。下面就来说一下Stein算法的原理:
若a和b都是偶数，则记录下公约数2，然后都除2(即右移1位); 若其中一个数是偶数，则偶数除2，因为此时2不可能是这两个数的公约数了 若两个都是奇数，则a = |a-b|，b = min(a,b)，因为若d是a和b的公约数，那么d也是|a-b|和min(a,b)的公约数。 Stein算法比辗转相除法更加快速，简易。它与每一次进行更相减损法得到的结果似乎存在着微妙的联系，通过下面的比较，可以发现两种算法之间的联系。
更相减损法:操作 甲数 乙数 Stein算法:操作 甲数 乙数 98 63 98 63 98-63=35 63 35 98是偶数，除以2 49 63 63-35=28 35 28 都是奇数，63-49=14 49 14 35-28=7 28 7 14是偶数，除以2 49 7 28-7=21 7 21 49-7=42 42 7 21-7=14 7 14 42是偶数，除以2 21 7 14-7=7 7 7 21-7=14 14 7
7-7=0 7 0 14是偶数，除以2 7 7 7-7=0 7 0