数学研发论坛

 找回密码
 欢迎注册
查看: 5860|回复: 24

[擂台] 分数代码优化

[复制链接]
发表于 2009-12-12 10:47:47 | 显示全部楼层 |阅读模式

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

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

x
为了在复数范围而不是有限域范围内验证果树问题,我现在实现了一个“短”有理数代码,对于计算溢出,通过C++异常来处理。
结果发现这个代码的速度还是比较让人满意的,用在果树问题上,速度大概只比有限域版本慢一倍多一点。
但是其中使用的分数类代码还不是很优化,特意贴出来让大家帮忙优化一下,最后能够让速度达到有限域版本:

  1. long long gcd(long long a, long long b)
  2. {
  3.         long long t;
  4.         while(b!=0){
  5.                 a%=b;
  6.                 t=b;
  7.                 b=a;
  8.                 a=t;
  9.         }
  10.         return a;
  11. }
  12. #define MINI (-0x7fffffff)
  13. #define MAXI 0x7fffffff
  14. bool in_range(long long& u, long long& d)
  15. {
  16.         if(MINI<=u&&u<=MAXI&&MINI<=d&&d<=MAXI)
  17.                 return true;
  18.         long long r=gcd(u,d);
  19.         u/=r;d/=r;
  20.         if(MINI<=u&&u<=MAXI&&MINI<=d&&d<=MAXI)
  21.                 return true;
  22.         return false;
  23. }
  24. class MyException{
  25.         int v;
  26. public:
  27.         MyException(int u):v(u){}
  28. };

  29. class number{
  30.     int up;
  31.     int down;
  32. public:
  33.     number(const number& n):up(n.up),down(n.down){}
  34.     number(int n=0):up(n),down(1){}
  35.     number& operator+=(const number& n);
  36.     number& operator-=(const number& n);
  37.     number& operator*=(const number& n);
  38.     number& operator/=(const number& n);
  39.     bool is_zero()const{return up==0;}
  40.     bool is_one()const{return up==down;}
  41.         bool is_mone()const{return up==-down;}
  42.     bool operator==(const number& n)const{return
  43.         n.down*(long long)up==n.up*(long long)down;}
  44.     bool operator<(const number& n)const;
  45.     bool operator>(const number& n)const{return n<*this;}
  46.     bool operator<=(const number& n)const{return !(*this>n);}
  47.     bool operator!=(const number& n)const{return !(n==*this);}
  48.     bool operator>=(const number& n)const{return !(*this<n);}
  49.     number operator+(const number& n)const{number m(*this);return m+=n;}
  50.     number operator-(const number& n)const{number m(*this);return m-=n;}
  51.     number operator*(const number& n)const{number m(*this);return m*=n;}
  52.     number operator/(const number& n)const{number m(*this);return m/=n;}
  53.     bool is_integer()const{return up%down==0;}
  54.     int get_integer()const{if(is_integer())return up/down;else throw  MyException(7);}
  55.     number& operator=(int n){up=n;down=1;return *this;}
  56.     int get_up()const{return up;}
  57.     int get_down()const{return down;}
  58.         number neg()const{number x;x.up=-up;x.down=down; return x;}
  59.     number abs()const{number x;x.up=up>=0?up:-up;x.down=down>=0?down:-down;return x;}
  60. };

  61. number& number::operator +=(const number& n)
  62. {
  63.         long long u=(long long)up*n.down+(long long)down*n.up;
  64.         long long d=(long long)down*n.down;
  65.         if(!in_range(u,d))
  66.                 throw  MyException(1);
  67.     up=(int)u;
  68.     down=(int)d;
  69.     return *this;
  70. }

  71. number& number::operator -=(const number& n)
  72. {
  73.         long long u=(long long)up*n.down-(long long)down*n.up;
  74.         long long d=(long long)down*n.down;
  75.         if(!in_range(u,d))
  76.                 throw  MyException(2);
  77.     up=(int)u;
  78.     down=(int)d;
  79.     return *this;

  80. }

  81. number& number::operator *=(const number& n)
  82. {
  83.         long long u=(long long)up*n.up;
  84.         long long d=(long long)down*n.down;
  85.         if(!in_range(u,d))
  86.                 throw  MyException(3);
  87.     up=(int)u;
  88.     down=(int)d;
  89.     return *this;
  90. }

  91. number& number::operator /=(const number& n)
  92. {
  93.         long long u=(long long)up*n.down;
  94.         long long d=(long long)down*n.up;
  95.         if(!in_range(u,d))
  96.                 throw  MyException(4);
  97.         if(d==0)throw  MyException(5);
  98.         if(d<0){
  99.                 d=-d;u=-u;
  100.         }
  101.     up=(int)u;
  102.     down=(int)d;
  103.     return *this;
  104. }

  105. bool number::operator <(const number &n)const
  106. {
  107.     return (long long)up*n.down<n.up*(long long)down;
  108. }
