请选择 进入手机版 | 继续访问电脑版
查看: 450|回复: 0

[云计算] 最大公约数问题(主要针对大整数运算二设计的方法)

715

主题

715

帖子

2162

积分

猿er

Rank: 1

积分
2162
发表于 2016-8-14 18:57:31
借鉴
  1. 首先,按照数学上的辗转相除法计算最大公约数固然可以,但是如果两个数都是非常大的数,那么除法的代价很昂贵;另外,如果将除法转换为减法,即f(x,y)=f(y,x-y)可以很大程度上减少除法的开销,但是可能导致迭代此处太多,算法代价仍然昂贵,现在结合这两者的思想,给出一个最佳的算法,特别适合Big Int的计算,算法思想如下:
  2. 如果 y=k*y1;x=k*x1;
  3. 那么有f(x,y) = k*f(x1,y1);
  4. 另外,如果
  5. x=p*x1;且p为素数,且y%p != 0;那么f(x,y)=f(x1,y);
  6. 由于在计算机中移位操作很方便,代价很小,效率也很高,所以我们考虑p=2的情况下进行求取,代码如下:
  7. bool isEven(int x)
  8. {
  9. if ( x%2 == 0 )
  10. {
  11. return true;
  12. }
  13. else
  14. {
  15. return false;
  16. }
  17. }
  18. int MaxGcd(int x,int y)
  19. {
  20. if ( x<y )
  21. {
  22. return MaxGcd(y,x);
  23. }
  24. if (y==0)
  25. {
  26. return x;
  27. }
  28. else
  29. {
  30. if (isEven(x))
  31. {
  32. if ( isEven(y) )
  33. {
  34. return (MaxGcd(x>>1,y>>1)<<1);
  35. }
  36. else
  37. {
  38. return MaxGcd(x>>1,y);
  39. }
  40. }
  41. else
  42. {
  43. if ( isEven(y) )
  44. {
  45. return MaxGcd(x,y>>1);
  46. }
  47. else
  48. {
  49. return MaxGcd(y,x-y);
  50. }
  51. }
  52. }
  53. }
复制代码


回复

使用道具 举报