俄罗斯农夫算法
俄罗斯农夫算法今天做题的时候，偶然在网上看到了一个十分有趣的算法，据说是俄罗斯的农夫发明的。特别适合在计算机里面算整数乘法。
我们来看简单的等式
a * b = (a /2 )* (2 * b)(如果a是偶数)
a * b = ((a-1)/2 )* (2 * b) + b (如果a是奇数)
我们来看看运算步骤如下表
比如我们要计算 77 * 33
a b
77 33
38 66 +33
19 132
9 264 +132
4 528 +264
2 1056
1 2112
那么结果就是 2112 + 264 + 132 + 33 = 2541
分析：在计算机中除2与乘2的操作是很快的，用位运算就可以了，而且对于很大的数来讲，这种方法也是可行的，因为对这种算法讲，a是以指数下降的，即使一个32位才能表示的整数也只要移位31次就可以为1，在机器层面讲，乘法是比移位慢的多的操作。
因此，这个算法对整数计算是很有实际意义的！
自己写了个C++程序^-^[不是大数的]
#include <cstdio>
int mul(int a,int b)
{
int r=0;
if(a==1) return b;
if(a%2==1) r+=b;
return r+mul(a>>1,b<<1);
}
int main()
{
int a,b;
scanf("%d%d",&a,&b);
printf("%d\n",mul(a,b));
return 0;
} 看上去不错
不知道用在高精度上的效果怎么样
如果用数组存，位移就很烦
顺便问一下：楼主做什么题？
回复 2# 的帖子
做ACM题的时候，描述里提到了农夫算法~~高精度的话我不算太熟。一般人用数组时候是每个int表示0-9，就是表示1位数。因为int型的最大值为0x7fffffff(2147483647)，所以你也可以设定每个int最大表示999999999，就是表示9位数。有空编个程序看看。 可能这个算法适用于汇编
高精度计算一般用10000进制来优化
每个int存大了乘时会溢出
回复 4# 的帖子
也许吧，我也没试过:) 复杂度为O(n)次长度为n的大数加法或移位，也就是O(n^2)的算法，所以不适合大数乘法计算。其实上面过程同我们手工乘法过程没有任何区别（二进制下） 楼上说的极是。
回复 6# 的帖子
嗯，理解了。另外问一下，写大数的话，怎么样提供运算效率。 看上去很美的算法而已
现代计算机的乘都很快
所以普通乘效率很高
连高级的快速算法都要在大数上才显示优势
页:
[1]