复制代码
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2009-12-12 11:58:23 | 显示全部楼层
想问一下mathe,你的那个 gcd函数里面的while如果改成这样,效率会提高吗
  1. while(b!=0){
  2.                  t=b;
  3.                  b=a%b;
  4.                  a=t;
  5.          }
复制代码
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2009-12-12 12:19:40 | 显示全部楼层
这种变化应该没有区别。现在的编译器对于局部优化可以做得很不错的。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2009-12-12 20:31:13 | 显示全部楼层
所做的操作都是很必要的,一点优化的余地都没有了,怎么可能提速2倍以上?

如果硬要做点改动的话,可以在in_range函数里把这3行代码加在最前面:

  1. if((u&15)==0&&(d&15)==0){u>>=4;d>>=4}
  2. if((u&3)==0&&(d&3)==0){u>>=2;d>>=2}
  3. if((u&1)==0&&(d&1)==0){u>>=1;d>>=1}
复制代码
添加理由:

1.有64%的可约分数含有公因子2,有52%的可约分数只需把因子2约去就不可约了(对于要进来检查的分数来说,这个比例可能更大)。
2.约去因子2只要用移位操作就可以完成。
3.移位操作花费的代价很小。
4.gcd操作花费的代价很大,应尽量少用。

上述改动实际上是试图通过盲目地增加一些移位操作来减少gcd的调用次数。

花费大量的移位操作的代价来换取一次gcd的调用是否值得?

如果这个交易是亏本的,那么速度反而会下降。

即使是盈利的,速度改善的程度也是很有限的,能提速10%就很不错了,不可能提速2倍以上。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2009-12-13 08:33:16 | 显示全部楼层
呵呵,最终提高多少不重要,有多少是多少吧。
不过这里有很多汇编高手,也许他们可以帮不少忙的。
到星期一我可以提供一个完整的版本和测试数据。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2009-12-13 13:05:54 | 显示全部楼层
分数的四则运算看似简单,实际上有许多技巧而变得复杂,尤其是如何通分、结合率的使用等。
举个简单的例子,计算:$1/2+1/6+1/12+1/20+1/30+1/42+1/56+1/72+1/90$

4# KeyTo9_Fans 建议 in_range 中采用移位运算,
但其变量都是有符号的,恐怕不大适合。
是不是可以采用新的数据结构,分别定义:符号、分子和分母(均为无符号型)

求最大公约数最好采用 Josef Stein 算法,以避免除法指令。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2009-12-13 23:29:11 | 显示全部楼层
回6#:

测了几个数据,似乎没有任何问题。

  1. #include<stdio.h>

  2. int i;
  3. __int64 _i;

  4. int main()
  5. {
  6.         //test1
  7.         i=-128;
  8.         printf("%d\n",i&15);                //output: 0
  9.         printf("%d\n",i>>4);                //output: -8
  10.         //test2
  11.         i=-37;
  12.         printf("%d\n",i&1);                        //output: 1
  13.         printf("%d\n",i&3);                        //output: 3
  14.         //test3
  15.         i=-2147483648;
  16.         printf("%d\n",i&65535);                //output: 0
  17.         printf("%d\n",i>>16);                //output: -32768
  18.         printf("%d\n",i>>31);                //output: -1
  19.         //test4
  20.         _i=-2222222222222222;
  21.         printf("%I64d\n",_i&1);                //output: 0
  22.         printf("%I64d\n",_i>>1);        //output: -1111111111111111
  23.         printf("%I64d\n",_i&3);                //output: 2
  24.         return 0;
  25. }
复制代码
其中,-128的32个比特位为

11111111 11111111 11111111 10000000

后面连续出现7个0,和+128的性质相同:

10000000

所以&1、&3、&15的运算结果和+128是完全一样的。

在默认情况下,>>运算是算术右移,符号会保留。

所以((-128)>>4)的比特位为:

11111111 11111111 11111111 11111000

即 ((-128)>>4) = -8

与除以16的效果完全相同。

最特殊负数-2147483648的&运算与>>运算也没有问题。

所以那3行代码应该是没问题的。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2009-12-14 07:35:47 | 显示全部楼层
楼上说的是对的。
我搞大数计算多了,对无符号类型变量有偏爱。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2009-12-14 08:05:11 | 显示全部楼层
我觉得long long拖了后腿
用汇编吧
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2009-12-14 17:13:02 | 显示全部楼层
我也觉得long long是个问题。
不过用汇编也会有汇编的问题。
这两天我女儿生病了,现在我暂时没有时间提供测试版本了
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

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

GMT+8, 2021-1-19 06:59 , Processed in 0.069984 second(s), 17 queries .

Powered by Discuz! X3.4

© 2001-2017 Comsenz Inc.

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