tlargefloat.cpp

一个很叨 的算法作业,很强大的源代码 很强大的源代码很强大的源代码

    Zero();
    long new_size=TDigits(emLongDoubleDigits+1).GetDigitsArraySize();
    if ((long)m_Digits.size()<new_size)
        m_Digits.resize(new_size,0);
    if (fValue==0)
        return;
    else if (fValue>0)
        m_Sign=1;
    else
    {
        m_Sign=-1;
        fValue=-fValue;
    }

    m_Exponent=(long)floor(log10(fValue));
    fValue/=pow(10.0,(long)m_Exponent.AsInt());
    long size=m_Digits.size();
    for (long i=0;i<size;++i)//得到小数位
    {
        if (fValue<=0) break;
        fValue*=emBase;
        TInt32bit iValue=(TInt32bit)floor(fValue);
        fValue-=iValue;
        m_Digits[i]=iValue;
    }      
    
    Canonicity();
}

void TLargeFloat::Swap(SelfType& Value)
{
    if (this==&Value) return;
    m_Digits.swap(Value.m_Digits);
    std::swap(m_Sign,Value.m_Sign);
    std::swap(m_Exponent,Value.m_Exponent);
}

void TLargeFloat::Chs()
{
    m_Sign*=(-1);
}

void TLargeFloat::Abs()
{
    if (m_Sign!=0) m_Sign=1;
}

unsigned long TLargeFloat::GetDigitsLength() const
{
    return m_Digits.size()*em10Power;
}

void TLargeFloat::SetDigitsLength(const TDigits& DigitsLength)
{
    m_Digits.resize(DigitsLength.GetDigitsArraySize(),0);
}

TLargeFloat::SelfType& TLargeFloat::operator =  (const SelfType& Value)
{
    if (this==&Value) return *this;
    m_Digits=Value.m_Digits;
    m_Sign=Value.m_Sign;
    m_Exponent=Value.m_Exponent;
    return *this;
}

TLargeFloat::SelfType& TLargeFloat::operator =  (long double  fValue)
{
    fToLargeFloat(fValue);
    return *this;
}

long double TLargeFloat::AsFloat() const
{
    if ( ((m_Exponent.AsInt())>=emLongDoubleMaxExponent)
        ||((m_Exponent.AsInt())<=emLongDoubleMinExponent) )
    {
        throw TException("ERROR:TLargeFloat::AsFloat()");
    }

    if (m_Sign==0) return 0;
    long double result=m_Sign*pow((long double)10.0,(long double)m_Exponent.AsInt());

    long double r=1;
    long double Sum=0;
    long old_size=m_Digits.size();
    for (long i=0;i<old_size;++i)//得到小数位
    {
        r/=emBase;//r*=(1.0/emBase);
        if (r==0) break; 
        Sum+=(m_Digits[i]*r);
    }       
    return result*Sum;
}
std::string  TLargeFloat::AsString() const
{
    if (m_Sign==0)
        return "0";

    //计算需要的字符串空间大小
    long str_length=2+m_Digits.size()*em10Power;
    if  (m_Sign<0) ++str_length; //负号

    TMaxInt EpValue=m_Exponent.AsInt();
    long UEP_StrLength=0;
    if (EpValue!=0) 
    {
        ++str_length;
        if (EpValue<0)
        {
            EpValue=-EpValue;
            ++str_length;
        }
        UEP_StrLength=0;
        while (EpValue>0)
        {
            EpValue/=10;
            ++UEP_StrLength;
        }
        str_length+=UEP_StrLength;
    }

    std::string result(str_length,' ');
    std::string::value_type* pStr=&result[0];

    //输出字符串
    if  (m_Sign<0) { *pStr='-'; ++pStr; }
    *pStr='0'; ++pStr;   *pStr='.'; ++pStr;

    long dgsize=m_Digits.size();
    for (long i=0;i<dgsize;++i)
    {
        TInt32bit Value=m_Digits[i];
        for (long d=0;d<em10Power;++d)
        {
            pStr[em10Power-1-d]=(char)('0'+(Value%10));
            Value/=10;
        }
        pStr+=em10Power;
    }

    EpValue=m_Exponent.AsInt();
    if (EpValue!=0) 
    {
        *pStr='e'; ++pStr;
        if (EpValue<0)
        {
            EpValue=-EpValue;
            *pStr='-'; ++pStr;
        }
        for (long i=0;i<UEP_StrLength;++i)
        {
            pStr[UEP_StrLength-1-i]=(char)('0'+(EpValue%10));
            EpValue/=10;
        }
        pStr+=UEP_StrLength;
    }

    return result;
}

    template<class PChar>
    PChar sToLargeFloat_GetCharIntEnd(PChar int_begin,PChar str_end)
    {
        long int_count=0;
        for (PChar i=int_begin;i<str_end;++i)
        {
            if ( ('0'<=(*i)) && ((*i)<='9') )
                ++int_count;
            else
                break;
        }
        return &int_begin[int_count];
    }

    inline void sToLargeFloat_setAChar(TLargeFloat::TArray& Digits,long set_index,char aChar)
    {
        unsigned long Value=aChar-'0';
        long e10Power_count=TLargeFloat::em10Power-1-(set_index%TLargeFloat::em10Power);
        for (long i=0;i<e10Power_count;++i)
          Value*=10;
        Digits[set_index/TLargeFloat::em10Power]+=Value;
    }

