bignum.cpp

處理大數 能夠處理負數 加減乘除優先順序

        n *= 10;
        int dig = ( int )floor( n );
        n -= dig;
        if( !dig ) continue;

        int carry = 0;
        for( int j = 0; j < size || carry; j++ )
        {
            int newdig =
                ( i + j < 0 ? afterDot[-( i + j )] : result.digits[i + j] )
                + dig * digits[j]
                + carry;
            ( i + j < 0 ? afterDot[-( i + j )] : result.digits[i + j] ) = newdig % 10;
            if( i + j >= 0 && result.digits[i + j] ) result.size >?= i + j + 1;
            carry = newdig / 10;
        }
    }
    if( !result.size ) result.sign = 0;
    return result;
}

void BigInt::operator*=( long double n )
{
    operator=( operator*( n ) );
}

BigInt BigInt::operator<<( int n )
{
    BigInt result( *this );
    result <<= n;
    return result;
}

void BigInt::operator<<=( int n )
{
    if( n < 0 ) operator>>=( -n );
    else if( n > 0 )
    {
        BigInt mult( 1, 4 * n );
        for( int i = ( 1 << 30 ); i; i >>= 1 )
        {
            mult *= mult;
            if( n & i ) mult *= 2;
        }
        operator*=( mult );
    }
}

BigInt BigInt::operator>>( int n )
{
    BigInt result( *this );
    result >>= n;
    return result;
}

void BigInt::operator>>=( int n )
{
    if( n < 0 ) operator<<=( -n );
    else if( n > 0 )
    {
        BigInt mult( 1, 4 * n );
        for( int i = ( 1 << 30 ); i; i >>= 1 )
        {
            mult *= mult;
            if( n & i ) mult *= 2;
        }
        operator/=( mult );
    }
}
/*
BigInt BigInt::operator&( int n )
{
}

BigInt BigInt::operator&( BigInt n )
{
}

void BigInt::operator&=( int n )
{
}

void BigInt::operator&=( BigInt n )
{
}

BigInt BigInt::operator|( int n )
{
}

BigInt BigInt::operator|( BigInt n )
{
}

void BigInt::operator|=( int n )
{
}

void BigInt::operator|=( BigInt n )
{
}

BigInt BigInt::operator^( int n )
{
}

BigInt BigInt::operator^( BigInt n )
{
}

void BigInt::operator^=( int n )
{
}

void BigInt::operator^=( BigInt n )
{
}

BigInt BigInt::operator~()
{
}
*/
BigInt BigInt::operator,( int n )
{
    BigInt result( 0, size + ( int )sizeof( n ) * 8 );
    for( result.size = 0; n; result.size++ )
    {
        result.digits[result.size] = n % 10;
        n /= 10;
    }
    memcpy( result.digits + result.size, digits, size * sizeof( digits[0] ) );
    result.size += size;
    result.sign = 1;
    result.normalize();
    return result;
}

BigInt BigInt::operator,( BigInt n )
{
    BigInt result( 0, size + n.size );
    memcpy( result.digits, n.digits, n.size * sizeof( n.digits[0] ) );
    memcpy( result.digits + n.size, digits, size * sizeof( digits[0] ) );
    result.size = size + n.size;
    result.sign = 1;
    result.normalize();
    return result;
}

bool BigInt::operator!()
{
    return !size;
}

BigInt::operator bool()
{
    return size;
}

//BigInt::operator int()
//{
//    return toInt();
//}

BigInt::operator string()
{
    return toString();
}

bool BigInt::operator<( BigInt n )
{
    return( compare( n ) < 0 );
}

bool BigInt::operator>( BigInt n )
{
    return( compare( n ) > 0 );
}

bool BigInt::operator==( BigInt n )
{
    return( compare( n ) == 0 );
}

bool BigInt::operator<=( BigInt n )
{
    return( compare( n ) <= 0 );
}

bool BigInt::operator>=( BigInt n )
{
    return( compare( n ) >= 0 );
}

bool BigInt::operator<( int n )
{
    return( compare( BigInt( n ) ) < 0 );
}

