论坛 › 编程擂台 › 分数代码优化

mathe 发表于 2009-12-12 10:47:47

分数代码优化

为了在复数范围而不是有限域范围内验证果树问题，我现在实现了一个“短”有理数代码，对于计算溢出，通过C++异常来处理。
结果发现这个代码的速度还是比较让人满意的，用在果树问题上，速度大概只比有限域版本慢一倍多一点。
但是其中使用的分数类代码还不是很优化，特意贴出来让大家帮忙优化一下，最后能够让速度达到有限域版本:
long long gcd(long long a, long long b)
{
        long long t;
        while(b!=0){
                a%=b;
                t=b;
                b=a;
                a=t;
        }
        return a;
}
#define MINI (-0x7fffffff)
#define MAXI 0x7fffffff
bool in_range(long long& u, long long& d)
{
        if(MINI<=u&&u<=MAXI&&MINI<=d&&d<=MAXI)
                return true;
        long long r=gcd(u,d);
        u/=r;d/=r;
        if(MINI<=u&&u<=MAXI&&MINI<=d&&d<=MAXI)
                return true;
        return false;
}
class MyException{
        int v;
public:
        MyException(int u):v(u){}
};

class number{
    int up;
    int down;
public:
    number(const number& n):up(n.up),down(n.down){}
    number(int n=0):up(n),down(1){}
    number& operator+=(const number& n);
    number& operator-=(const number& n);
    number& operator*=(const number& n);
    number& operator/=(const number& n);
    bool is_zero()const{return up==0;}
    bool is_one()const{return up==down;}
        bool is_mone()const{return up==-down;}
    bool operator==(const number& n)const{return
      n.down*(long long)up==n.up*(long long)down;}
    bool operator<(const number& n)const;
    bool operator>(const number& n)const{return n<*this;}
    bool operator<=(const number& n)const{return !(*this>n);}
    bool operator!=(const number& n)const{return !(n==*this);}
    bool operator>=(const number& n)const{return !(*this<n);}
    number operator+(const number& n)const{number m(*this);return m+=n;}
    number operator-(const number& n)const{number m(*this);return m-=n;}
    number operator*(const number& n)const{number m(*this);return m*=n;}
    number operator/(const number& n)const{number m(*this);return m/=n;}
    bool is_integer()const{return up%down==0;}
    int get_integer()const{if(is_integer())return up/down;else throwMyException(7);}
    number& operator=(int n){up=n;down=1;return *this;}
    int get_up()const{return up;}
    int get_down()const{return down;}
        number neg()const{number x;x.up=-up;x.down=down; return x;}
    number abs()const{number x;x.up=up>=0?up:-up;x.down=down>=0?down:-down;return x;}
};

number& number::operator +=(const number& n)
{
        long long u=(long long)up*n.down+(long long)down*n.up;
        long long d=(long long)down*n.down;
        if(!in_range(u,d))
                throwMyException(1);
    up=(int)u;
    down=(int)d;
    return *this;
}

number& number::operator -=(const number& n)
{
        long long u=(long long)up*n.down-(long long)down*n.up;
        long long d=(long long)down*n.down;
        if(!in_range(u,d))
                throwMyException(2);
    up=(int)u;
    down=(int)d;
    return *this;

}

number& number::operator *=(const number& n)
{
        long long u=(long long)up*n.up;
        long long d=(long long)down*n.down;
        if(!in_range(u,d))
                throwMyException(3);
    up=(int)u;
    down=(int)d;
    return *this;
}

number& number::operator /=(const number& n)
{
        long long u=(long long)up*n.down;
        long long d=(long long)down*n.up;
        if(!in_range(u,d))
                throwMyException(4);
        if(d==0)throwMyException(5);
        if(d<0){
                d=-d;u=-u;
        }
    up=(int)u;
    down=(int)d;
    return *this;
}

bool number::operator <(const number &n)const
{
    return (long long)up*n.down<n.up*(long long)down;
}

wayne 发表于 2009-12-12 11:58:23

想问一下mathe，你的那个 gcd函数里面的while如果改成这样，效率会提高吗while(b!=0){
               t=b;
               b=a%b;
               a=t;
         }

mathe 发表于 2009-12-12 12:19:40

这种变化应该没有区别。现在的编译器对于局部优化可以做得很不错的。

KeyTo9_Fans 发表于 2009-12-12 20:31:13

所做的操作都是很必要的，一点优化的余地都没有了，怎么可能提速2倍以上？

如果硬要做点改动的话，可以在in_range函数里把这3行代码加在最前面：
if((u&15)==0&&(d&15)==0){u>>=4;d>>=4}
if((u&3)==0&&(d&3)==0){u>>=2;d>>=2}
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倍以上。

mathe 发表于 2009-12-13 08:33:16

呵呵，最终提高多少不重要，有多少是多少吧。
不过这里有很多汇编高手，也许他们可以帮不少忙的。
到星期一我可以提供一个完整的版本和测试数据。

gxqcn 发表于 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 算法，以避免除法指令。

KeyTo9_Fans 发表于 2009-12-13 23:29:11

回6#：

测了几个数据，似乎没有任何问题。
#include<stdio.h>

int i;
__int64 _i;

int main()
{
        //test1
        i=-128;
        printf("%d\n",i&15);                //output: 0
        printf("%d\n",i>>4);                //output: -8
        //test2
        i=-37;
        printf("%d\n",i&1);                        //output: 1
        printf("%d\n",i&3);                        //output: 3
        //test3
        i=-2147483648;
        printf("%d\n",i&65535);                //output: 0
        printf("%d\n",i>>16);                //output: -32768
        printf("%d\n",i>>31);                //output: -1
        //test4
        _i=-2222222222222222;
        printf("%I64d\n",_i&1);                //output: 0
        printf("%I64d\n",_i>>1);        //output: -1111111111111111
        printf("%I64d\n",_i&3);                //output: 2
        return 0;
}
其中，-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行代码应该是没问题的。

gxqcn 发表于 2009-12-14 07:35:47

楼上说的是对的。
我搞大数计算多了，对无符号类型变量有偏爱。:D

无心人 发表于 2009-12-14 08:05:11

我觉得long long拖了后腿
用汇编吧

mathe 发表于 2009-12-14 17:13:02

我也觉得long long是个问题。
不过用汇编也会有汇编的问题。
这两天我女儿生病了，现在我暂时没有时间提供测试版本了

查看完整版本: 分数代码优化