找回密码
 欢迎注册
查看: 9666|回复: 8

[分享] 俄罗斯农夫算法

[复制链接]
发表于 2008-2-4 18:19:50 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能,让你轻松玩转社区。

您需要 登录 才可以下载或查看,没有账号?欢迎注册

×
俄罗斯农夫算法

    今天做题的时候,偶然在网上看到了一个十分有趣的算法,据说是俄罗斯的农夫发明的。特别适合在计算机里面算整数乘法。
    我们来看简单的等式  
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;
}
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-2-4 18:58:23 | 显示全部楼层
看上去不错
不知道用在高精度上的效果怎么样
如果用数组存,位移就很烦
顺便问一下:楼主做什么题?
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2008-2-4 22:54:50 | 显示全部楼层

回复 2# 的帖子

做ACM题的时候,描述里提到了农夫算法~~

高精度的话我不算太熟。一般人用数组时候是每个int表示0-9,就是表示1位数。因为int型的最大值为0x7fffffff(2147483647),所以你也可以设定每个int最大表示999999999,就是表示9位数。有空编个程序看看。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-2-4 23:04:20 | 显示全部楼层
可能这个算法适用于汇编
高精度计算一般用10000进制来优化
每个int存大了乘时会溢出
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2008-2-4 23:09:38 | 显示全部楼层

回复 4# 的帖子

也许吧,我也没试过
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-2-5 08:17:39 | 显示全部楼层
复杂度为O(n)次长度为n的大数加法或移位,也就是O(n^2)的算法,所以不适合大数乘法计算。
其实上面过程同我们手工乘法过程没有任何区别(二进制下)
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-2-5 08:19:11 | 显示全部楼层
楼上说的极是。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2008-2-5 15:31:10 | 显示全部楼层

回复 6# 的帖子

嗯,理解了。
另外问一下,写大数的话,怎么样提供运算效率。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-3-7 11:21:00 | 显示全部楼层
看上去很美的算法而已

现代计算机的乘都很快
所以普通乘效率很高
连高级的快速算法都要在大数上才显示优势
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

小黑屋|手机版|数学研发网 ( 苏ICP备07505100号 )

GMT+8, 2024-3-28 18:32 , Processed in 0.052933 second(s), 16 queries .

Powered by Discuz! X3.5

© 2001-2024 Discuz! Team.

快速回复 返回顶部 返回列表