bool BigInt::operator>( int n )
{
    return( compare( BigInt( n ) ) > 0 );
}

bool BigInt::operator==( int n )
{
    return( compare( BigInt( n ) ) == 0 );
}

bool BigInt::operator<=( int n )
{
    return( compare( BigInt( n ) ) <= 0 );
}

bool BigInt::operator>=( int n )
{
    return( compare( BigInt( n ) ) >= 0 );
}

int BigInt::compare( BigInt n )
{
    if( sign < n.sign ) return -1;
    if( sign > n.sign ) return 1;
    if( size < n.size ) return -sign;
    if( size > n.size ) return sign;
    for( int i = size - 1; i >= 0; i-- )
    {
        if( digits[i] < n.digits[i] ) return -sign;
        else if( digits[i] > n.digits[i] ) return sign;
    }
    return 0;
}

long double log2( BigInt x, long double epsilon = 0.000000000000001 )
{
    static /* const */ long double O = 0.0;
    if( x.sign <= 0 ) return O / O;     // Return NaN

    long double y = 0.0, z = 1.0, f = 0.0;
    while( x >= 2 )
    {
        if( x.divide( 2 ) ) f += 1.0;
        f /= 2.0;
        y++;
    }
    f += 1.0;
    while( z > epsilon )
    {
        f *= f;
        z /= 2.0;
        if( f >= 2.0 )
        {
            y += z;
            f /= 2.0;
        }
    }
    return y;
}

inline long double log( BigInt x, long double epsilon = 0.000000000000001 )
{
    return log2( x, epsilon ) * 0.6931471805599;
}

inline long double log10( BigInt x, long double epsilon = 0.000000000000001 )
{
    return log2( x, epsilon ) * 0.301029995664;
}

inline long double lg( BigInt x, long double epsilon = 0.000000000000001 )
{
    return log2( x, epsilon );
}

inline long double ln( BigInt x, long double epsilon = 0.000000000000001 )
{
    return log( x, epsilon );
}