void TLargeFloat::sToLargeFloat(const std::string& strValue)
{
    if (strValue.size()<=0)
    {
        this->Zero();
        return;
    }
    typedef const std::string::value_type* PChar;
    PChar pstr_begin=strValue.c_str();
    PChar pstr_end=&pstr_begin[strValue.size()];

    //str as:  [+|-][0..9][.][0..9][E|e][+|-][0..9] 
    bool is_have_sign=false;
    long  sign=1;
    bool is_have_int=false;
    PChar int_begin=0; PChar int_end=0; 
    bool is_have_dot=false;
    bool is_have_digits=false;
    PChar digits_begin=0; PChar digits_end=0; 
    bool is_have_ep=false;
    bool is_have_ep_sign=false;
    long  ep_sign=1;
    bool is_have_ep_int=false;
    PChar ep_int_begin=0; PChar ep_int_end=0; 

    //处理正负号
    if ((*pstr_begin)=='-') 
    {
        sign = -1;
        is_have_sign=true;
        ++pstr_begin; 
    }
    else if ((*pstr_begin)=='+') 
    {
        is_have_sign=true;
        ++pstr_begin; 
    }

    //处理前面的整数部分
    int_begin=pstr_begin;
    int_end=sToLargeFloat_GetCharIntEnd(int_begin,pstr_end);
    is_have_int=(int_begin!=int_end);
    if ((int_end-int_begin>=2)&&((*int_begin)=='0')) throw TException("ERROR:TLargeFloat::sToLargeFloat(); 0"); //'0?'数字表示错误
    pstr_begin=int_end;
    if (((*pstr_begin)!='.')&&(!is_have_int)) throw TException("ERROR:TLargeFloat::sToLargeFloat(); 1"); //没有任何数字
    
    //处理小数部分
    if ((*pstr_begin)=='.')
    {
        is_have_dot=true;
        ++pstr_begin;

        digits_begin=pstr_begin;
        digits_end=sToLargeFloat_GetCharIntEnd(digits_begin,pstr_end);
        is_have_digits=(digits_begin!=digits_end);
        if ((!is_have_digits)&&(!is_have_int)) throw TException("ERROR:TLargeFloat::sToLargeFloat(); 2"); //没有任何数字
        pstr_begin=digits_end;
    }

    //处理指数部分
    if ( ((*pstr_begin)=='e')||((*pstr_begin)=='E') )
    {
        is_have_ep=true;
        ++pstr_begin;
        //处理指数的正负号
        if ((*pstr_begin)=='-') 
        {
            ep_sign = -1;
            is_have_ep_sign=true;
            ++pstr_begin; 
        }
        else if((*pstr_begin)=='+') 
        {
            is_have_ep_sign=true;
            ++pstr_begin; 
        }
        //处理指数中的整数
        ep_int_begin=pstr_begin;
        ep_int_end=sToLargeFloat_GetCharIntEnd(ep_int_begin,pstr_end);
        is_have_ep_int=(ep_int_begin!=ep_int_end);
        if ((ep_int_end-ep_int_begin>=2)&&((*ep_int_begin)=='0')) throw TException("ERROR:TLargeFloat::sToLargeFloat(); 3"); //'0?'数字表示错误
        pstr_begin=ep_int_end;
        if (!is_have_ep_int) throw TException("ERROR:TLargeFloat::sToLargeFloat(); 4"); //指数没有数字
    }
    if (pstr_begin!=pstr_end) throw TException("ERROR:TLargeFloat::sToLargeFloat(); 5"); //未预料的字符


    //////////////////
    //实际的类型转换

    this->Zero();
    this->m_Sign=sign;
    this->m_Exponent=(int_end-int_begin);
    long need_digits_count=(int_end-int_begin)+(digits_end-digits_begin);
    if ((long)this->GetDigitsLength()<need_digits_count)
      this->SetDigitsLength(need_digits_count);
    long set_index=0;
    PChar set_begin=int_begin;
    for (;set_begin<int_end;++set_begin,++set_index)
        sToLargeFloat_setAChar(this->m_Digits,set_index,*set_begin);
    set_begin=digits_begin;
    for (;set_begin<digits_end;++set_begin,++set_index)
        sToLargeFloat_setAChar(this->m_Digits,set_index,*set_begin);

    if (is_have_ep)
    {
        TExpInt ep=0;
        for (PChar set_begin=ep_int_begin;set_begin<ep_int_end;++set_begin)
        {
            ep*=10;
            ep+=((*set_begin)-'0');
        }
        ep*=ep_sign;
        this->m_Exponent+=ep;
    }
    Canonicity();
}


