用Python实现常见算法 -- ["qingfeng"] (Date(2009-04-21T16:35:01Z)) TableOfContents

求最大公约数

欧几里得算法

分析：求最大公约数的算法思想：
(1) 对于已知两数m，n，使得m>n； 
(2) m除以n得余数r； 
(3) 若r=0，则n为求得的最大公约数，算法结束；否则执行(4)； 
(4) m←n，n←r，再重复执行(2)。 
例如: 求 m=14 ,n=6 的最大公约数. m n r

代码: 

   1 def f(m,n):
   2     m,n=max(m,n),min(m,n)
   3     if n==0:return m
   4     return f(n,m%n)
   5 f(14,6)

Stein算法

欧几里德算法是计算两个数最大公约数的传统算法，无论是理论，还是从效率上都是很好的。但是他有一个致命的缺陷，这个缺陷只有在很大的素数时才会显现出来。
考虑现在的硬件平台，一般整数最多也就是64位， 对于这样的整数，计算两个数值就的模很简单的。对于字长为32位的平台，计算两个不超过32位的整数的模，只需要一个指令周期，而计算64位以下的整数模，也不过几个周期而已。但是对于更大的素数，这样的计算过程就不得不由用户来设计，为了计算两个超过64位的整数的模，用户也许不得不采用类似于多位除法手算过程中的试商法，这个过程不但复杂，而且消耗了很多CPU时间。对于现代密码算法，要求计算128位以上的素数的情况比比皆是，设计这样的程序迫切希望能够抛弃除法和取模。
Stein算法由J.Stein 1961年提出，这个方法也是计算两个数的最大公约数。和欧几里德算法不同的是，Stein算法只有整数的移位和加减法，这对于程序设计者是一个福音。
为了说明Stein算法的正确性，首先必须注意到以下结论：
  gcd(a, a) = a， 也就是一个数和他自己的公约数是其自身。
  gcd(ka, kb) = k * gcd(a, b)，也就是最大公约数运算和倍乘运算可以交换，特殊的，当k=2时，说明两个偶数的最大公约数比如能被2整除。

代码: 

   1 def f(a, b):    
   2     a,b = max(a,b),min(a,b)
   3     if (b == 0):
   4         return a
   5     if a % 2 == 0 and b % 2 == 0:
   6         return 2 * f(a/2, b/2)
   7     if a % 2 == 0:
   8         return f(a / 2, b)
   9     if b % 2 == 0:
  10         return f(a, b / 2)
  11     
  12     return f((a + b) / 2, (a - b) / 2)