/** DEBUG & TESTING **/
int main()
{
    cout << "Constructors and copy constructors:" << endl;
    cout << "12345000 = " << BigInt( 12345000 ) << endl;
    BigInt b = BigInt( 12345000 );
    cout << "12345000 = " << b << endl;
    BigInt c; c = b;
    cout << "12345000 = " << c << endl;
    cout << "1234567890 = " << BigInt( ( long double )1234567890.49999 ) << endl;
    cout << endl;

    cout << "Addition and subtraction:" << endl;
    cout << "123 + 234 = " << ( BigInt( 123 ) + 234 ).toInt() << endl;
    cout << "243 + 999 = " << ( BigInt( 243 ) + BigInt( 999 ) ) << endl;
    cout << "-123 + -321 = " << ( BigInt( -123 ) + BigInt( -321 ) ) << endl;
    cout << "-123 + 321 = " << ( BigInt( -123 ) + BigInt( 321 ) ) << endl;
    cout << "-2 + 5 = " << ( BigInt( -2 ) + 5 ) << endl;
    cout << "-2 + 5 = " << ( BigInt( -2 ) + BigInt( 5 ) ) << endl;
    cout << "-2 + -5 = " << ( BigInt( -2 ) + -5 ) << endl;
    cout << "-2 + -5 = " << ( BigInt( -2 ) + BigInt( -5 ) ) << endl;
    cout << "0 + -5 = " << ( BigInt( 0 ) + -5 ) << endl;
    cout << "0 + -5 = " << ( BigInt( 0 ) + BigInt( -5 ) ) << endl;
    cout << "4567 - 1234 = " << ( 4567 - BigInt( 1234 ) ) << endl;
    cout << "345 - 46 = " << ( BigInt( 345 ) - BigInt( 46 ) ) << endl;
    cout << "2 - 6 = " << ( BigInt( 2 ) - BigInt( 6 ) ) << endl;
    cout << "2 - 6 = " << ( BigInt( 2 ) - 6 ) << endl;
    cout << "0 - 5 = " << ( BigInt( 0 ) - 5 ) << endl;
    cout << "0 - 5 = " << ( BigInt( 0 ) - BigInt( 5 ) ) << endl;
    cout << "0 - -5 = " << ( BigInt( 0 ) - -5 ) << endl;
    cout << "0 - -5 = " << ( BigInt( 0 ) - BigInt( -5 ) ) << endl;
    cout << "10000 - 10000 = " << ( BigInt( 10000 ) - 10000 ) << endl;
    cout << "10000 - 10110 = " << ( BigInt( 10000 ) - 10110 ) << endl;
    cout << "4567 - 4568 = " << ( BigInt( 4567 ) - 4568 ) << endl;
    cout << "-4567 - -4568 = " << ( BigInt( -4567 ) - BigInt( -4568 ) ) << endl;
    cout << "999 - 9999 = " << ( BigInt( 999 ) - 9999 ) << endl;
    cout << "2000000000 + 2000000000 + 2000123456 = " << ( BigInt( 2000000000 ) + 2000000000 + BigInt( 2000123456 ) ) << endl;
    cout << "-34567 + 34568 = " << ( BigInt( -34567 ) + BigInt( 34568 ) ) << endl;
    cout << "10 - 1 = " << ( BigInt( 10 ) - 1 ) << endl;
    cout << "1 - 10 = " << ( BigInt( 1 ) - 10 ) << endl;
    cout << "Fib( 613 ) + Fib( 614 ) = " << (
        BigInt( "57535841731394367586444934959935162731893485882113791734636043664022186311322175066312007025864665068095897804714985049873571833" )
        +
        BigInt( "93094947492730684688120544687306111880728698574224279139760379700550384193434187688727692133714165658764281830930007773906603177" )
        ) << endl;
    cout << endl;
    cout << "Multiplication/division:" << endl;
    cout << "128 * 512 = " << ( BigInt( 128 ) * 512 ) << endl;
    cout << "0 * 12345 = " << ( BigInt( 0 ) * 12345 ) << endl;
    cout << "-123 * 0 = " << ( BigInt( -123 ) * 0 ) << endl;
    cout << "-12345 * 1000001 = " << ( BigInt( -12345 ) * BigInt( 1000001 ) ) << endl;
    cout << "-1 * -1 = " << ( BigInt( -1 ) * BigInt( -1 ) ) << endl;
    cout << "1024 / 2 = " << ( BigInt( 1024 ) / 2 ) << endl;
    cout << "-525474 / -789 = " << ( BigInt( -525474 ) / -789 ) << endl;
    cout << "-81 / 27 = " << ( BigInt( -81 ) / 27 ) << endl;
    cout << "0 / -888 = " << ( BigInt( 0 ) / -888 ) << endl;
    cout << "1024 / 2 = " << ( BigInt( 1024 ) / BigInt( 2 ) ) << endl;
    cout << "-525474 / -789 = " << ( BigInt( -525474 ) / BigInt( -789 ) ) << endl;
    cout << "-81 / 27 = " << ( BigInt( -81 ) / BigInt( 27 ) ) << endl;
    cout << "0 / -888 = " << ( BigInt( 0 ) / BigInt( -888 ) ) << endl;
    BigInt q = 1023;
    int rem = q.divide( 2 );
    cout << "1023 / 2 = " << q << " + " << rem << "/2" << endl;
    q = 1219255159;
    rem = q.divide( 98765 );
    cout << "1219255159 / 98765 = " << q << " + " << rem << "/98765" << endl;
    q = 121;
    rem = q.divide( 11 );
    cout << "121 / 11 = " << q << " + " << rem << "/11" << endl;
    q = 1023;
    BigInt rem2 = q.divide( BigInt( 2 ) );
    cout << "1023 / 2 = " << q << " + " << rem2 << "/2" << endl;
    q = 1219255159;
    rem2 = q.divide( BigInt( 98765 ) );
    cout << "1219255159 / 98765 = " << q << " + " << rem2 << "/98765" << endl;
    q = 121;
    rem2 = q.divide( BigInt( 11 ) );
    cout << "121 / 11 = " << q << " + " << rem2 << "/11" << endl;
    q = 9999;
    rem2 = q.divide( BigInt( 9 ) );
    cout << "9999 / 9 = " << q << " + " << rem2 << "/9" << endl;
    cout << "1024 * 15.37 = " << BigInt( 1024 ) * 15.37l << endl;
    cout << "100 * 0.5 = " << BigInt( 100 ) * 0.5l << endl;
    cout << "123456789 * 0.123456789 = " << BigInt( 123456789 ) * 0.123456789l << endl;
    cout << "4286 * -0.5 = " << BigInt( 4286 ) * -0.5l << endl;
    cout << "29384723 * 1.0 = " << BigInt( 29384723 ) * 1.0l << endl;
    cout << "29384723 * -1.0 = " << BigInt( 29384723 ) * -1.0l << endl;
    cout << "3874928345 * 0.0 = " << BigInt( "3874928345" ) * 0.0l << endl;
    BigInt n = 1000;
    cout << "n = 1000: n*n*(8+n*(12+n*(3+n*n))) = " << n*n*(8+n*(12+n*(3+n*n))) << endl;
    
    cout << endl;
    cout << "Concatenation:" << endl;
    cout << "123,456 = " << ( BigInt( 123 ), 456 ) << endl;
    cout << "9999,55 = " << ( BigInt( 9999 ), BigInt( 55 ) ) << endl;
    cout << "0,1 = " << ( BigInt( 0 ), BigInt( 1 ) ) << endl;
    cout << "0,0 = " << ( BigInt( 0 ), 0 ) << endl;
    cout << "0,0 = " << ( BigInt( 0 ), BigInt( 0 ) ) << endl;
    cout << endl;
    cout << "Reflection:" << endl;
    BigInt x = 11;
    cout << "11 + 11 = " << ( x + x ) << endl;
    cout << "11 * 11 = " << ( x * x ) << endl;
    x += x;
    cout << "11 + 11 = " << x << endl;
    x *= x;
    cout << "22 * 22 = " << x << endl;
    cout << endl;
    cout << "Bitwise operations:" << endl;
    cout << "1 << 10 = " << ( 1 << 10 ) << " = " << ( BigInt( 1 ) << 10 ) << endl;
    cout << "-7 << 2 = " << ( -7 << 2 ) << " = " << ( BigInt( -7 ) << 2 ) << endl;
    cout << "3 << 8 = " << ( 3 << 8 ) << " = " << ( BigInt( 3 ) << 8 ) << endl;
    cout << "3 << 9 = " << ( 3 << 9 ) << " = " << ( BigInt( 3 ) << 9 ) << endl;
    cout << "1024 >> 9 = " << ( 1024 >> 9 ) << " = " << ( BigInt( 1024 ) >> 9 ) << endl;
    cout << "-1 >> 4 = " << (-1 >> 4) << " = " << ( BigInt( -1 ) >> 4 ) << endl;
    cout << endl;
    cout << "Input:" << endl;
    istringstream in( "1234567890" );
    in >> x;
    cout << "1234567890 = " << x << endl;
    istringstream in2( " \t\n\r01234 -00009876\t" );
    in2 >> x >> rem2;
    cout << "1234 = " << x << endl;
    cout << "-9876 = " << rem2 << endl;
    cout << endl;
    cout << "Exhaustion:" << endl;
    BigInt *table = new BigInt[10240];
    table[0] = 0; table[1] = 1;
    for( int i = 2; i < 10240; i++ )
        table[i] = table[i - 1] + table[i - 2];
    cout << "Fibonacci( 615 )  = " << table[615] << endl;
    cout << "Fibonacci( 10000 )  = " << table[10000] << endl;
    delete [] table;
    cout << endl;
    cout << "Logarithms" << endl;
    cout << "log2( 1024 ) = " << log2( BigInt( 1024 ) ) << endl;
    cout << "log2( 6 ) = " << log2( BigInt( 6 ) ) << endl;
    cout << "log( 0 ) = " << log( BigInt( 0 ) ) << endl;
    cout << "log10( 1000000 ) = " << log10( BigInt( 10000000 ) ) << endl;
    cout << "log( 1234567 ) = " << log( BigInt( 1234567 ) ) << endl;
    return 0;
}