long  TLargeFloat::Compare(const SelfType& Value) const
{
    if (this==&Value) return 0;
    //(*this)>Value 返回1，小于返回-1，相等返回0

    //比较符号
    if (m_Sign>Value.m_Sign)
        return 1;
    else if(m_Sign<Value.m_Sign)
        return -1;
    else //m_Sign==Value.m_Sign
    {
        if(m_Sign==0)
            return 0;
    }
    //m_Sign==Value.m_Sign

    //比较指数
    if (m_Exponent.AsInt()>Value.m_Exponent.AsInt())
        return m_Sign;
    else if (m_Exponent.AsInt()<Value.m_Exponent.AsInt())
        return -m_Sign;
    else//(m_Exponent==Value.m_Exponent)
    {
        long sizeS=m_Digits.size();
        long sizeV=Value.m_Digits.size();
        long min_size=std::min(sizeS,sizeV);
        for (long i=0;i<min_size;++i)
        {
            if (m_Digits[i]!=Value.m_Digits[i])
            {
                if (m_Digits[i]>Value.m_Digits[i])
                    return m_Sign;
                else //if (m_Digits[i]<Value.m_Digits[i])
                    return -m_Sign;
            }
        }

        //继续比较 处理尾部
        if (sizeS>sizeV)
        {
            for (long i=sizeV;i<sizeS;++i) 
            {
                if (m_Digits[i]>0)
                    return m_Sign;;
            }
        }
        else if (sizeS<sizeV)
        {
            for (long i=sizeS;i<sizeV;++i) 
            {
                if (Value.m_Digits[i]>0)
                    return -m_Sign;
            }
        }
        //sizeS==sizeV
        
        return 0;
    }
}

//////////////////////////////
//+ -

TLargeFloat::SelfType& TLargeFloat::operator += (const SelfType& Value)
{
    if (Value.m_Sign==0)
        return (*this);
    else if (m_Sign==0)
        return (*this)=Value;
    else if (m_Sign==Value.m_Sign)
    {
        TInt32bit oldSign=m_Sign;
        Abs_Add(Value);
        m_Sign=oldSign;
        return *this;
    }
    else
        return *this-=(-Value);
}

