查看: 1387|回復: 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. }
復制代碼


回復

使用道具 舉報