大数乘方，看看各位的速度,该怎么处理

大数乘方，看看各位的速度
我新编了一个c程序，用于计算大数乘法，这里不比阶乘，只比乘方，看看各位算一个随机100位的数的100次方，用时多少。时间最好用多少次i++表示，即：算1亿次i++，看用的时间。我用的底数是123456111119964561319456454545431532451321546324545632442564394564545454315324513215463245456324425643，算1亿次i++用的时间是1020毫秒（取三次平均值），算一百次方用时3497毫秒（三次平均值）。
声明：我不是在比速度，只是在技术交流一下。看看有没有速度更快的。

[解决办法]
用fft的乘法和logn幂次，估计1千位的100次方也只要1秒左右。1万位能不能5秒里偶没把握。
当然基本上位数没上万的时候乘法还是用朴素。
[解决办法]
C/C++ code
    void    Neg()    {        Sign = -Sign;    }    Bool    IsZero() const    {        return !GetSign();    }    Int32    operator [] (Int32 pos) const    {        return BigNumberData::pData[pos];    }    Int32&    operator [] (Int32 pos)    {        //Dangerous, if pData is shared by another bignumber        return BigNumberData::pData[pos];    }    Int32    Capacity() const    {        return BigNumberData::DataSize;    }    void    Reserve(Int32 size)    {        if (Capacity() &lt; size)        {            BigNumberData    temp(size);            Int32 *    buff = temp.Buffer();            for (Int32 i = 0; i &lt; Capacity(); ++i)            {                buff[i] = BigNumberData::pData[i];            }            BigNumberData::Swap(temp);        }    }protected:    void    ReadCharNumber(const TCHAR* _pCharNumber)    {        RT_CONDITION(_pCharNumber != NULL);        Int32 s = 1;        Int32 i = 0, j = 0;        if (_pCharNumber[i] == '-')        {            s = -s;            ++i;        }        else if (_pCharNumber[i] == '+')        {            ++i;        }        for (j = i; _pCharNumber[j] != '\0'; ++j)            ;        --j;        Int32 length = j - i + 1;        if (length == 0)        {            ZeroInit();            return;        }        Int32    size = CalStoreLength(length);        BigNumberData temp_data(size);        BigNumberData::Swap(temp_data);        Int32 * temp = BigNumberData::Buffer();        Int32    curr = 0;        while (j &gt;= i)        {            Int32 value = 0;            Int32 count = 0;            Int32 base = 1;            while (j &gt;= i && count++ &lt; DIG_COUNT)            {                value += base * (_pCharNumber[j--] - '0');                base *= 10;            }            temp[curr++] = value;        }        Length = size;        Sign = 1;        ZeroAdjust();    }    void    ZeroAdjust() const    {        int i;        for (i = Length - 1; i &gt;= 0 && BigNumberData::pData[i] == 0; --i)            ;        if (i &lt; 0)        {            Length = 1;            Sign = 0;        }        else        {            Length = i + 1;        }    }private:    Int32    CalStoreLength(Int32 length)    {        Int32 ret = length / DIG_COUNT;        if (length % DIG_COUNT)        {            ++ret;        }        return ret;    }    void    ZeroInit()    {        BigNumberData temp_data(4);        BigNumberData::Swap(temp_data);        memset(this-&gt;Buffer(), 0, sizeof(Int32) * 4);        Length = 1;        Sign = 0;    }public:    static    Bool    AbsCompare(const BigNumber& l, const BigNumber& r)    {        l.ZeroAdjust();        r.ZeroAdjust();        Int32    l_length = l.GetLength();        Int32    r_length = r.GetLength();        if (l_length != r_length)        {            return l_length - r_length;        }        for (--l_length; l_length &gt;= 0 && l[l_length] == r[l_length]; --l_length)            ;        return l_length &gt;= 0 ? l[l_length] - r[l_length] : 0;    }    static    BigNumber    AbsAddImpl(BigNumber& l, const BigNumber& r)    {        l.ZeroAdjust();        r.ZeroAdjust();        Int32    longer            = l.GetLength();        Int32    shorter            = r.GetLength();        Int32*    longer_buffer    = l.Buffer();        Int32*    shorter_buffer    = r.Buffer();        RT_CONDITION(longer &gt;= shorter);        Int32        inc = 0;        Int32        curr = 0;        for (; curr &lt; shorter; ++curr)        {            inc += longer_buffer[curr] + shorter_buffer[curr];            longer_buffer[curr] = inc % BIG_NUMBER_BASE;            inc /= BIG_NUMBER_BASE;        }        for (; curr &lt; longer; ++curr)        {            Int32 value = longer_buffer[curr] + inc;            longer_buffer[curr] = value % BIG_NUMBER_BASE;            inc = value / BIG_NUMBER_BASE;        }        if (inc)        {            l.Reserve(curr+1);            l[curr++] = inc;        }        l.Length = curr;        return l;    }    static    BigNumber    AbsAdd(const BigNumber& l, const BigNumber& r)    {        l.ZeroAdjust();        r.ZeroAdjust();        if (l.Length &gt;= r.Length)        {            BigNumber    l_temp(l.Buffer(), l.Length, BigNumberData::COPY_DATA);            return AbsAddImpl(l_temp, r);        }        else        {            BigNumber    l_temp(r.Buffer(), r.Length, BigNumberData::COPY_DATA);            return AbsAddImpl(l_temp, l);        }    }    static    BigNumber    AbsSubImpl(BigNumber& l, const BigNumber& r)    {        Int32    longer            = l.GetLength();        Int32    shorter            = r.GetLength();        Int32*    shorter_buffer    = r.Buffer();        Int32*    longer_buffer    = l.Buffer();        (void)longer;        RT_CONDITION(BigNumber::AbsCompare(l, r) &gt;= 0);        for (Int32 curr = 0; curr &lt; shorter; ++curr)        {            Int32 value = longer_buffer[curr] - shorter_buffer[curr];            while (value &lt; 0)            {                --longer_buffer[curr+1];                value += BIG_NUMBER_BASE;            }            longer_buffer[curr] = value;        }        l.ZeroAdjust();        return l;    }    static    BigNumber    AbsSub(const BigNumber& l, const BigNumber& r)    {        l.ZeroAdjust();        r.ZeroAdjust();        if (l.Length &gt;= r.Length)        {            BigNumber    l_temp(l.Buffer(), l.Length, BigNumberData::COPY_DATA);            return AbsSubImpl(l_temp, r);        }        else        {            BigNumber    l_temp(r.Buffer(), r.Length, BigNumberData::COPY_DATA);            return AbsSubImpl(l_temp, l);        }    }    static    BigNumber    AbsMulImpl(const BigNumber& l, const BigNumber& r)    {        l.ZeroAdjust();        r.ZeroAdjust();        Int32    l_length    = l.GetLength();        Int32    r_length    = r.GetLength();        Int32    ret_length    = l_length + r_length;        BigNumber    ret(NULL, ret_length);        Int32*    ret_buffer    = ret.Buffer();        Int32*    l_buffer    = l.Buffer();        Int32*    r_buffer    = r.Buffer();        for (Int32 i = 0; i &lt; ret_length; ++i)        {            ret_buffer[i] = 0;        }        for (Int32 i = 0; i &lt; r_length; ++i)        {            Int32 t = r_buffer[i];            Int32 inc = 0;            Int32 j = 0;            for (; j &lt; l_length; ++j)            {                inc += t * l_buffer[j] + ret_buffer[i+j];                ret_buffer[i+j] = inc % BIG_NUMBER_BASE;                inc /= BIG_NUMBER_BASE;            }            for ( ;inc; inc /= BIG_NUMBER_BASE)            {                ret_buffer[i+j++] = inc % BIG_NUMBER_BASE;            }        }        ret.Length = ret_length;        ret.ZeroAdjust();        return ret;    }    static    BigNumber    AbsMul(const BigNumber& l, const BigNumber& r)    {        return AbsMulImpl(l, r);    }    static    Int32        DoMemMul(Int32* ResultBuff, Int32* LeftBuff, Int32 LeftLength, Int32 RightValue)    {        Int32    curr = 0;        Int32    inc = 0;        for (; curr &lt; LeftLength; ++curr)        {            Int32 value = RightValue * LeftBuff[curr] + inc;            ResultBuff[curr] = value % BIG_NUMBER_BASE;            inc = value / BIG_NUMBER_BASE;        }        if (inc)        {            ResultBuff[curr++] = inc;        }        return curr;    }    static    Int32        DoSub(Int32* LeftBuff, Int32 hi_l, Int32 lo_l,                              Int32* RightBuff, Int32 hi_r, Int32 lo_r,                              Int32 test, Int32* temp)    {            int hi2 = DoMemMul(temp+lo_r, RightBuff, hi_r-lo_r+1, test) - 1;            if (hi2 &gt;= hi_l - lo_l + 1)            {                return 0;            }            if (hi_l - lo_l == hi2 - lo_r)            {                for (Int32 i = hi_l, j = hi2; i &gt;= lo_l; --i, --j)                    {                        if(LeftBuff[i] &lt; temp[j])                        {                            return 0;                        }                        if (LeftBuff[i] &gt; temp[j])                        {                            break;                        }                    }            }            for (Int32 i = lo_r, j = lo_l; i &lt;= hi2; ++i, ++j)            {                if ((LeftBuff[j] -= temp[i]) &lt; 0)                {                    LeftBuff[j] += BIG_NUMBER_BASE;                    --LeftBuff[j+1];                }            }            return 1;    } 
 
[解决办法]
C/C++ code    static    BigNumber    AbsDivImpl(BigNumber& remain, const BigNumber& r)    {        DataBlock&lt;int&gt;    buffer_data(remain.Length + 5);        remain.ZeroAdjust();        r.ZeroAdjust();        Int32    l_length    = remain.GetLength();        Int32    r_length    = r.GetLength();        Int32    ret_length    = l_length - r_length + 1;        BigNumber    ret(NULL, ret_length);        Int32*    ret_buffer    = ret.Buffer();        Int32*    l_buffer    = remain.Buffer();        Int32*    r_buffer    = r.Buffer();        Int32    curr = ret_length - 1;        Int32    hi_l = l_length - 1, lo_l = curr;        Int32    hi_r = r_length - 1, lo_r = 0;        for (; curr &gt;= 0; --curr, --lo_l)        {            Int32    test;            if (r_length &gt; 1)            {                if (hi_l-lo_l&gt;hi_r-lo_r)                {                    test = (l_buffer[hi_l]*BIG_NUMBER_BASE + l_buffer[hi_l-1]) / r_buffer[hi_r];                }                else                {                    test = (l_buffer[hi_l]*BIG_NUMBER_BASE + l_buffer[hi_l-1]) / (r_buffer[hi_r]*BIG_NUMBER_BASE + r_buffer[hi_r-1]);                }            }            else            {                if (hi_l-lo_l+1&gt;1)                {                    test = (l_buffer[hi_l]*BIG_NUMBER_BASE + l_buffer[hi_l-1]) / r_buffer[hi_r];                }                else                {                    test = l_buffer[hi_l]/r_buffer[hi_r];                }            }            for( ; test &gt; 0; --test)            {                if (BigNumber::DoSub(l_buffer, hi_l, lo_l, r_buffer,  hi_r, lo_r, test, buffer_data.Buffer()))                {                    break;                }            }                        for (;l_buffer[hi_l] == 0 && hi_l &gt;= lo_l; --hi_l)                ;            ret_buffer[curr] = test;        }        ret.Length = ret_length;        ret.ZeroAdjust();        remain.ZeroAdjust();        return ret;    }    static    BigNumber    AbsDiv(const BigNumber& l, const BigNumber& r)    {        BigNumber    l_temp(l.Buffer(), l.Length, BigNumberData::COPY_DATA);        return AbsDivImpl(l_temp, r);    }public:    BigNumber    operator - () const    {        BigNumber ret(*this);        ret.Neg();        return ret;    }    BigNumber    operator + () const    {        return *this;    }    BigNumber&    operator += (const BigNumber& other)    {        *this = *this + other;        return *this;    }    BigNumber&    operator -= (const BigNumber& other)    {        *this = *this - other;        return *this;    }    BigNumber&    operator *= (const BigNumber& other)    {        *this = *this * other;        return *this;    }    BigNumber&    operator /= (const BigNumber& other)    {        *this = *this / other;        return *this;    }    BigNumber&    operator ^= (Int32 n)    {        *this = *this ^ n;        return *this;    }    BigNumber& operator ++ ()    {        *this = *this + 1;        return *this;    }    BigNumber operator ++ (int)    {        BigNumber ret(*this);        *this = *this + 1;        return ret;    }    BigNumber& operator -- ()    {        *this = *this - 1;        return *this;    }    BigNumber operator -- (int)    {        BigNumber ret(*this);        *this = *this - 1;        return ret;    }protected:    mutable    Int32    Length;    mutable    Int32    Sign;};inlineOutStream&    operator &lt;&lt; (OutStream& o, const BigNumber& n){    Int32 curr = n.GetLength() - 1;    if (n.GetSign() &lt; 0)    {        o &lt;&lt; '-';    }    o &lt;&lt; n[curr--];    while (curr&gt;=0)    {        o.fill('0');        o.width(DIG_COUNT);        o &lt;&lt; n[curr--];    }    return o;}inlineBigNumber    operator + (const BigNumber& l, const BigNumber& r){    if (l.IsZero())    {        return r;    }    if (r.IsZero())    {        return l;    }    if (l.GetSign() == r.GetSign())    {        BigNumber    ret(BigNumber::AbsAdd(l, r));        ret.Sign = l.Sign;        ret.ZeroAdjust();        return ret;    }    Int32    cmp;    if ((cmp = BigNumber::AbsCompare(l, r)) &gt; 0)    {        BigNumber    ret(BigNumber::AbsSub(l, r));        ret.Sign = l.Sign;        ret.ZeroAdjust();        return ret;    }    else if (cmp &lt; 0)    {        BigNumber    ret(BigNumber::AbsSub(r, l));        ret.Sign = r.Sign;        ret.ZeroAdjust();        return ret;    }    else    {        return 0;    }}inlineBigNumber    operator - (const BigNumber& l, const BigNumber& r){    if (l.IsZero())    {        return -r;    }    if (r.IsZero())    {        return l;    }    if (l.GetSign() != r.GetSign())    {        BigNumber    ret(BigNumber::AbsAdd(l, r));        ret.Sign = l.Sign;        ret.ZeroAdjust();        return ret;    }    Int32    cmp;    if ((cmp = BigNumber::AbsCompare(l, r)) &gt; 0)    {        BigNumber    ret(BigNumber::AbsSub(l, r));        ret.Sign = l.Sign;        ret.ZeroAdjust();        return ret;    }    else if (cmp &lt; 0)    {        BigNumber    ret(BigNumber::AbsSub(r, l));        ret.Sign = -r.Sign;        ret.ZeroAdjust();        return ret;    }    else    {        return 0;    }}inlineBigNumber    operator * (const BigNumber& l, const BigNumber& r){    Int32    s = l.GetSign() * r.GetSign();    if (s == 0)    {        return 0;    }    BigNumber    ret(BigNumber::AbsMul(l, r));    ret.Sign = s;    return ret;}inlineBigNumber    operator / (const BigNumber& l, const BigNumber& r){    Int32    s = l.GetSign() * r.GetSign();    Int32    cmp = BigNumber::AbsCompare(l, r);    if (s == 0 || cmp &lt; 0)    {        return 0;    }    if (cmp == 0)    {        return 1;    }    BigNumber    ret(BigNumber::AbsDiv(l, r));    ret.Sign = s;    return ret;}inlineBigNumber    operator ^ (const BigNumber& l, Int32 n){    BigNumber    ret(1);    BigNumber    t(l);    for (;n; n /= 2)    {        if (n & 1)        {            ret *= t;        }        t *= t;    }    return ret;}inlineBigNumber    operator ^ (const BigNumber& l, BigNumber& n){    BigNumber    ret(1);    BigNumber    t(l);    for (;!n.IsZero(); n /= 2)    {        if (n[0]&1)        {            ret *= t;        }        t *= t;    }    return ret;}int main(void){    BigNumber x("123456111119964561319456454545431532451321546324545632442564394564545454315324513215463245456324425643");    x ^= 100;    cout &lt;&lt; clock() &lt;&lt; endl;    cout &lt;&lt; x &lt;&lt; endl;    return 0;} 
 