TLargeFloat::SelfType& TLargeFloat::operator -= (const SelfType& Value)
{
    if (Value.m_Sign==0)
        return (*this);
    else if (m_Sign==0)
    {
        (*this)=-Value;
        return (*this);
    }
    else if (m_Sign==Value.m_Sign)
    {
        long comResult=this->Compare(Value);    
        if (comResult==0)
        {
            this->Zero();
        }
        else
        {
            Abs_Sub_Abs(Value);
            m_Sign=comResult;
        } 
        return *this;
    }
    else
        return *this+=(-Value);
}

void TLargeFloat::Abs_Add(const SelfType& Value)//绝对值加法
{
    this->Abs();
    SelfType Right(Value);
    Right.Abs();

    //精度一致
    if (m_Digits.size()<Right.m_Digits.size())
        m_Digits.resize(Right.m_Digits.size(),0);
    else if (m_Digits.size()>Right.m_Digits.size())
        Right.m_Digits.resize(m_Digits.size(),0);
    //被加数指数较大就可以了
    if (m_Exponent.AsInt()<Right.m_Exponent.AsInt())
        this->Swap(Right);
    long size=m_Digits.size();

    TMaxInt iMoveRightCount=m_Exponent.AsInt()-Right.m_Exponent.AsInt();
    if (iMoveRightCount>=size*(TMaxInt)TLargeFloat::em10Power) return;
    TLargeFloat_CtrlExponent(Right.m_Digits,iMoveRightCount);//对齐小数点

    TLargeFloat_ArrayAdd(&m_Digits[0],size,&Right.m_Digits[0],size);
    if (m_Digits[0]>=emBase)
        Canonicity();
}

void TLargeFloat::Abs_Sub_Abs(const SelfType& Value)//绝对值减法
{
    this->Abs();
    SelfType Right(Value);
    Right.Abs();

    long comResult=this->Compare(Right);
    if (comResult==0)
    {
        this->Zero();
        return;
    }
    else if (comResult<0)
        this->Swap(Right);

    //精度一致
    if (m_Digits.size()<Right.m_Digits.size())
        m_Digits.resize(Right.m_Digits.size(),0);
    else if (m_Digits.size()>Right.m_Digits.size())
        Right.m_Digits.resize(m_Digits.size(),0);

    long size=m_Digits.size();

    TMaxInt iMoveRightCount=m_Exponent.AsInt()-Right.m_Exponent.AsInt();
    if (iMoveRightCount>=size*(TMaxInt)TLargeFloat::em10Power) return;
    TLargeFloat_CtrlExponent(Right.m_Digits,iMoveRightCount); //对齐小数点

    TLargeFloat_ArraySub(&m_Digits[0],size,&Right.m_Digits[0],size);
    if (m_Digits[0]*10<emBase)
        Canonicity();
}



/////////////////////////////////
// /

    //最大的32bit整数除数M满足: (emBase-1)+(M-1)*emBase<=TInt32bit_MAX_VALUE
    const TInt32bit csMaxDiviValue=TInt32bit_MAX_VALUE/TLargeFloat::emBase -1;
    //最大的整数除数M满足: (emBase-1)+(M-1)*emBase<=TMaxInt_MAX_VALUE
    const TMaxInt csMaxDiviValueBig=TMaxInt_MAX_VALUE/TLargeFloat::emBase -1;

void TLargeFloat::DivInt(TMaxInt iValue)//除以一个整数
{
    if (iValue==0) 
        throw TException("ERROR:TLargeFloat::DivInt()");
    else if (iValue<0)
    {
        iValue=-iValue;
        this->Chs();
        //continue
    }
    if (iValue==1)  return;
    if (this->m_Sign==0) return;

    if (iValue>csMaxDiviValueBig) 
    {
        TLargeFloat y(0.0);
        y.iToLargeFloat(iValue);
        (*this)/=y;
        return;
    }
    
    if (iValue<=csMaxDiviValue)
    {
        TInt32bit iDiv=(TInt32bit)iValue;
        long size=m_Digits.size();
        for (long i=0;i<size-1;++i)
        {
            m_Digits[i+1]+=(m_Digits[i]%iDiv)*emBase;
            m_Digits[i]/=iDiv;
        }
        if (size>=1)
            m_Digits[size-1]/=iDiv;
    }
    else 
    {