写了个大数库, 大家看看效率,或者是否有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 编辑 ]