// ============================================================ // // lnv3.h // // Copyright 2002, Dennis Meilicke and Rene Peralta // // ============================================================ // // Description: // // ln class declaration. // // ============================================================ #ifndef __ln3_lnv3__ #define __ln3_lnv3__ #include #include class ln : public refCount< Base > { public: // // Constructors: // // Copy constructors are implemented in // the parent class (refCount). // ln( ) : refCount< Base >( ) { } ln( long a ) : refCount< Base >( ) { Assign( this->GetData( ), a ); } ln( unsigned long a ) : refCount< Base >( ) { Assign( this->GetData( ), a ); } ln( char *a ) : refCount< Base >( ) { Assign( this->GetData( ), a ); } ln( int a ) : refCount< Base >( ) { Assign( this->GetData( ), (long)a ); } ln( unsigned int a ) : refCount< Base >( ) { Assign( this->GetData( ), (unsigned long)a ); } // ln( __int64 ); // ln( unsigned __int64 ); // // Assignment // // operator= is in the parent class. // // Here is a riddle: operator= is not inherited. I do not include // an operator=( ln ) here. Yet it works, and reference counts // correctly. How is this happening? // ln& operator=( char *x ) { Assign( this->GetData( ), x ); return *this; } ln& operator=( long x ) { Assign( this->GetData( ), x ); return *this; } ln& operator=( unsigned long x ) { Assign( this->GetData( ), x ); return *this; } ln& operator=( int x ) { Assign( this->GetData( ), (long)x ); return *this; } ln& operator=( unsigned int x ) { Assign( this->GetData( ), (unsigned long)x ); return *this; } // ln& operator=( long64 ); // ln& operator=( unsigned long64 ); // // Relational operators and methods // compare_t Compare( const ln &A ) const { return ::Compare( this->GetData( ), A.GetData( ) ); } compare_t CompareAbs( const ln &A ) const { return AbsCompare( this->GetData( ), A.GetData( ) ); } bool operator==( const ln &A ) const { return ( ::Compare( this->GetData( ), A.GetData( ) ) == equalTo ); } bool operator==( long a ) const { return ( ::Compare( this->GetData( ), a ) == equalTo ); } bool operator==( unsigned long a ) const { return ( ::Compare( this->GetData( ), a ) == equalTo ); } bool operator!=( const ln &A ) const { return ( ::Compare( this->GetData( ), A.GetData( ) ) != equalTo ); } bool operator!=( long a ) const { return ( ::Compare( this->GetData( ), a ) != equalTo ); } bool operator!=( unsigned long a ) const { return ( ::Compare( this->GetData( ), a ) != equalTo ); } bool operator> ( const ln &A ) const { return ( ::Compare( this->GetData( ), A.GetData( ) ) == greaterThan ); } bool operator> ( long a ) const { return ( ::Compare( this->GetData( ), a ) == greaterThan ); } bool operator> ( unsigned long a ) const { return ( ::Compare( this->GetData( ), a ) == greaterThan ); } bool operator>=( const ln &A ) const { return ( ::Compare( this->GetData( ), A.GetData( ) ) != lessThan ); } bool operator>=( long a ) const { return ( ::Compare( this->GetData( ), a ) != lessThan ); } bool operator>=( unsigned long a ) const { return ( ::Compare( this->GetData( ), a ) != lessThan ); } bool operator< ( const ln &A ) const { return ( ::Compare( this->GetData( ), A.GetData( ) ) == lessThan ); } bool operator< ( long a ) const { return ( ::Compare( this->GetData( ), a ) == lessThan ); } bool operator< ( unsigned long a ) const { return ( ::Compare( this->GetData( ), a ) == lessThan ); } bool operator<=( const ln &A ) const { return ( ::Compare( this->GetData( ), A.GetData( ) ) != greaterThan ); } bool operator<=( long a ) const { return ( ::Compare( this->GetData( ), a ) != greaterThan ); } bool operator<=( unsigned long a ) const { return ( ::Compare( this->GetData( ), a ) != greaterThan ); } bool IsZero( void ) const { return ( this->GetData( )->size == 0 ); } bool IsNotZero( void ) const { return ( this->GetData( )->size != 0 ); } inline bool IsOdd( void ) const; inline bool IsEven( void ) const; // // Sign of the number: // ln operator-( ) const { ln R( *this ); R.IsPositive( ) ? R.GetData( )->sign = negative : R.GetData( )->sign = positive; return R; } ln operator+( ) const { ln R( *this ); R.GetData( )->sign = positive; return R; } bool IsNegative( void ) const { return ( this->GetData( )->sign == negative ); } bool IsPositive( void ) const { return ( this->GetData( )->sign == positive ); } ln Abs( void ) const { return IsNegative( ) ? -(*this) : *this; } // // Arithmetic operators // ln operator+ ( const ln& A ) const { ln Sum; add( A.GetData( ), this->GetData( ), Sum.GetData( ) ); return Sum; } ln operator+ ( long a ) const { ln S( *this ); add( S.GetData( ), a ); return S; } ln operator+ ( unsigned long a ) const { ln S( *this ); add( S.GetData( ), a ); return S; } ln& operator+=( const ln& A ) { return *this = *this + A; } ln& operator+=( long a ) { add( this->GetData( ), a ); return *this; } ln& operator+=( unsigned long a ) { add( this->GetData( ), a ); return *this; } ln& operator++( ) { return *this += 1L; } ln operator++( int ) { ln R( *this ); *this += 1L; return R; } ln operator- ( const ln&A ) const { ln Diff; Subtract( this->GetData( ), A.GetData( ), Diff.GetData( ) ); return Diff; } ln operator- ( long a ) const { ln Diff( *this ); Subtract( Diff.GetData( ), a ); return Diff; } ln operator- ( unsigned long a ) const { ln Diff( *this ); Subtract( Diff.GetData( ), a ); return Diff; } ln& operator-=( const ln &A ) { return *this = *this - A; } ln& operator-=( long a ) { Subtract( this->GetData( ), a ); return *this; } ln& operator-=( unsigned long a ) { Subtract( this->GetData( ), a ); return *this; } ln& operator--( ) { return *this -= 1L; } ln operator--( int ) { ln R( *this ); *this -= 1L; return R; } ln operator* ( const ln& A ) const { ln Prod; multiply( A.GetData( ), this->GetData( ), Prod.GetData( ) ); return Prod; } ln operator* ( long b ) const { ln A( *this ); Multiply( A.GetData( ), b ); return A; } ln operator* ( unsigned long b ) const { ln A( *this ); Multiply( A.GetData( ), b ); return A; } ln& operator*=( const ln&A ) { return *this = *this * A; } ln& operator*=( long b ) { Multiply( this->GetData( ), b ); return *this; } ln& operator*=( unsigned long b ) { Multiply( this->GetData( ), b ); return *this; } ln operator/ ( const ln &D ) const { ln Q, R; ::Divide( this->GetData( ), D.GetData( ), Q.GetData( ), R.GetData( ) ); return Q; } ln& operator/=( const ln &D ) { return *this = *this / D; } ln operator% ( const ln &M ) const { ln Q, R; ::Divide( this->GetData( ), M.GetData( ), Q.GetData( ), R.GetData( ) ); if( R.IsNotZero( ) && R.IsNegative( ) ) R += M; return R; } ln& operator%=( const ln &M ) { return *this = *this % M; } void Divide( const ln &D, ln *Q, ln *R ) const { ::Divide( this->GetData( ), D.GetData( ), Q->GetData( ), R->GetData( ) ); } void Divide( long d, ln *Q, long *r ) const { ::Divide( this->GetData( ), d, Q->GetData( ), r ); } void Divide( unsigned long d, ln *Q, unsigned long *r ) const { ::Divide( this->GetData( ), d, Q->GetData( ), r ); } // // Bit-wise methods and operators // short NumBits( void ) const { return ::NumBits( this->GetData( ) ); } short GetBit( size_t bit ) const { return ::GetBit( this->GetData( ), bit ); } void SetBit( size_t bit, short value ) { ::SetBit( this->GetData( ), bit, value ); } ln& operator&= ( const ln &X ) { And( this->GetData( ), X.GetData( ) ); return *this; } ln& operator|= ( const ln &X ) { Or( this->GetData( ), X.GetData( ) ); return *this; } ln& operator^= ( const ln &X ) { Xor( this->GetData( ), X.GetData( ) ); return *this; } ln& Not ( void ) { ::Not( this->GetData( ) ); return *this; } ln operator& ( const ln &X ) const { ln R(*this); return R &= X; } ln operator| ( const ln &X ) const { ln R(*this); return R |= X; } ln operator^ ( const ln &X ) const { ln R(*this); return R ^= X; } ln operator~ ( void ) const { ln X(*this); return X.Not( ); } ln operator>> ( size_t d ) { ln R( *this ); ShiftRightEqual( R.GetData( ), d ); return R; } ln operator<< ( size_t d ) { ln R( *this ); ShiftLeftEqual( R.GetData( ), d ); return R; } ln& operator>>=( size_t d ) { ShiftRightEqual( this->GetData( ), d ); return *this; } ln& operator<<=( size_t d ) { ShiftLeftEqual( this->GetData( ), d ); return *this; } // // Conversion methods // // Consider corresponding query functions, e.g. IsShort, IsLong, etc. // // short ToShort( void ); // unsigned short ToUnsignedShort( void ); // long ToLong( void ); // unsigned long ToLong( void ); // long64 ToLong64( void ); // unsigned long64 ToUnsignedLong64( void ); // char *ToChar( void ); // // Misc methods // ln& Random( size_t digits ); ln& RandomMod( ln mod ); // // The following should really be NTTL functions. In a perfect // world. Where I would have an infinite amount of time... // ln ln::FastExp( const ln &Exponent, const ln &Modulus ) const; short Jacobi( const ln &Modulus ) const; // // I/O // void Read( istream &stream ) { ::Read( this->GetData( ), stream ); } void Print( ostream &stream, short base=10 ) const { ::Print( this->GetData( ), stream, base ); } friend ostream& operator<<( ostream &stream, const ln &X ); friend istream& operator>>( istream &stream, ln &X ); // // 'Getters' and 'Setters'... // sign_t GetSign( void ) const { return this->GetData( )->sign; } size_t GetSize( void ) const { return this->GetData( )->size; } digit_t GetDigit( size_t index ) const { return this->GetData( )->digit[ index ]; } void SetSign( sign_t sign ) { this->GetData( )->sign = sign; } void SetSize( size_t size ) { this->GetData( )->size = size; } void SetDigit( size_t index, digit_t value ) { this->GetData( )->digit[ index ] = value; } }; inline bool ln::IsOdd( void ) const { if( this->GetData( )->size == 0 ) return false; return ( ( this->GetData( )->digit[0] & 1 ) == 1 ); } inline bool ln::IsEven( void ) const { if( this->GetData( )->size == 0 ) return false; return ( ( this->GetData( )->digit[0] & 1 ) == 0 ); } // // The following inline functions serve two purposes: // First, they provide an unambigous conversion from the // basic data types (PODs) to long. This way, the only // scalar operation needed is a long operation. // Second, they provided commutated versions of the // scalar operations. // // Some of these functions don't make any sense. // Consider: // int a; ln A; // a += A; // This only makes sense if A is small... Still, the // analogs: // short a; long A; // a += A; // exist... // // Addition: inline ln operator+ ( const ln &A, int b ) { return A + (long)b; } inline ln operator+ ( int b, const ln &A ) { return A + (long)b; } inline ln operator+ ( long b, const ln &A ) { return A + (long)b; } inline ln operator+ ( const ln &A, unsigned int b ) { return A + (unsigned long)b; } inline ln operator+ ( unsigned int b, const ln &A ) { return A + (unsigned long)b; } inline ln operator+ ( unsigned long b, const ln &A ) { return A + (unsigned long)b; } inline ln& operator+=( ln &A, int b ) { return A += (long)b; } inline ln& operator+=( ln &A, unsigned int b ) { return A += (unsigned long)b; } // // Subtraction: inline ln operator- ( const ln &A, int b ) { return A - (long)b; } inline ln operator- ( int b, const ln &A ) { return -( A - (long)b ); } inline ln operator- ( long b, const ln &A ) { return -( A - (long)b ); } inline ln operator- ( const ln &A, unsigned int b ) { return A - (unsigned long)b; } inline ln operator- ( unsigned int b, const ln &A ) { return -( A - (unsigned long)b ); } inline ln operator- ( unsigned long b, const ln &A ) { return -( A - (unsigned long)b ); } inline ln& operator-=( ln &A, int b ) { return A -= (long)b; } //inline ln& operator-=( int b, ln A ) { A -= (long)b; A.SetSign( ( A.GetSign( ) == positive ) ? positive : negative ); return A; } //inline ln& operator-=( long b, ln A ) { A -= (long)b; A.SetSign( ( A.GetSign( ) == positive ) ? positive : negative ); return A; } inline ln& operator-=( ln &A, unsigned int b ) { return A -= (unsigned long)b; } //inline ln& operator-=( unsigned int b, ln A ) { A -= (unsigned long)b; A.SetSign( ( A.GetSign( ) == positive ) ? positive : negative ); return A; } //inline ln& operator-=( unsigned long b, ln A ) { A -= (unsigned long)b; A.SetSign( ( A.GetSign( ) == positive ) ? positive : negative ); return A; } // // Multiplication: inline ln operator* ( const ln &A, int b ) { return A * (long)b; } inline ln operator* ( int b, const ln &A ) { return A * (long)b; } inline ln operator* ( long b, const ln &A ) { return A * (long)b; } inline ln operator* ( const ln &A, unsigned int b ) { return A * (unsigned long)b; } inline ln operator* ( unsigned int b, const ln &A ) { return A * (unsigned long)b; } inline ln operator* ( unsigned long b, const ln &A ) { return A * (unsigned long)b; } inline ln& operator*=( ln &A, int b ) { return A *= (long)b; } //inline ln& operator*=( int b, const ln &A ) { return A *= (long)b; } //inline ln& operator*=( long b, const ln &A ) { return A *= (long)b; } inline ln& operator*=( ln &A, unsigned int b ) { return A *= (unsigned long)b; } //inline ln& operator*=( unsigned int b, const ln &A ) { return A *= (unsigned long)b; } //inline ln& operator*=( unsigned long b, const ln &A ) { return A *= (unsigned long)b; } // // Division: // // Comparison inline bool operator==( const ln &A, int b ) { return ( A == (long)b ); } inline bool operator==( int b, const ln &A ) { return ( A == (long)b ); } inline bool operator==( long b, const ln &A ) { return ( A == b ); } inline bool operator==( const ln &A, unsigned int b ) { return ( A == (unsigned long)b ); } inline bool operator==( unsigned int b, const ln &A ) { return ( A == (unsigned long)b ); } inline bool operator==( unsigned long b, const ln &A ) { return ( A == b ); } inline bool operator!=( const ln &A, int b ) { return ( A != (long)b ); } inline bool operator!=( int b, const ln &A ) { return ( A != (long)b ); } inline bool operator!=( long b, const ln &A ) { return ( A != b ); } inline bool operator!=( const ln &A, unsigned int b ) { return ( A != (unsigned long)b ); } inline bool operator!=( unsigned int b, const ln &A ) { return ( A != (unsigned long)b ); } inline bool operator!=( unsigned long b, const ln &A ) { return ( A != b ); } inline bool operator> ( const ln &A, int b ) { return ( A > (long)b ); } inline bool operator> ( int b, const ln &A ) { return ( A < (long)b ); } inline bool operator> ( long b, const ln &A ) { return ( A < b ); } inline bool operator> ( const ln &A, unsigned int b ) { return ( A > (unsigned long)b ); } inline bool operator> ( unsigned int b, const ln &A ) { return ( A < (unsigned long)b ); } inline bool operator> ( unsigned long b, const ln &A ) { return ( A < b ); } inline bool operator>=( const ln &A, int b ) { return ( A >= (long)b ); } inline bool operator>=( int b, const ln &A ) { return ( A <= (long)b ); } inline bool operator>=( long b, const ln &A ) { return ( A <= b ); } inline bool operator>=( const ln &A, unsigned int b ) { return ( A >= (unsigned long)b ); } inline bool operator>=( unsigned int b, const ln &A ) { return ( A <= (unsigned long)b ); } inline bool operator>=( unsigned long b, const ln &A ) { return ( A <= b ); } inline bool operator< ( const ln &A, int b ) { return ( A < (long)b ); } inline bool operator< ( int b, const ln &A ) { return ( A > (long)b ); } inline bool operator< ( long b, const ln &A ) { return ( A > b ); } inline bool operator< ( const ln &A, unsigned int b ) { return ( A < (unsigned long)b ); } inline bool operator< ( unsigned int b, const ln &A ) { return ( A > (unsigned long)b ); } inline bool operator< ( unsigned long b, const ln &A ) { return ( A > b ); } inline bool operator<=( const ln &A, int b ) { return ( A <= (long)b ); } inline bool operator<=( int b, const ln &A ) { return ( A >= (long)b ); } inline bool operator<=( long b, const ln &A ) { return ( A >= b ); } inline bool operator<=( const ln &A, unsigned int b ) { return ( A <= (unsigned long)b ); } inline bool operator<=( unsigned int b, const ln &A ) { return ( A >= (unsigned long)b ); } inline bool operator<=( unsigned long b, const ln &A ) { return ( A >= b ); } // I/O inline istream &operator>>( istream& stream, ln& X ) { X.Read( stream ); return stream; } inline ostream &operator<<( ostream &stream, const ln &X ) { X.Print( stream ); return stream; } #include #include #endif