| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 4915 人关注过本帖, 2 人收藏
标题:写了个大数库, 大家看看效率,或者是否有bug
只看楼主 加入收藏
Devil_W
Rank: 10Rank: 10Rank: 10
等 级:青峰侠
威 望:9
帖 子:1160
专家分:1797
注 册:2009-9-14
结帖率:100%
收藏(2)
 问题点数:0 回复次数:31 
写了个大数库, 大家看看效率,或者是否有bug
除了% 和/别的功能都实现了。
大家看看效率,或者是否有bug.
boost的大数库还有merge到标准库里面。 大数还要自己写。
程序代码:
#include<iostream>
#include<deque>
#include<string>
#include<cassert>
#include<exception>
class BigInt
{
public:
    explicit BigInt(int i);
    BigInt(const BigInt &other);
    BigInt(const std::string &);
    ~BigInt();
    friend BigInt operator += (BigInt &, const BigInt &);
    friend BigInt operator -= (BigInt &, const BigInt &);
    friend BigInt operator *= (BigInt &,  int );
    friend BigInt operator *= (BigInt &,  const BigInt &);
    friend BigInt operator +(const BigInt & , const BigInt & );
    friend BigInt operator -(const BigInt & , const BigInt & );
    friend BigInt operator - (const BigInt &); 
    friend BigInt operator *(const BigInt & , int);
    friend BigInt operator *( const int  ,const BigInt &);
    friend BigInt operator *(const BigInt & , const BigInt & );
    friend bool operator == (const BigInt &,  const BigInt & );
    friend bool operator >  ( const BigInt &, const BigInt &);
    friend bool operator < ( const BigInt &, const BigInt & );
    friend bool operator >= ( const BigInt &, const BigInt &);
    friend bool operator <= ( const BigInt &, const BigInt &);
    BigInt & operator = (const BigInt &);
    friend std::ostream & operator << ( std::ostream & out, BigInt &bg);
    friend BigInt fab(const BigInt &);
    friend BigInt pow ( const BigInt &,int );
protected:
    void trim(){
    while( 0 == dt.back() )
    {
        dt.pop_back();
    } 
    }
private:
    bool sign;
    static const unsigned int Base;
    std::deque<unsigned int> dt;
};
const unsigned int BigInt::Base =10;

BigInt::BigInt(int i=0)
{
    sign= i >= 0? true: false; 
    i = i > 0 ? i : -i;
    assert(dt.empty());
    for ( ; i > 0; i /= Base)
    {
    dt.push_back(i%Base);
    }
}
BigInt::BigInt(const BigInt &other)
{
    assert(this->dt.empty());
    dt=other.dt;
    sign=other.sign;
}

BigInt & BigInt::operator = (const BigInt & other)
{
    this->sign=other.sign;
    this->dt=other.dt;    
    return *this;
}
BigInt::BigInt( const std::string & s)
{
    try{
    std::string::const_reverse_iterator it=s.rbegin();
    for( ; it!=s.rend(); it++)
    {
        if ( * it == '-' || (* it <='9' && * it >='0'))
        {
        if( *it != '-')
            dt.push_back((unsigned)( *it-'0' ));
        else
            sign=false;
        }
        else
        throw std::exception();
    }
    }catch ( std::exception e)
    {
    std::cerr<<e.what()<<std::endl;
    }
}

BigInt::~BigInt()
{
    dt.clear();
}


std::ostream & operator << ( std::ostream & out, BigInt &bg)
{
    if( 0 == bg.dt.size())
    out<< unsigned(0);
    if( !bg.sign)
    out<<"-";
    std::deque<unsigned int>::const_reverse_iterator rit = bg.dt.rbegin();
    for( ; rit != bg.dt.rend() ; rit++ ) 
    {
    out<<*rit;
    } 
    return out;
}
BigInt operator - (const BigInt & bg)
{
    BigInt ret(bg);
    ret.sign=!ret.sign;
    return ret;
}

bool operator == ( const BigInt& op1 , const BigInt &op2)
{
    return op1.sign==op2.sign && op1.dt== op2.dt;    
}

bool operator > ( const BigInt &op1, const BigInt & op2)
{
    if( op1.sign> op2.sign)
    return true;
    if ( op1 == op2 )
    return false;
    if( op1.dt.size()== op2.dt.size())
    {
    std::deque<unsigned>::const_reverse_iterator it,jt;
    it=op1.dt.rbegin();
    jt=op2.dt.rbegin();
    while( *it == *jt && it != op1.dt.rend() && jt !=op2.dt.rend() )
    {
        it++;
        jt++;
    }
    if( op1.sign > 0 )
        return *it > *jt;
    else
        return *it < *jt;
    }
    else
    {
    if( op1.sign > 0 )
        return op1.dt.size()>op2.dt.size()? true:false;
    else
        return op1.dt.size()>op2.dt.size()? false: true;
    }
}

bool operator >= ( const BigInt & op1, const BigInt & op2 )
{
    return op1 == op2 || op1 > op2;
}

bool operator <= ( const BigInt & op1, const BigInt & op2 )
{
    return op1 == op2 || op1 < op2;
}

