//
//
// Integer.h: Unsigned integer with arbitrary precision.
//
// Proper Numbers Library
//
// © Copyright 2011 - 2011 by Miroslav Bonchev Bonchev. All rights reserved.
//
//
//******************************************************************************************************
// Open Source License – The MIT License
//
//
// {your product} uses the Proper Numbers Library by Miroslav Bonchev Bonchev. All Rights Reserved.
// {your product} uses the Object Contextualization Model by Miroslav Bonchev Bonchev. All Rights Reserved.
//
// Permission is hereby granted, free of charge, to any person obtaining a copy of this software and
// associated documentation files (the "Software"), to deal in the Software without restriction,
// including without limitation the rights to use, copy, modify, merge, publish, distribute,
// sublicense, and/or sell copies of the Software, and to permit persons to whom the Software is
// furnished to do so, subject to the following conditions:
//
// The above copyright notice and this permission notice shall be included in all copies or
// substantial portions of the Software.
//
// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT
// NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
// NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM,
// DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
// OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
//__________________________________________________________________________________________________
// This software is OSI Certified Open Source Software.
// OSI Certified is a certification mark of the Open Source Initiative.
#pragma once
#include "stdafx.h"
#include "Common.h"
#include "MAtom.h"
#include "StringEx.h"
#include "Pair.h"
#include "Specialize.h"
#pragma warning( push )
#pragma warning( disable : 4290 ) // warning C4290: C++ exception specification ignored except to indicate a function is not __declspec(nothrow)
template< class dataType, bool bExceptions = true >
class NumberException
{
public:
enum Error
{
eIntegerDivisionByZero,
eNonCompatibleOperation
};
private:
Error eError;
private:
NumberException( const Error excError ) throw() : eError( excError ) {}
public:
NumberException( const NumberException& objNumberException ) throw() : eError( objNumberException.eError ) {}
~NumberException() {}
NumberException& operator=( const NumberException& objNumberException ) throw() { eError = objNumberException.eError; }
public:
__forceinline static void TestDivisionByZero( typename const dataType muiDivisor ) throw( NumberException< dataType, bExceptions > )
{
if( 0 == muiDivisor )
{
MASSERT( FALSE );
bExceptions ? throw( NumberException< dataType, true >( NumberException::eIntegerDivisionByZero ) ) : 0;
}
}
__forceinline static void TestCompatibility( typename const dataType objLeft, typename const dataType objRight ) throw( NumberException< dataType, bExceptions > )
{
if( !objLeft.IsCompatible( objRight ) )
{
MASSERT( FALSE );
bExceptions ? throw( NumberException< dataType, true >( NumberException::eNonCompatibleOperation ) ) : 0;
}
}
};
#pragma warning( pop )
// The Integer class represents unsigned integer with arbitrary precision.
//
// Objects from this type expand arbitrarily large up to available memory and are able to accommodate
// arbitrarily large numbers (up to the available memory).
//
// Some points of interest:
//
// Each number is composited from one or more 64 bit words. Arithmetic operations are implemented using
// set of appropriate fast algorithms. When a number exceed the current size the operation is carried
// out adding more space to the number thus overflow and truncation are inapplicable and hence it is
// not possible to lose information for these reasons (provided there is enough memory in the system).
// Shift to right and subtraction decrease the size of the number (object). Empty number is not allowed.
// Zero is represented with one 64 bit word equal to zero. The objects are maintained normalized which
// for this class means that there are no leading zeroed 64 bit words - except one zero word for the 0.
// When subtracting larger number from smaller the result wraps and has the size of the larger number.
// The decrement operator has unusual behavior - it does NOT decrement below zero to avoid ambiguity.
//
// Semantically the Integer class is a specialization of a linked list of type MList< unsigned __int64 >.
// When a number is represented with an object of this type the underlying linked list is accelerated thus
// the words of the number are accessed as an array achieving performance as if the numbers were indeed
// represented by an array. The integer class inherits as protected and thus the methods of the underling
// list are not visible (accessible) from an integer instance.
//
// Currently object from the Integer type throw NumberException only when dividing by zero. This behaviour
// may change in future removing all exceptions altogether although this is not likely, or new operator
// with alternative behaviour will be provided. The division operator returns object specialized Quotient
// and Reminder thus helping to prevent errors.
//
// The logical operators are NOT overloaded purposefully. The reason is that Integer numbers are NOT Boolean
// entities and therefore they should not implicitly represent logical values. Should one want to use them
// as Boolean variables they can use the IsZero() method and the comparison operators appropriately.
//
// Objects from the Integer class are able to print themselves using the Print() method.
class Integer : protected MList< unsigned __int64 >
{
template< class classType, class classSpecializer > friend class specialize;
private:
// Constructor for internal use creating skeleton of a number.
Integer( const Integer& integer, const DWORD dwSegmentCount )
{
if( 0 != dwSegmentCount )
{
*this = integer;
for( DWORD dwIndex = GetCount(); dwIndex < dwSegmentCount; dwIndex++ )
{
AddTail( new unsigned __int64( 0 ) );
}
}
}
// Removes any leading zeroes, but leave one last if the number is zero. "Empty" number is illegal.
Integer Normalize()
{
while( (0 == *pTail->GetObject()) && (1 < GetCount()) )
{
delete RemoveTail();
}
if( IsEmpty() )
{
AddHead( new unsigned __int64( 0 ) );
}
return( *this );
}
public:
// Default constructor - initializes the object with zero.
Integer() : MList< unsigned __int64 >( (unsigned __int64)0 )
{
}
// Initializes the object with native (unsigned) integer.
Integer( const unsigned __int64 uiInteger ) : MList< unsigned __int64 >( (unsigned __int64)uiInteger )
{
}
// Copy constructor.
Integer( const Integer& integer ) : MList< unsigned __int64 >( integer )
{
}
// Inherits virtual destructor.
~Integer()
{
}
// Standard operator equal.
inline Integer& operator=( const Integer& integer )
{
return( dynamic_cast< MList< unsigned __int64 >* >( this )->operator=( *dynamic_cast< const MList< unsigned __int64 >* >( &integer ) ), *this );
}
// Test if the number is zero.
inline bool IsZero() const
{
return( (1 == GetCount()) && (0 == *(*this)[0]) );
}
// Test if the number is even.
inline bool IsEven() const
{
return( 0 == (1 & *(*this)[0]) );
}
// Test if the number is odd.
inline bool IsOdd() const
{
return( 1 == (1 & *(*this)[0]) );
}
// Standard operator +=
inline Integer operator +=( const Integer& iSummand )
{
return( *this = ::operator +( *this, iSummand ) );
}
// Standard operator -=
inline Integer operator -=( const Integer& iSubtrahend )
{
return( *this = ::operator -( *this, iSubtrahend ) );
}
// Standard operator *=
inline Integer operator *=( const Integer& iFactor )
{
return( *this = *this * iFactor );
}
// Standard operator /=
inline Integer operator /=( const Integer& iDivisor )
{
return( *this = (*this / iDivisor).GetLabelRef() );
}
// Standard operator %=
inline Integer operator %=( const Integer& iDivisor )
{
return( *this = (*this / iDivisor).GetValueRef() );
}
// Standard operator &=
inline Integer operator &=( const Integer& iGate )
{
return( *this = *this & iGate );
}
// Standard operator |=
inline Integer operator |=( const Integer& iGate )
{
return( *this = *this | iGate );
}
// Standard operator ^=
inline Integer operator ^=( const Integer& iGate )
{
return( *this = *this ^ iGate );
}
// Standard operator <<=
inline Integer operator <<=( const Integer& iShiftCount )
{
return( *this = *this << iShiftCount );
}
// Standard operator >>=
inline Integer operator >>=( const Integer& iShiftCount )
{
return( *this = *this >> iShiftCount );
}
// Unary plus (returns the operand itself).
inline Integer operator+() const
{
return( *this );
}
// Unary operator negation (two's complements – inverts the bits and adds one).
inline Integer operator-() const
{
if( IsZero() )
{
return( *this );
}
Integer i( *this );
for( DWORD dwIndex = 0; dwIndex < i.GetCount(); dwIndex++ )
{
*i[dwIndex] = ~*i[dwIndex];
}
i.IncrementFromSegment( 0 );
return( i );
}
// Operator bitwise NOT (inverts all bits).
inline Integer operator ~() const
{
Integer i( *this );
for( DWORD dwIndex = 0; dwIndex < i.GetCount(); dwIndex++ )
{
*i[dwIndex] = ~*i[dwIndex];
}
return( i );
}
// Returns an integer power of this integer.
inline Integer ToPower( const Integer& uiPower ) const
{
Integer uiThis( 1 );
for( Integer uiCount = 0; uiCount < uiPower; uiCount += 1 )
{
uiThis = uiThis * *this;
}
return( uiThis );
}
// Add one to the number - this instance.
inline Integer& Increment()
{
IncrementFromSegment( 0 );
return( *this );
}
// Prefix increment operator.
inline Integer& operator++()
{
Increment();
return( *this );
}
// Postfix increment operator.
inline Integer operator++( int )
{
Integer uiThis( *this );
Increment();
return( uiThis );
}
// Prefix decrement operator. Note it does NOT decrement below zero - since the number is
// of an arbitrary span it is ambiguous how large should the number be when decrementing
// it from zero. However since it is an unsigned integer the number will not be decremented
// below the zero, thus any decrement call after the number is already zero will be ignored.
inline Integer& operator--()
{
if( !IsZero() )
{
*this = *this - 1;
}
return( *this );
}
// Prefix decrement operator. Note it does NOT decrement below zero - since the number is
// of an arbitrary span it is ambiguous how large should the number be when decrementing
// it from zero. However since it is an unsigned integer the number will not be decremented
// below the zero, thus any decrement call after the number is already zero will be ignored.
inline Integer operator--( int )
{
Integer uiThis( *this );
if( !IsZero() )
{
*this = *this - 1;
}
return( uiThis );
}
// Return ONE based index of the most significant 1, therefore returning 0 implies
// that the number is zero. Divide this method’s return value mod 64 plus one to
// get the number of 64 bit words used in the representation of the number.
inline unsigned __int64 GetMostSignificantOneIndex() const
{
const unsigned __int64 uiMSB( *GetTail() );
for( unsigned __int64 uiWindow = ((unsigned __int64)1) << 63, uiIndex = 64; 0 != uiWindow; uiWindow >>= 1, uiIndex-- )
{
if( 0 != (uiMSB & uiWindow) )
{
return( (GetCount() - 1) * 8 * sizeof( unsigned __int64 ) + uiIndex );
}
}
return( 0 );
}
// Return a string object containing the decimal representation of the number.
MStringEx< TCHAR > Print() const
{
MList< BYTE > listResult( new BYTE( 0 ), NULL );
MList< BYTE > list2Power( new BYTE( 1 ), NULL );
// One based index of the most significant one - zero implies tho ones at all.
unsigned __int64 uiMSBitIndex( GetMostSignificantOneIndex() );
if( 0 < uiMSBitIndex )
{
unsigned __int64 uiCurrentIndex( 0 );
// Head is LSB, Tail is MSB
for( DWORD dwSegment = 0; dwSegment < GetCount(); dwSegment++ )
{
for( unsigned __int64 uiWindow = 1; 0 != uiWindow; uiCurrentIndex++, uiWindow <<= 1 )
{
if( 0 != (*(*this)[dwSegment] & uiWindow) )
{
AddDecimal( listResult, list2Power );
}
if( uiCurrentIndex >= uiMSBitIndex )
{
break;
}
MultiplyDecimalBy2( list2Power );
}
}
}
MStringEx< TCHAR > strNumber;
for( DWORD dwIndex = 0; dwIndex < listResult.GetCount(); dwIndex++ )
{
strNumber = MStringEx< TCHAR >( MStringEx< TCHAR >::FF, TEXT("%d"), *listResult[dwIndex] ) + strNumber;
}
return( strNumber );
}
// Return the quotient part from the division of this number by another integer.
// This method uses the division operator. It is more efficient to use the division
// operator directly if you also need the reminder part from tis division.
inline Integer DivideBy_ReturnQuotient( const Integer& iDivisor ) const
{
return( operator /( *this, iDivisor ).GetLabelRef() );
}
// Return the reminder part from the division of this number by another integer.
// This method uses the division operator. It is more efficient to use the division
// operator directly if you also need the quotient part from tis division.
inline Integer DivideBy_ReturnReminder( const Integer& iDivisor ) const
{
return( operator /( *this, iDivisor ).GetValueRef() );
}
// Shift to left.
inline Integer& Shift2Left( const unsigned __int64 uiTimes )
{
if( !IsZero() && (0 != uiTimes) )
{
const unsigned __int64 uiNewSegments( uiTimes / 64 );
// The Head is Least Significant Part, and the Tail is Most Significant Part so compute Headt-to-Tail.
// Add one empty segment at the head, i.e. least segnificant part, for every 64 bit shift to the left.
for( Integer iSegment = 0; iSegment < uiNewSegments; iSegment++ )
{
AddHead( new unsigned __int64( 0 ) );
}
const BYTE b1BitIncShift( uiTimes % 64 );
if( 0 != b1BitIncShift )
{
// Division by 64 cannot have remiander bigger than 63.
MASSERT( b1BitIncShift < 64 );
// Head - LSB, Tail - MSB.
unsigned __int64 uiCarry( 0 );
for( DWORD dwIndex = 0; dwIndex < GetCount(); dwIndex++ )
{
const unsigned __int64 bNewCarry( *(*this)[dwIndex] >> (64 - b1BitIncShift) );
*(*this)[dwIndex] <<= b1BitIncShift;
*(*this)[dwIndex] |= uiCarry;
uiCarry = bNewCarry;
}
if( 0 != uiCarry )
{
AddTail( new unsigned __int64( uiCarry ) );
}
}
}
return( *this );
}
// Shift to right.
inline Integer& Shift2Right( const unsigned __int64 uiTimes )
{
if( !IsZero() && (0 != uiTimes) )
{
const unsigned __int64 uiDelSegments( uiTimes / 64 );
// The Head is Least Significant Part, and the Tail is Most Significant Part so compute Headt-to-Tail.
// Remove one segment from the head, i.e. least segnificant part, for every 64 bit shift to the right.
for( unsigned __int64 uiSegment = 0; (uiSegment < uiDelSegments) && !IsEmpty(); uiSegment++ )
{
delete RemoveHead();
}
if( !IsEmpty() )
{
const BYTE b1BitIncShift( uiTimes % 64 );
if( 0 != b1BitIncShift )
{
// Division by 64 cannot have remiander bigger than 63.
MASSERT( b1BitIncShift < 64 );
// Head - LSB, Tail - MSB.
unsigned __int64 uiCarry( 0 );
for( DWORD dwIndex = GetCount() - 1; (DWORD)-1 != dwIndex; dwIndex-- )
{
const unsigned __int64 bNewCarry( *(*this)[dwIndex] << (64 - b1BitIncShift) );
*(*this)[dwIndex] >>= b1BitIncShift;
*(*this)[dwIndex] |= uiCarry;
uiCarry = bNewCarry;
}
}
}
}
// Lose any newly created leading zeros or emptied object.
Normalize();
return( *this );
}
// This method attempts to represent the integer number as double precision floating point number.
// Note that a number from the Integer class may be much larger than the larger number that a double
// precision floating point could represent. Also, note that floating point numbers are not evenly
// distributed having irregularly sized gaps between them. In difference the Integer numbers are
// evenly distributed. This means that Integer numbers could be in fact very rarely represented
// exactly using a floating point number. This function is useful for displaying Integer numbers.
double GetAsDouble() const
{
// The algorithm is to multiply the double 1 by *this and keep the result in a double variable.
if( IsZero() )
{
return( 0 );
}
Integer iFactor( *this );
double dThis( 0 );
double dFactor( 1 );
while( 0 != iFactor )
{
if( iFactor.Shift2Right() )
{
// There was a right carry.
dThis += dFactor;
}
dFactor *= 2;
}
return( dThis );
}
private:
// Shift to right with one bit. Returns true if one has been
// lost by the shift and false if zero was removed (lost).
inline bool Shift2Right()
{
bool bRightCarry( false );
// Head - LSB, Tail - MSB.
for( DWORD dwIndex = GetCount() - 1; (DWORD)-1 != dwIndex; dwIndex-- )
{
const bool bNewRightCarry( 1 & (*(*this)[dwIndex]) );
(*(*this)[dwIndex]) >>= 1;
if( bRightCarry )
{
(*(*this)[dwIndex]) |= (((unsigned __int64)1) << 63);
}
bRightCarry = bNewRightCarry;
}
// Lose any newly created leading zeros.
Normalize();
return( bRightCarry );
}
inline void AddDecimal( MList< BYTE >& listResult, const MList< BYTE >& list2Power ) const
{
const DWORD dwLoopCount( MMAX< DWORD, DWORD, DWORD >( listResult.GetCount(), list2Power.GetCount() ) );
BYTE b1Carry( 0 );
for( DWORD dwSegment = 0; dwSegment < dwLoopCount; dwSegment++ )
{
// The Head is Least Significant Part, and the Tail is Most Significant Part so compute Head-to-Tail.
BYTE b1This( b1Carry );
if( listResult.GetCount() > dwSegment )
{
b1This += *listResult[dwSegment];
}
if( list2Power.GetCount() > dwSegment )
{
b1This += *list2Power[dwSegment];
}
if( 9 < b1This )
{
b1This -= 10;
b1Carry = 1;
}
else
{
b1Carry = 0;
}
if( listResult.GetCount() > dwSegment )
{
*listResult[dwSegment] = b1This;
}
else
{
listResult.AddTail( new BYTE( b1This ) );
}
}
if( 0 != b1Carry )
{
listResult.AddTail( new BYTE( b1Carry ) );
}
}
inline void MultiplyDecimalBy2( MList< BYTE >& list2Power ) const
{
BYTE b1Carry( 0 );
// Head is LSS, Tail is MSS
for( DWORD dwSegment = 0; dwSegment < list2Power.GetCount(); dwSegment++ )
{
BYTE b1New = 2 * (*list2Power[dwSegment]) + b1Carry;
if( 9 < b1New )
{
*list2Power[dwSegment] = b1New - 10;
b1Carry = 1;
}
else
{
*list2Power[dwSegment] = b1New;
b1Carry = 0;
}
}
if( 0 != b1Carry )
{
list2Power.AddTail( new BYTE( b1Carry ) );
}
}
inline void IncrementFromSegment( const DWORD dwSegment )
{
if( dwSegment < GetCount() )
{
// Head LSB, Tail MSB.
if( (unsigned __int64)-1 > *(*this)[dwSegment] )
{
(*(*this)[dwSegment])++;
}
else
{
(*(*this)[dwSegment]) = 0;
IncrementFromSegment( dwSegment + 1 );
}
}
else
{
AddTail( new unsigned __int64( 1 ) );
}
}
// External operators - friend operators.
// Standard comparison operator equal to.
friend bool operator ==( const Integer& iLeft, const Integer& iRight )
{
if( iLeft.GetCount() != iRight.GetCount() )
{
return( false );
}
for( DWORD dwIndex = 0; dwIndex < iLeft.GetCount(); dwIndex++ )
{
if( *iLeft[dwIndex] != *iRight[dwIndex] )
{
return( false );
}
}
return( true );
}
// Standard comparison operator not equal to.
friend bool operator !=( const Integer& rLeft, const Integer& rRight )
{
return( !::operator==( rLeft, rRight ) );
}
// Standard comparison operator less than.
friend inline bool operator <( const Integer& iLeft, const Integer& iRight )
{
if( iLeft.GetCount() == iRight.GetCount() )
{
// When equal size-in-part compare part by part. Compare from Tail to Head, since
// the Head is Least Significant Part, and the Tail is Most Significant Part.
for( DWORD dwIndex = iLeft.GetCount() - 1; (DWORD)-1 > dwIndex; dwIndex-- )
{
if( *iLeft[dwIndex] != *iRight[dwIndex] )
{
return( *iLeft[dwIndex] < *iRight[dwIndex] );
}
}
// All parts are equal, so false.
return( false );
}
return( iLeft.GetCount() < iRight.GetCount() );
}
// Standard comparison operator greater than.
friend inline bool operator >( const Integer& iLeft, const Integer& iRight )
{
if( iLeft.GetCount() == iRight.GetCount() )
{
// When equal size-in-part compare part by part. Compare from Tail to Head, since
// the Head is Least Significant Part, and the Tail is Most Significant Part.
for( DWORD dwIndex = iLeft.GetCount() - 1; (DWORD)-1 > dwIndex; dwIndex-- )
{
if( *iLeft[dwIndex] != *iRight[dwIndex] )
{
return( *iLeft[dwIndex] > *iRight[dwIndex] );
}
}
// All parts are equal, so false.
return( false );
}
return( iLeft.GetCount() > iRight.GetCount() );
}
// Standard comparison operator less than or equal to.
friend inline bool operator <=( const Integer& iLeft, const Integer& iRight )
{
if( iLeft.GetCount() == iRight.GetCount() )
{
// When equal size-in-part compare part by part. Compare from Tail to Head, since
// the Head is Least Significant Part, and the Tail is Most Significant Part.
for( DWORD dwIndex = iLeft.GetCount() - 1; (DWORD)-1 > dwIndex; dwIndex-- )
{
if( *iLeft[dwIndex] != *iRight[dwIndex] )
{
return( *iLeft[dwIndex] <= *iRight[dwIndex] );
}
}
// All parts are equal, so equal.
return( true );
}
return( iLeft.GetCount() < iRight.GetCount() );
}
// Standard comparison operator greater than or equal to.
friend inline bool operator >=( const Integer& iLeft, const Integer& iRight )
{
if( iLeft.GetCount() == iRight.GetCount() )
{
// When equal size-in-part compare part by part. Compare from Tail to Head, since
// the Head is Least Significant Part, and the Tail is Most Significant Part.
for( DWORD dwIndex = iLeft.GetCount() - 1; (DWORD)-1 > dwIndex; dwIndex-- )
{
if( *iLeft[dwIndex] != *iRight[dwIndex] )
{
return( *iLeft[dwIndex] >= *iRight[dwIndex] );
}
}
// All parts are equal, so equal.
return( true );
}
return( iLeft.GetCount() > iRight.GetCount() );
}
// Standard arithmetic operator plus.
friend inline Integer operator +( const Integer& iSummandL, const Integer& iSummandR )
{
// Create an empty result.
Integer iResult( iSummandL, 0 );
const DWORD dwLoopCount( MMAX< DWORD, DWORD, DWORD >( iSummandL.GetCount(), iSummandR.GetCount() ) );
unsigned __int64 uiCarry( 0 );
for( DWORD dwIndex = 0; dwIndex < dwLoopCount; dwIndex++ )
{
// The Head is Least Significant Part, and the Tail is Most Significant Part so compute Headt-to-Tail.
unsigned __int64 uiLeft( 0 );
if( iSummandL.GetCount() > dwIndex )
{
uiLeft = *iSummandL[dwIndex];
}
unsigned __int64 uiRight( 0 );
if( iSummandR.GetCount() > dwIndex )
{
uiRight = *iSummandR[dwIndex];
}
iResult.AddTail( new unsigned __int64( uiLeft + uiRight + uiCarry ) );
// Find out if there is a carry.
unsigned __int64 uiOverflow( (unsigned __int64)-1 - uiLeft );
if( uiOverflow < uiRight )
{
// There was a carry;
uiCarry = 1;
continue;
}
uiOverflow -= uiRight;
uiCarry = uiOverflow < uiCarry ? 1 : 0;
}
if( 0 != uiCarry )
{
MASSERT( 1 == uiCarry );
iResult.AddTail( new unsigned __int64( uiCarry ) );
}
if( 0 == iResult.GetCount() )
{
iResult.AddTail( new unsigned __int64( 0 ) );
}
return( iResult );
}
// Standard arithmetic operator minus. When subtracting larger number from smaller
// the result wraps up and has the size of the larger number, i.e. A > B; C = B - A;
// [size C == size A] = [size B] - [size A], C = 0 - ( A - B ).
friend inline Integer operator -( Integer iMinuend, Integer iSubtrahend )
{
// Create an empty result.
Integer iResult( iMinuend, 0 );
const DWORD dwLoopCount( MMAX< DWORD, DWORD, DWORD >( iMinuend.GetCount(), iSubtrahend.GetCount() ) );
// Create equal elements countinteger numbers.
iMinuend = Integer( iMinuend, dwLoopCount );
iSubtrahend = -Integer( iSubtrahend, dwLoopCount );
unsigned __int64 uiCarry( 0 );
for( DWORD dwIndex = 0; dwIndex < dwLoopCount; dwIndex++ )
{
// The Head is Least Significant Part, and the Tail is Most Significant Part so compute Headt-to-Tail.
const unsigned __int64 uiLeft( *iMinuend[dwIndex] );
const unsigned __int64 uiRight( *iSubtrahend[dwIndex] );
iResult.AddTail( new unsigned __int64( uiLeft + uiRight + uiCarry ) );
// Find out if there is a carry.
unsigned __int64 uiOverflow( (unsigned __int64)-1 - uiLeft );
if( uiOverflow < uiRight )
{
// There was a carry;
uiCarry = 1;
continue;
}
uiOverflow -= uiRight;
uiCarry = uiOverflow < uiCarry ? 1 : 0;
}
if( 0 == iResult.GetCount() )
{
iResult.AddTail( new unsigned __int64( 0 ) );
}
// Note that in subtraction I ignore the most significant Carry.
return( iResult.Normalize() );
}
// Standard arithmetic operator multiplication.
friend inline Integer operator *( const Integer& iFactorL, const Integer& iFactorR )
{
// Fast multiplication algorithm. Push the shorther to the right amending the longer.
Integer iShorter( iFactorL < iFactorR ? iFactorL : iFactorR );
Integer iLonger( iFactorL > iFactorR ? iFactorL : iFactorR );
// Create an empty result.
Integer iResult( iFactorL, 0 );
while( 0 != iShorter )
{
if( iShorter.Shift2Right() )
{
// There was a right carry.
iResult += iLonger;
}
iLonger.Shift2Left( 1 );
}
if( 0 == iResult.GetCount() )
{
iResult.AddTail( new unsigned __int64( 0 ) );
}
return( iResult );
}
// Standard arithmetic operator division. The division operator returns a pair of specialized integers
// for quotient and reminder. This operator throws NumberException exception when dividing by zero.
friend inline Pair< specialize< Integer as sX::Quotient >, specialize< Integer as sX::Reminder > > operator /( Integer iDividend, Integer iDivisor )
{
NumberException< Integer, true >::TestDivisionByZero( iDivisor );
// Fast division algorithm. Push the shorther to the right amending the longer.
unsigned __int64 uiMS1_Divisor( iDivisor.GetMostSignificantOneIndex() );
specialize< Integer as sX::Quotient > iQuotient( specialize< Integer as sX::Quotient >::Initialize( 0 ) );
while( iDividend >= iDivisor )
{
unsigned __int64 uiMS1_Divident( iDividend.GetMostSignificantOneIndex() );
unsigned __int64 uiOrderDifference( uiMS1_Divident - uiMS1_Divisor );
Integer iExpandedDivisor( iDivisor );
iExpandedDivisor.Shift2Left( uiOrderDifference );
if( iDividend < iExpandedDivisor )
{
uiOrderDifference--;
iExpandedDivisor.Shift2Right();
}
iQuotient += Integer( 1 ).Shift2Left( uiOrderDifference );
iDividend -= iExpandedDivisor;
}
return( Pair< specialize< Integer as sX::Quotient >, specialize< Integer as sX::Reminder > >( iQuotient, specialize< Integer as sX::Reminder >::Initialize( iDividend ) ) );
}
// Standard arithmetic operator modulo.
friend inline Integer operator %( const Integer& iDividend, const Integer& iDivisor )
{
return( operator /( iDividend, iDivisor ).GetValueRef() );
}
// Bitwise AND operator.
friend inline Integer operator &( const Integer& iGateL, const Integer& iGateR )
{
// Create an empty result.
Integer iResult( iGateL, 0 );
const DWORD dwLoopCount( MMIN< DWORD, DWORD, DWORD >( iGateL.GetCount(), iGateR.GetCount() ) );
for( DWORD dwIndex = 0; dwIndex < dwLoopCount; dwIndex++ )
{
// The Head is Least Significant Part, and the Tail is Most Significant Part so compute Headt-to-Tail.
iResult.AddTail( new unsigned __int64( *iGateL[dwIndex] & *iGateR[dwIndex] ) );
}
MASSERT( 0 != iResult.GetCount() );
return( iResult );
}
// Bitwise OR operator.
friend inline Integer operator |( const Integer& iGateL, const Integer& iGateR )
{
// Create an empty result.
Integer iResult( iGateL, 0 );
const DWORD dwLoopCount( MMAX< DWORD, DWORD, DWORD >( iGateL.GetCount(), iGateR.GetCount() ) );
for( DWORD dwIndex = 0; dwIndex < dwLoopCount; dwIndex++ )
{
// The Head is Least Significant Part, and the Tail is Most Significant Part so compute Headt-to-Tail.
unsigned __int64 uiLeft( 0 );
if( iGateL.GetCount() > dwIndex )
{
uiLeft = *iGateL[dwIndex];
}
unsigned __int64 uiRight( 0 );
if( iGateR.GetCount() > dwIndex )
{
uiRight = *iGateR[dwIndex];
}
iResult.AddTail( new unsigned __int64( uiLeft | uiRight ) );
}
return( iResult );
}
// Bitwise XOR operator.
friend inline Integer operator ^( const Integer& iGateL, const Integer& iGateR )
{
// Create an empty result.
Integer iResult( iGateL, 0 );
const DWORD dwLoopCount( MMAX< DWORD, DWORD, DWORD >( iGateL.GetCount(), iGateR.GetCount() ) );
for( DWORD dwIndex = 0; dwIndex < dwLoopCount; dwIndex++ )
{
// The Head is Least Significant Part, and the Tail is Most Significant Part so compute Headt-to-Tail.
unsigned __int64 uiLeft( 0 );
if( iGateL.GetCount() > dwIndex )
{
uiLeft = *iGateL[dwIndex];
}
unsigned __int64 uiRight( 0 );
if( iGateR.GetCount() > dwIndex )
{
uiRight = *iGateR[dwIndex];
}
iResult.AddTail( new unsigned __int64( uiLeft ^ uiRight ) );
}
// XOR may cause non zero operands to produce zero result
iResult.Normalize();
return( iResult );
}
// Shift to left operator. This operator may allocate significant amount of system resources if used without care. Passing
// large number of left shifts will incur adding a new 64 bit segment to the result for every 64 units in the shift request.
friend inline Integer operator <<( const Integer& iThisObject, const Integer& iShiftCount )
{
if( iThisObject.IsZero() )
{
return( Integer( 0 ) );
}
Integer iResult( iThisObject );
if( !iShiftCount.IsZero() )
{
const Pair< specialize< Integer as sX::Quotient >, specialize< Integer as sX::Reminder > > prDivision( iShiftCount / 64 );
// The Head is Least Significant Part, and the Tail is Most Significant Part so compute Headt-to-Tail.
// Add one empty segment at the head, i.e. least segnificant part, for every 64 bit shift to the left.
for( Integer iSegment = 0; iSegment < prDivision.GetLabelRef(); iSegment++ )
{
iResult.AddHead( new unsigned __int64( 0 ) );
}
// Division by 64 cannot have remiander bigger than 63.
MASSERT( prDivision.GetValueRef() < 64 );
// Shift for the remainder, 64 is well held in one segment.
iResult.Shift2Left( *prDivision.GetValueRef().GetTail() );
}
return( iResult );
}
// Shift to right operator.
friend inline Integer operator >>( const Integer& iThisObject, const Integer& iShiftCount )
{
if( iThisObject.IsZero() )
{
return( Integer( 0 ) );
}
Integer iResult( iThisObject );
if( !iShiftCount.IsZero() )
{
const Pair< specialize< Integer as sX::Quotient >, specialize< Integer as sX::Reminder > > prDivision( iShiftCount / 64 );
// The Head is Least Significant Part, and the Tail is Most Significant Part so compute Headt-to-Tail.
// Remove one segment from the head, i.e. least segnificant part, for every 64 bit shift to the right.
for( Integer iSegment = 0; (iSegment < prDivision.GetLabelRef()) && (0 < iResult.GetCount()); iSegment++ )
{
delete iResult.RemoveHead();
}
// Division by 64 cannot have remiander bigger than 63.
MASSERT( prDivision.GetValueRef() < 64 );
// Shift for the remainder, 64 is well held in one segment.
iResult.Shift2Right( *prDivision.GetValueRef().GetTail() );
}
return( iResult );
}
};