GCD的二进制算法

进一步提高gcd的效率。

$x=y \Rightarrow gcd(x,y)=x$,$x \neq y \Rightarrow$

  • $x \mod 2 = 0, y \mod 2 = 0 \rightarrow gcd(x, y) = 2\cdot gcd(\frac{x}{2}, \frac{y}{2})$
  • $x \mod 2 = 0, y \mod 2 = 1 \rightarrow gcd(x, y) = gcd(\frac{x}{2}, y)$
  • $x \mod 2 = 1, y \mod 2 = 0 \rightarrow gcd(x, y) = gcd(x, \frac{y}{2})$
  • $x \mod 2 = 1, y \mod 2 = 1 \rightarrow gcd(x, y) = gcd(x-y, y)$

 

2
说点什么

avatar
50
1 Comment threads
1 Thread replies
0 Followers
 
Most reacted comment
Hottest comment thread
2 Comment authors
YuweiZhaoMoonChasing Recent comment authors
  Subscribe  
最新 最旧 得票最多
提醒
MoonChasing
游客

老哥,你这不return呀