bool operator < ( const BigInt & op1, const BigInt & op2)
{
    if( op1.sign >  op2.sign)
    return true;
    else if( op1.sign < 0 && op2.sign <0 )
    {
    return fab(op1) > fab(op2) ;
    }
    else
    return ! (op1 > op2);
}

BigInt operator += ( BigInt & op1,const BigInt & op2 )
{
    if (op1.sign != op2.sign)
    {
    BigInt tmp(op2);
    tmp=-tmp;
    op1-=tmp;
    return op1;
    }
    BigInt bg,other;
    bg=fab(op1)>fab(op2)?op1:op2;
    other= bg==op1? op2: op1;
    unsigned int carry = 0;
    std::deque<unsigned int>::iterator it;
    std::deque<unsigned int>::const_iterator jt;
    for( it = bg.dt.begin(),jt = other.dt.begin(); it < bg.dt.end() || jt < other.dt.end() || carry > 0 ; )
    {
    if( it < bg.dt.end() && jt < other.dt.end() )
    {
        carry += * it + *jt ;
        *it = carry % BigInt::Base;
        carry /= BigInt::Base;
        it ++;
        jt ++;
    }
    else if ( it < bg.dt.end() )
    {
        carry += *it;
        *it = carry % BigInt::Base;
        carry /= BigInt::Base;
        it ++;
    }
    else if( jt< other.dt.end())
    {
        carry += *jt;
        bg.dt.push_back(carry % BigInt::Base);
        carry /= BigInt::Base;
        jt++;
    }
    else
    {
        while ( carry > 0 )
        {
        bg.dt.push_back(carry%BigInt::Base);
        carry /= BigInt::Base;
        }
    }
    }
    op1=bg;
    return op1;
}

BigInt operator + ( const BigInt & op1, const BigInt & op2 )
{
    BigInt ret(op1);
    ret+=op2;
    return ret;
}

 
BigInt operator -=( BigInt & bg, const BigInt &other )
{
    if ( bg.sign != other.sign )
    {
    BigInt tmp(other);
    tmp=-tmp;
    bg+=tmp;
    return bg;
    }
    int carry=0;
    BigInt op1,op2;
    if ( bg.dt.size() == other.dt.size() )
    {
    op1 = bg.dt.back() >= other.dt.back() ? bg: other;
    op2 = bg.dt.back() >= other.dt.back() ? other: bg;
    }
    else
    {
    op1 = bg.dt.size() > other.dt.size()? bg:other;
    op2 = bg.dt.size() > other.dt.size()? other:bg;
    } 
    op1.sign= (op1 == bg );
    assert( op1.dt.size() >= op2.dt.size() );
    std::deque<unsigned int>::iterator it;
    std::deque<unsigned int>::const_iterator jt;
    try
    {
    for( it =  op1.dt.begin(),jt = op2.dt.begin(); it< op1.dt.end()||jt<op2.dt.end()|| carry < 0; )
    {
        if( it < op1.dt.end() && jt<op2.dt.end() )
        {
        carry += (int) *it- (int)*jt;
        *it= carry >=0 ? (unsigned)(carry % BigInt::Base) :(unsigned) (carry + BigInt::Base)% BigInt::Base;
        carry = carry >= 0 ? carry/BigInt::Base: -((-carry + BigInt::Base)/(BigInt::Base));
        it++;
        jt++;
        }
        else if ( it < op1.dt.end() )
        {
        carry += (int)* it;
        *it= carry >=0 ?(unsigned) (carry % BigInt::Base) :(unsigned) (carry + BigInt::Base)% BigInt::Base;
        carry = carry >= 0 ? carry/BigInt::Base: -((-carry + BigInt::Base)/(BigInt::Base));
        it++;
        }
        else if( jt < op2.dt.end() )
        {
        throw std::exception();
        }
    }
    }catch( std::exception e )
    {
    std::cerr<<e.what()<<std::endl;
    }
    op1.trim();
    bg=op1;
    return bg;
}

BigInt operator -( const BigInt & op1, BigInt &op2)
{
    BigInt ret(op1);
    ret-=op2;
    return ret;
}

BigInt operator *= ( BigInt &  bg, int other)
{
    bg.sign = bg.sign== (other>=0?true:false) ? true:false;
    other = other>=0? other:-other;
    unsigned int carry=0;
    if ( 0 == other )
    {
    bg.dt.clear();
    bg.dt.push_back(0);
    return bg;
    }
    std::deque<unsigned int>::iterator it=bg.dt.begin();
    for( ; it != bg.dt.end(); it ++ )
    {
    carry += *it* other;
    *it= carry % BigInt::Base;
    carry /= BigInt::Base;
    }
    while ( carry > 0 )
    {
    bg.dt.push_back(carry%BigInt::Base);
    carry/=BigInt::Base;
    }
    return bg;
}

BigInt operator * ( int n, BigInt & other)
{
    BigInt bg(other);
    bg*=n;
    return bg;
}

