俄国农民乘法 和 俄国农民指数算法
1.俄国农民乘法
俄国农民乘法适用于大整数的相乘运算，对于 m*n，m，n均为整数，运算基于以下原则：
1. 如果m为偶数， m * n = (m>>1) * (n<<1);
2. 如果m为奇数， m * n = (m>>1) * (n<<1) + n;
- //俄国农民乘法,求 a*b
long long int RussianFarmerAlgorithm(long long int a,long long int b){if(a==1)return b;if(a%2==1)return RussianFarmerAlgorithm(a>>1,b<<1)+b;return RussianFarmerAlgorithm(a>>1,b<<1);}
2.俄国农民指数算法
俄国农民指数算法可以减少求 n^m 的时候的运算次数，它的运算基于整数的二进制和十进制之间的转换.
eg: n = 3, m =13
13 的二进制表示： 1101 = (110)*2 + 1 , 110 = (11)*2+0 , 11 = (1)*2 +1
所以12次乘法运算转变为6次运算。
- //俄国农民指数算法 求 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; }
俄国农民指数算法和普通算法求幂运行时间比较：
#include <stdio.h>#include <stdlib.h>#include <time.h>//俄国农民指数算法 求 g^mint 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;}//普通求幂int cal(int g,int m){if(m==1){return g;}return g*cal(g,m-1);}//计算运行时间void c1(int a,int b){clock_t begin, end;double cost;begin = clock();int res;int i;for(i=0; i<1000000; i++){res = RFS(a,b);}end = clock();cost = (double)(end - begin) / CLOCKS_PER_SEC;printf("俄国农民算法 运行结果: %d , 运行时间: %lf\n",res,cost);}//计算运行时间void c2(int a,int b){clock_t begin, end;double cost;begin = clock();int res;int i;for(i=0; i<1000000; i++){res = cal(a,b);}end = clock();cost = (double)(end - begin) / CLOCKS_PER_SEC;printf("普通算法 运行结果: %d , 运行时间: %lf\n",res,cost);}int main(){c1(3,17);c2(3,17);return 0;}
求 3^17:
求 7^12:
求 137^6:
可以明显看出俄国农民算法是优于普通算法的。