/*============================================================================== | | File Name: | | ppBigInt.h | | Description: | | Header file for multiple precision math routines. | | Legal: | | Primpoly Version 7.7 - A Program for Computing Primitive Polynomials. | Copyright (C) 1999-2008 by Sean Erik O'Connor. All Rights Reserved. | | This program is free software; you can redistribute it and/or | modify it under the terms of the GNU General Public License | as published by the Free Software Foundation; version 2 | of the License. | | This program is distributed in the hope that it will be useful, | but WITHOUT ANY WARRANTY; without even the implied warranty of | MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the | GNU General Public License for more details. | | You should have received a copy of the GNU General Public License | along with this program; if not, write to the Free Software | Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, | USA. | | The author's address is artifex@seanerikoconnor.freeservers.com | ==============================================================================*/ // Wrap this header file to prevent duplication if it is included // accidentally more than once. #ifndef __PP_BIGINT_H__ #define __PP_BIGINT_H__ // Shorthand for convenience to avoid spelling out "unsigned int" everywhere. typedef unsigned int uint ; /*============================================================================= | | NAME | | BigIntMathError General math error, including internal memory errors. | BigIntUnderflow Underflow. | BigIntOverflow Overflow. | BigIntZeroDivide Zero divide. | BigIntRangeError Input range error. | BigIntDomainError Input domain error, i.e. log(-1). | | DESCRIPTION | | Exception classes for the BigInt class | derived from the STL exception class runtime_error. | | BUGS | +============================================================================*/ class BigIntMathError : public runtime_error { public: // Throw with an error message. BigIntMathError( const string & description ) : runtime_error( description ) { } ; // Default throw with no error message. BigIntMathError() : runtime_error( "BigInt math error: " ) { } ; } ; // end class BigIntMathError class BigIntRangeError : public BigIntMathError { public: // Throw with an error message. BigIntRangeError( const string & description ) : BigIntMathError( description ) { } ; // Default throw with no error message. BigIntRangeError() : BigIntMathError( "BigInt range error: " ) { } ; } ; // end class BigIntRangeError class BigIntDomainError : public BigIntMathError { public: // Throw with an error message. BigIntDomainError( const string & description ) : BigIntMathError( description ) { } ; // Default throw with no error message. BigIntDomainError() : BigIntMathError( "BigInt domain error: " ) { } ; } ; // end class BigIntDomainError class BigIntOverflow : public BigIntMathError { public: BigIntOverflow( const string & description ) : BigIntMathError( description ) { } ; BigIntOverflow() : BigIntMathError( "BigInt overflow. " ) { } } ; class BigIntUnderflow : public BigIntMathError { public: BigIntUnderflow( const string & description ) : BigIntMathError( description ) { } ; BigIntUnderflow() : BigIntMathError( "BigInt underflow. " ) { } } ; class BigIntZeroDivide : public BigIntMathError { public: BigIntZeroDivide( const string & description ) : BigIntMathError( description ) { } ; BigIntZeroDivide() : BigIntMathError( "BigInt zero divide. " ) { } } ; /*============================================================================= | | NAME | | BigInt | | DESCRIPTION | | Class for multiprecision integer arithmetic. | | We throw one of the following exceptions, | | BigIntMathError General math error. | BigIntRangeError Range error on input. | BigIntUnderflow Underflow. | BigIntOverflow Overflow. | BigIntZeroDivide Zero divide. | bad_exception Thrown if we violate a function's | exception specification. | | NOTES | | The member functions and friends are documented in detail ppBigInt.cpp | | BUGS | +============================================================================*/ class BigInt { public: //-----------------< Basic mathematical operations >------------------ // *** Constructors. // Default constructor. // e.g. BigInt u ; BigInt() throw( bad_exception ) ; // Destructor. ~BigInt() ; // Constructor from unsigned integer. // e.g. unsigned int u ; BigInt w( u ) ; BigInt( const uint d ) throw( BigIntMathError, bad_exception ) ; // Constructor from decimal number string. // e.g. string s = "314159" ; BigInt w( s ) ; BigInt( const string & s ) throw( BigIntRangeError, bad_exception ) ; // Copy constructor. // e.g. BigInt u ; BigInt v( u ) ; BigInt( const BigInt & u ) throw( bad_exception ) ; // Assignment. // e.g. BigInt u( "123" ) ; BigInt v ; v = u ; BigInt & operator=( const BigInt & n ) throw( BigIntMathError, bad_exception ) ; // Conversion to int. // e.g. BigInt( w ) = "123" ; unsigned int u = static_cast( w ) ; operator uint() const throw( BigIntOverflow, bad_exception ) ; // *** Input and output operators. // e.g. ostringstream os ; os << u ; friend ostream & operator<<( ostream & out, const BigInt & u ) throw( BigIntRangeError, bad_exception ) ; // e.g. istringstream is ; is >> u ; friend istream & operator>>( istream & in, BigInt & u ) throw( BigIntRangeError, bad_exception ) ; // u + v and other additions. friend const BigInt operator+( const BigInt & u, const BigInt & v ) throw( BigIntMathError, bad_exception ) ; friend const BigInt operator+( const BigInt & u, const uint d ) throw ( BigIntMathError, bad_exception ) ; BigInt & operator+=( const BigInt & u ) throw ( BigIntMathError, bad_exception ) ; BigInt & operator+=( const uint d ) throw ( BigIntMathError, bad_exception ) ; // ++u and other increments. BigInt & operator++() throw ( BigIntMathError, bad_exception ) ; const BigInt operator++( int ) throw ( BigIntMathError, bad_exception ) ; // u - v and other subtractions. friend const BigInt operator-( const BigInt & u, const BigInt & v ) throw( BigIntMathError, bad_exception ) ; friend const BigInt operator-( const BigInt & u, const uint d ) throw( BigIntMathError, bad_exception ) ; BigInt & operator-=( const BigInt & u ) throw( BigIntUnderflow, bad_exception ) ; BigInt & operator-=( const uint d ) throw( BigIntUnderflow, bad_exception ) ; // --u and other decrements BigInt & operator--() throw( BigIntUnderflow, bad_exception ) ; BigInt operator--( int ) throw( BigIntUnderflow, bad_exception ) ; // u * v, and other multiplies. friend const BigInt operator*( const BigInt & u, const BigInt & v ) throw( BigIntMathError, BigIntOverflow, bad_exception ) ; friend const BigInt operator*( const BigInt & u, const uint d ) throw( BigIntMathError, BigIntOverflow, bad_exception ) ; BigInt & operator*=( const BigInt & u ) throw( BigIntMathError, BigIntOverflow, bad_exception ) ; BigInt & operator*=( uint d ) throw( BigIntMathError, BigIntOverflow, bad_exception ) ; // | u / v |, and other integer divides. // -- -- friend const BigInt operator/( const BigInt & u, const BigInt & v ) throw( BigIntZeroDivide, BigIntRangeError, BigIntMathError, bad_exception ) ; friend const BigInt operator/( const BigInt & u, const uint d ) throw( BigIntZeroDivide, BigIntRangeError, BigIntMathError, bad_exception ) ; BigInt & operator/=( const BigInt & u ) throw( BigIntZeroDivide, BigIntRangeError, BigIntMathError, bad_exception ) ; BigInt & operator/=( uint d ) throw( BigIntZeroDivide, BigIntRangeError, BigIntMathError, bad_exception ) ; // u % v, and other integer moduli. friend BigInt operator%( const BigInt & u, const BigInt & v ) throw( BigIntZeroDivide, BigIntRangeError, BigIntMathError, bad_exception ) ; friend uint operator%( const BigInt & u, const uint d ) throw( BigIntZeroDivide, BigIntRangeError, BigIntMathError, bad_exception ) ; // Power, p ^ n friend BigInt power( uint p, uint n ) throw( BigIntMathError, bad_exception ) ; // -- -- // | lg() | int ceilLg() throw( BigIntMathError, bad_exception ) ; // Comparisions including // ==, == d, !=, != d, >, > d, // <, < d, >=, >= d, <=, <= d, friend bool operator==( const BigInt & u, const BigInt & v ) ; friend bool operator==( const BigInt & u, const uint d ) ; friend bool operator!=( const BigInt & u, const BigInt & v ) ; friend bool operator!=( const BigInt & u, const uint d ) ; friend bool operator> ( const BigInt & u, const BigInt & v ) ; friend bool operator> ( const BigInt & u, const uint d ) throw ( BigIntOverflow, bad_exception ) ; friend bool operator< ( const BigInt & u, const BigInt & v ) ; friend bool operator< ( const BigInt & u, const uint d ) ; friend bool operator>=( const BigInt & u, const BigInt & v ) ; friend bool operator>=( const BigInt & u, const uint d ) ; friend bool operator<=( const BigInt & u, const BigInt & v ) ; friend bool operator<=( const BigInt & u, const uint d ) ; // Bit masking and setting: &, <<, test bit, highest bit friend BigInt operator& ( const BigInt & u, const BigInt & v ) throw( BigIntMathError, bad_exception ) ; friend BigInt operator<<( const BigInt & u, uint n ) throw( BigIntRangeError, bad_exception ) ; const bool testBit( const uint bitNum ) const throw( BigIntRangeError, BigIntMathError, bad_exception ) ; friend const bool testBit( const uint n, const uint bitNum ) ; //-----------------< Helper functions >------------------------------- // Conversion to decimal number string. // e.g. BigInt u( "123" ) ; string s = u.to_string() ; string to_string() const throw( BigIntRangeError, bad_exception ) ; // Helper functions for division and mod. friend void divMod( const BigInt & u, const BigInt & v, BigInt & q, BigInt & r ) throw( BigIntZeroDivide, BigIntRangeError, BigIntMathError, bad_exception ) ; friend void divMod( const BigInt & u, const uint d, BigInt & q, uint & r ) throw( BigIntZeroDivide, BigIntRangeError, BigIntMathError, bad_exception ) ; // Highest bit number in a BigInt, 0 is smallest bit. uint maxBitNumber() const ; //-----------------< Unit Test Functions >---------------------------- friend const uint getDigit( const BigInt & u, const uint n ) throw( BigIntRangeError, bad_exception ) ; friend const uint getNumDigits( const BigInt & u ) throw( bad_exception ) ; friend const uint getBase( const BigInt & u ) throw( bad_exception ) ; friend void setBase( const BigInt & u, const uint base ) throw( bad_exception ) ; friend void printNumber( const BigInt & u ) throw( bad_exception ) ; // Class variables shared among all classes. // We use static functions instead of static variables to work // around the C++ static member initialization order problem. private: // Base of the number system (a power of 2) and // corresponding number of bits per digit. static uint & base_() throw( BigIntRangeError, bad_exception ) ; // For testing only. static uint * pbase ; static uint & numBitsPerDigit_() throw( BigIntMathError, bad_exception ) ; // Private data for member functions only. private: // Numbers are n-place quantities with base b digits, // 2 // where b is guaranteed to fit into a digit and // b is a power of 2. // // (u . . . u ) // n-1 0 // // For programming ease, digits are stored in a vector of // length n with the least significant digit at digit[ 0 ], // // +----+----+----+------+------+ // | u | u | u | | u | // | 0 | 1 | 2 | ... | n-1 | // +----+----+----+------+------+ // vector< uint > digit_ ; } ; #endif // __PP_BIGINT_H__ --- End of wrapper for header file.