Welcome to Rooeye's blog

俄国农民乘法 和 俄国农民指数算法

算法 rooeye 1447℃ 0评论
1.俄国农民乘法
俄国农民乘法适用于大整数的相乘运算,对于 m*n,m,n均为整数,运算基于以下原则:


1. 如果m为偶数, m * n = (m>>1) * (n<<1);
2. 如果m为奇数, m * n = (m>>1) * (n<<1) + n;

  1. //俄国农民乘法,求 a*b
  2. long long int RussianFarmerAlgorithm(long long int a,long long int b)
  3. {
  4. if(a==1)
  5. return b;
  6. if(a%2==1)
  7. return RussianFarmerAlgorithm(a>>1,b<<1)+b;
  8. return RussianFarmerAlgorithm(a>>1,b<<1);
  9. }

2.俄国农民指数算法

俄国农民指数算法可以减少求 n^m 的时候的运算次数,它的运算基于整数的二进制和十进制之间的转换.

eg:   n = 3, m =13

13 的二进制表示: 1101 = (110)*2 + 1 , 110 = (11)*2+0 , 11  = (1)*2 +1

所以12次乘法运算转变为6次运算。
  1. //俄国农民指数算法 求 g^m int RFS(int g,int m) { if(m==1) { return g; } int temp = RFS(g,m>>1); if(m%2==0) { return temp*temp; } return g*temp*temp; }
俄国农民指数算法和普通算法求幂运行时间比较:
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <time.h>
  4. //俄国农民指数算法 求 g^m
  5. int RFS(int g,int m)
  6. {
  7. if(m==1)
  8. {
  9. return g;
  10. }
  11. int temp = RFS(g,m>>1);
  12. if(m%2==0)
  13. {
  14. return temp*temp;
  15. }
  16. return g*temp*temp;
  17. }
  18. //普通求幂
  19. int cal(int g,int m)
  20. {
  21. if(m==1)
  22. {
  23. return g;
  24. }
  25. return g*cal(g,m-1);
  26. }
  27. //计算运行时间
  28. void c1(int a,int b)
  29. {
  30. clock_t begin, end;
  31. double cost;
  32. begin = clock();
  33. int res;
  34. int i;
  35. for(i=0; i<1000000; i++)
  36. {
  37. res = RFS(a,b);
  38. }
  39. end = clock();
  40. cost = (double)(end - begin) / CLOCKS_PER_SEC;
  41. printf("俄国农民算法 运行结果: %d , 运行时间: %lf\n",res,cost);
  42. }
  43. //计算运行时间
  44. void c2(int a,int b)
  45. {
  46. clock_t begin, end;
  47. double cost;
  48. begin = clock();
  49. int res;
  50. int i;
  51. for(i=0; i<1000000; i++)
  52. {
  53. res = cal(a,b);
  54. }
  55. end = clock();
  56. cost = (double)(end - begin) / CLOCKS_PER_SEC;
  57. printf("普通算法 运行结果: %d , 运行时间: %lf\n",res,cost);
  58. }
  59. int main()
  60. {
  61. c1(3,17);
  62. c2(3,17);
  63. return 0;
  64. }
求 3^17:
求 7^12:
求 137^6:

可以明显看出俄国农民算法是优于普通算法的





来自为知笔记(Wiz)

转载请注明: Jinkun 的博客 » 俄国农民乘法 和 俄国农民指数算法

喜欢 (0)
发表我的评论
取消评论

Hi,您需要填写昵称和邮箱!

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址
(3)个小伙伴在吐槽
  1. 嗯嗯,是的,我试一下 ~ o(∩_∩)o
    rooeye2015-10-16 18:15 回复
  2. 代码已修正,o(∩_∩)o
    rooeye2015-10-16 20:54 回复
  3. 童鞋好丫,这几天考试也没太看博客,不好意思!1.5*(n-1)书上写的是平均乘法次数,不过我不太理解这个平均怎么来的,囧......不过这里乘法的次数俺是确定的,对于n^m(我木有加取模的过程),设m的二进制长度为p(从1开始算,比如10的p=2),m转化为二进制后其中为1的个数为t(从1开始算,比如10的t=1),那么所使用的乘法次数为: p-1+t, 这里的p=4,t=3,所以就是6
    rooeye2016-01-06 13:32 回复