[解决办法]
C/C++ code//这个写在最前面,然后我前面贴的两份代码依次...//可恶的CSDN,只让我连续回复三次...#include &lt;iostream&gt;#include &lt;deque&gt;#include &lt;vector&gt;#include &lt;ctime&gt;#include &lt;cstring&gt;using namespace std;    #define        tcout             std::cout    #define        tcin            std::cin    #define        tcerr            std::cerr    #define        tostream        std::ostream    #define        tistream        std::istream    #define        tiostream        std::iostream    #define        tfstream        std::fstream    #define        tifstream        std::ifstream        #define        tstringstream    std::stringstream    #define        tstring            std::string    #define        tendl            std::endl        #define        OutStream        tostream    #define        dbg_new            new    #define        dbg_delete(x)    delete x    #define        dbg_deletea(x)    delete[] x        typedef    float                    Float32;    typedef    double                    Float64;        typedef    unsigned int            UInt32;    typedef    unsigned long long        UInt64;        typedef    int                        Int32;    typedef    long long                Int64;        typedef    Int32                    Bool;        typedef    Float64                    Float;        const Float                        SDL_eps = 1e-10;    #define        RT_CONDITION(x) (void)(x)        #define        TCHAR char/***    Data    Block*    If _DataType is not POD, operator delete invoked by _DataType's destructor won't be detected.**/template&lt;typename _DataType&gt;class    DataBlock{    typedef    _DataType        DataType;public:    enum    {NOT_COPY_DATA = false, COPY_DATA = true, COPY_ALL = -1};    DataBlock()        :    pData(0),            pRefCount(0),            DataSize(0)    {    }    DataBlock(Int32    size)    {        RT_CONDITION(size &gt; 0);        pData        =    dbg_new    DataType[size];        pRefCount    =    dbg_new    Int32(0);        DataSize    =    size;        IncReference();    }    DataBlock(DataType * data, Int32 size, Bool CanCopy = NOT_COPY_DATA, Int32 RequiredSize = COPY_ALL)    {        DoBindData(data, size, CanCopy, RequiredSize);        IncReference();    }    DataBlock(const DataBlock& other)    {        pData        =    other.pData;        pRefCount    =    other.pRefCount;        DataSize    =    other.DataSize;        IncReference();    }    ~DataBlock()    {        DecReference();    }    DataBlock&    operator  = (const DataBlock& other)    {        if (this != &other)        {            DecReference();            DataBlock    temp(other);            Swap(temp);            IncReference();        }        return *this;    }    void    Swap(DataBlock& other)    {        std::swap(pData, other.pData);        std::swap(pRefCount, other.pRefCount);        std::swap(DataSize, other.DataSize);    }    void    SetOwned()    {        if (pRefCount && *pRefCount &gt; 1)        {            DataBlock    temp(pData, DataSize, COPY_DATA,  COPY_ALL);            Swap(temp);        }    }    void    BindData(DataType * data, Int32 size, Bool CanCopy = NOT_COPY_DATA, Int32 RequiredSize = COPY_ALL)    {        DecReference();        DoBindData(data, size, CanCopy, RequiredSize);        IncReference();    }    DataType*    Buffer() const    {        return pData;    }    DataType    operator [] (Int32 pos) const    {        return pData[pos];    }    DataType&    operator[] (Int32 pos)    {        return pData[pos];    }protected:    void    IncReference() const    {        if (pRefCount)        {            ++*pRefCount;        }    }    void    DecReference()    {        if (pRefCount && !--*pRefCount)        {            RT_CONDITION(pData != 0);            DoRelease();        }    }private:    void    DoBindData(DataType * data, Int32 size, Bool CanCopy, Int32 RequiredSize)    {        if (CanCopy == COPY_DATA || data == NULL)        {            if (RequiredSize == COPY_ALL)            {                DataSize    =    size;            }            else            {                RT_CONDITION(size &gt;= RequiredSize);                DataSize    =    RequiredSize;            }            pData        =    dbg_new DataType[DataSize];                pRefCount    =    dbg_new Int32(0);            if (data)            {                for (int i = 0; i &lt; DataSize; ++i)                {                    pData[i] = data[i];                }            }        }        else        {            DataSize    =    size;            pData        =    data;            pRefCount    =    0;        }    }    void    DoRelease()    {        dbg_deletea(pData);        pData = 0;        dbg_delete(pRefCount);        pRefCount    =    0;    }protected:    DataType    *    pData;    Int32        *    pRefCount;    Int32            DataSize;};typedef    DataBlock&lt;Int32&gt;    BigNumberData;const Int32    BIG_NUMBER_BASE    =    10000;const Int32    DIG_COUNT        =    4;class    BigNumber    :    protected    BigNumberData{    friend    inline    BigNumber    operator + (const BigNumber& l, const BigNumber& r);    friend    inline    BigNumber    operator - (const BigNumber& l, const BigNumber& r);    friend    inline    BigNumber    operator * (const BigNumber& l, const BigNumber& r);    friend    inline    BigNumber    operator / (const BigNumber& l, const BigNumber& r);    friend    inline    BigNumber    operator ^ (const BigNumber& l, Int32 n);    friend    inline    BigNumber    operator ^ (const BigNumber& l, BigNumber& r);    friend    inline    BigNumber    operator % (const BigNumber& l, const BigNumber& r);    friend    inline    Bool        operator &gt; (const BigNumber& l, const BigNumber& r);    friend    inline    Bool        operator &lt; (const BigNumber& l, const BigNumber& r);    friend    inline    Bool        operator == (const BigNumber& l, const BigNumber& r);    friend    inline    Bool        operator &gt;= (const BigNumber& l, const BigNumber& r);    friend    inline    Bool        operator &lt;= (const BigNumber& l, const BigNumber& r);    friend    inline    OutStream&    operator &lt;&lt; (std::ostream& o, const BigNumber& n);    friend    inline    BigNumber    GCD(const BigNumber& l, const BigNumber& r);    friend    inline    BigNumber    GCDEX(const BigNumber& p, const BigNumber& m);    friend    inline    BigNumber    fabs(const BigNumber& n);    friend    inline    BigNumber    abs(const BigNumber& n);public:    typedef    BigNumber    SelfType;    BigNumber(Int32 value = 0)    {        ZeroInit();        if (value != 0)        {            Sign = value &gt; 0 ? 1 : -1;            if (value &lt; 0)            {                value = - value;            }            Int32 curr = 0;            for (;value; value /= BIG_NUMBER_BASE, ++curr)            {                BigNumberData::pData[curr] = value % BIG_NUMBER_BASE;            }            Length = curr;        }    }    BigNumber(const TCHAR* _pCharNumber)    {        ReadCharNumber(_pCharNumber);    }    BigNumber(const BigNumber& other)        :    BigNumberData(other)    {        Length        = other.Length;        Sign        = other.Sign;    }    BigNumber(Int32* _pBuff, Int32 size, Int32 copy = BigNumberData::NOT_COPY_DATA, Int32 copy_size = BigNumberData::COPY_ALL)        :    BigNumberData(_pBuff, size, copy, copy_size),            Length(size),            Sign(1)    {        if (_pBuff == 0)        {            memset(pData, 0, sizeof(Int32) * size);        }        ZeroAdjust();    }    BigNumber&    operator = (const BigNumber& other)    {        if (&other != this)        {            BigNumber    temp(other);            Swap(temp);        }        return *this;    }    void    Swap(BigNumber& other)    {        BigNumberData::Swap(other);        std::swap(Length, other.Length);        std::swap(Sign, other.Sign);    }    Int32*    Buffer() const    {        return BigNumberData::Buffer();    }    Int32    GetLength() const    {        return Length;    }    Int32    GetSign() const    {        return Sign;    } 
 
[解决办法]
探讨
原来如此，谢谢baihacker大哥了，不过好像还是有些error
bcc中，出错的是这两句：
&#160; &#160; typedef&#160; &#160; unsigned long long&#160; &#160; &#160; &#160; UInt64;
&#160; &#160; typedef&#160; &#160; long long&#160; &#160; &#160; &#160; &#160; &#160; &#160; &#160; Int64;
错误记录：
Error E2176 D:\Backup\我的文档\bignumber-baihacker.cpp 33: Too many types in declaration
Error E2176 D:\Backup\我的文档\bignumber-baihacker.cpp 36: Too many types in declaration

warning我就不复制了
大数乘方看看各位的速度,该怎么处理

热点推荐