BigInt operator *( const int n,const BigInt & bg)
{
    BigInt ret(bg);
    ret*=n;
    return ret;
}
BigInt operator *=(BigInt& op1, const BigInt & op2)
{
    if ( op1 == BigInt(0) || op2 == BigInt(0) )
    return BigInt (0);
    BigInt out(0);
    BigInt tmp;
    int carry=0;
    for( std::deque<unsigned>::const_iterator it = op2.dt.begin(); it != op2.dt.end();it ++,carry++ )
    {
    tmp= op1* (*it);
    for( int i=0;i<carry; i++)
    {
        tmp.dt.push_front(unsigned(0));
    }
    out+=tmp;
    }
    op1=out;
    op1.sign= !op1.sign ^ op2.sign;
    return op1;
}
BigInt operator * ( const BigInt &op1, const BigInt & op2 )
{
    BigInt ret(op1);
    ret*=op2;
    return ret;
}

BigInt operator * ( const BigInt & op1, int other)
{
    BigInt ret(op1);
    ret*=other;
    return ret;
}

BigInt fab( const BigInt & bg)
{
    BigInt ret(bg);
    ret.sign=true;
    return ret;
}

BigInt pow( const BigInt & bg, int n)
{
    assert( n >= 0 );
    if ( n == 0 )
    return BigInt(0);
    BigInt ret(bg);
    for( int i=0; i < n-1 ; i++)
    {
    ret*=bg;
    }
    return ret;
}

#include<climits>
#include<ctime>
int main()
{
    BigInt bg(11111),other(-1111111);
    BigInt sum=bg*other;
    std::cout<<sum<<std::endl;
}


[ 本帖最后由 Devil_W 于 2010-6-7 00:12 编辑 ]
搜索更多相关主题的帖子: 效率 bug 
2010-06-06 18:42
BlueGuy
Rank: 16Rank: 16Rank: 16Rank: 16
等 级:版主
威 望:29
帖 子:4476
专家分:4055
注 册:2009-4-18
收藏
得分:0 
年底我决定用我那可怜的薪水买个笔记本 。/

我就是真命天子,顺我者生,逆我者死!
2010-06-06 18:46
UserYuH
Rank: 12Rank: 12Rank: 12
来 自:毅华
等 级:火箭侠
威 望:8
帖 子:720
专家分:3300
注 册:2009-8-10
收藏
得分:0 
回复 2楼 BlueGuy
这样回复楼主有点灌水了吧?不过你要买什么牌子的本本呢?什么价位的?

努力—前进—变老—退休—入土
2010-06-07 00:05
Devil_W
Rank: 10Rank: 10Rank: 10
等 级:青峰侠
威 望:9
帖 子:1160
专家分:1797
注 册:2009-9-14
收藏
得分:0 
fix bug
2010-06-07 00:12
BlueGuy
Rank: 16Rank: 16Rank: 16Rank: 16
等 级:版主
威 望:29
帖 子:4476
专家分:4055
注 册:2009-4-18
收藏
得分:0 
回复 3楼 UserYuH
我的意思是说,爱莫能助 /  
5000左右的吧 ,/  你潜水时间长了, 出来透透气?

[ 本帖最后由 BlueGuy 于 2010-6-7 08:43 编辑 ]

我就是真命天子,顺我者生,逆我者死!
2010-06-07 08:27
forever74
Rank: 16Rank: 16Rank: 16Rank: 16
来 自:CC
等 级:版主
威 望:58
帖 子:1694
专家分:4282
注 册:2007-12-27
收藏
得分:0 
建议转到PP版
哦,是CPP

对宇宙最严谨的描述应该就是宇宙其实是不严谨的
2010-06-07 09:07
Devil_W
Rank: 10Rank: 10Rank: 10
等 级:青峰侠
威 望:9
帖 子:1160
专家分:1797
注 册:2009-9-14
收藏
得分:0 
以下是引用forever74在2010-6-7 09:07:35的发言:

建议转到PP版
哦,是CPP


不care了, 我的code放到哪里都会是精华。
2010-06-07 10:05
lintaoyn
Rank: 11Rank: 11Rank: 11Rank: 11
等 级:小飞侠
威 望:4
帖 子:606
专家分:2499
注 册:2009-4-8
收藏
得分:0 
原来这样就能成为精华贴…在家里我也写了个,因为没实现/就没敢贴出来…

迭代的是人,递归的是神。
2010-06-07 11:50
BlueGuy
Rank: 16Rank: 16Rank: 16Rank: 16
等 级:版主
威 望:29
帖 子:4476
专家分:4055
注 册:2009-4-18
收藏
得分:0 
回复 8楼 lintaoyn
是的, 精华帖很容易得的, 发出来共享一下吧

我就是真命天子,顺我者生,逆我者死!
2010-06-07 11:54
lintaoyn
Rank: 11Rank: 11Rank: 11Rank: 11
等 级:小飞侠
威 望:4
帖 子:606
专家分:2499
注 册:2009-4-8
收藏
得分:0 
回复 9楼 BlueGuy
这些天忙着整理论文要毕业了,代码在家里电脑里,15号能回家的~

迭代的是人,递归的是神。
2010-06-07 12:07
快速回复:写了个大数库, 大家看看效率,或者是否有bug
数据加载中...
 
   



关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.025599 second(s), 9 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved