//
//
// Rational.h: Rational 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 – Copyright © 2011 by Miroslav Bonchev Bonchev. All Rights Reserved.
// {your product} uses the: Object Contextualization Model – Copyright © 2009 - 2011 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 "StringEx.h"
#include "Specialize.h"
#include "Integer.h"
#define Minus_Char_TextSize L"22"
#define Rational_Notation_TextSize L"12"
#define Decimal_Notation_TextSize L"12"
// The RationalTBase template class represents signed rational numbers over an unspecified specializer filed.
// The Rational is a specialization of RationalTBase with the Integer class representing arbitrary precision
// signed rational numbers.
//
// Objects from type Rational expand arbitrarily large up to available memory and are able to accommodate
// arbitrarily large numbers with arbitrary precision (up to the available memory).
//
// Some points of interest:
//
// The rational numbers are represented by a sign and an ordered pair of numerator and denominator elements
// of the underlying commutative ring with identity CRI (the specialiser of the template). When the template
// is specialized with the Integer class, which represents an arbitrarily large unsigned integer numbers, the
// Rational numbers represented by this class become with arbitrary precision and even distribution numbers,
// thus become perfect for precise computations. It is possible to use other types of underlying rings (CRI),
// such as BYTE, thus creating Rational Numbers over Z[2^8], unsigned short achieving rational numbers over
// Z[2^16], unsigned int achieving rational numbers over Z[2^32], unsigned __int64 achieving rational numbers
// over Z[2^64], etc.
//
// Overflow may or may not be signalled depending on the behaviour of the underlying CRI. For example since
// the numbers from the Integer class never overflow, but instead they grow thus maintaining their integrity,
// Rational specialized with Integer never overflows and is always correct. The build in types on the other
// hand ignore any overflows, hence Rational specialized with build in type may become erroneous without
// signalling the overflow. Other specializer types may or may not signal overflow in accordance with their
// behaviour. Numbers of Rational type are always normalized so that the numerator and denominator are always
// coprime.
//
// Objects from this 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 logical operators are NOT overloaded purposefully. The reason is that rational 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.
//
// Bitwise operators are NOT overloaded purposefully as not applicable for a rational type.
//
// Objects from the rational class are able to print themselves in various ways.
template< class UnderlingCRI >
class RationalTBase
{
private:
bool bNegative;
specialize< UnderlingCRI as sX::Numerator > uiN;
specialize< UnderlingCRI as sX::Denominator > uiD;
public:
// Default constructor - initializes the object with zero.
RationalTBase()
: bNegative( false ),
uiN( specialize< UnderlingCRI as sX::Numerator >::Initialize( 0 ) ),
uiD( specialize< UnderlingCRI as sX::Denominator >::Initialize( 1 ) )
{
}
// Constructor from signed integer.
RationalTBase( const __int64 nInteger )
: bNegative( 0 > nInteger ),
uiN( specialize< UnderlingCRI as sX::Numerator >::Initialize( MABSsat< UnderlingCRI, __int64 >( nInteger ) ) ),
uiD( specialize< UnderlingCRI as sX::Denominator >::Initialize( 1 ) )
{
Normalize();
}
// Copy constructor.
RationalTBase( const RationalTBase< UnderlingCRI >& rational )
: bNegative( rational.bNegative ),
uiN( rational.uiN ),
uiD( rational.uiD )
{
}
// Constructor from unsigned Integer.
RationalTBase( const specialize< UnderlingCRI as sX::Numerator >& uiNumerator )
: bNegative( false ),
uiN( uiNumerator ),
uiD( specialize< UnderlingCRI as sX::Denominator >::Initialize( 1 ) )
{
Normalize();
}
// Constructor from signed and numerator, and denominator.
RationalTBase( const bool bNegative,
const specialize< UnderlingCRI as sX::Numerator >& uiNumerator )
: bNegative( bNegative ),
uiN( uiNumerator ),
uiD( specialize< UnderlingCRI as sX::Denominator >::Initialize( 1 ) )
{
Normalize();
}
// Constructor from unsigned numerator and denominator.
RationalTBase( const specialize< UnderlingCRI as sX::Numerator >& uiNumerator,
const specialize< UnderlingCRI as sX::Denominator >& uiDenominator )
: bNegative( false ),
uiN( uiNumerator ),
uiD( uiDenominator )
{
NumberException< UnderlingCRI, true >::TestDivisionByZero( uiD );
Normalize();
}
// Constructor from signed and numerator, and denominator.
RationalTBase( const bool bNegative,
const specialize< UnderlingCRI as sX::Numerator >& uiNumerator,
const specialize< UnderlingCRI as sX::Denominator >& uiDenominator )
: bNegative( bNegative ),
uiN( uiNumerator ),
uiD( uiDenominator )
{
NumberException< UnderlingCRI, true >::TestDivisionByZero( uiD );
Normalize();
}
// Destructor.
~RationalTBase()
{
}
// Standard operator equal.
RationalTBase< UnderlingCRI >& operator=( const RationalTBase< UnderlingCRI >& rational )
{
bNegative = rational.bNegative;
uiN = rational.uiN;
uiD = rational.uiD;
return( *this );
}
// Standard operator +=
RationalTBase< UnderlingCRI > operator +=( const RationalTBase< UnderlingCRI >& rSummand )
{
return( *this = *this + rSummand );
}
// Standard operator -=
RationalTBase< UnderlingCRI > operator -=( const RationalTBase< UnderlingCRI >& rSubtrahend )
{
return( *this = *this - rSubtrahend );
}
// Standard operator *=
RationalTBase< UnderlingCRI > operator *=( const RationalTBase< UnderlingCRI >& rFactor )
{
return( *this = *this * rFactor );
}
// Standard operator /=
RationalTBase< UnderlingCRI > operator /=( const RationalTBase< UnderlingCRI >& rDivisor )
{
return( *this = *this / rDivisor );
}
// Returns an rational power of this integer.
inline RationalTBase< UnderlingCRI > ToPower( const Integer& uiPower ) const
{
RationalTBase< UnderlingCRI > rThis( 1 );
for( Integer uiCount = 0; uiCount < uiPower; uiCount += 1 )
{
rThis = rThis * *this;
}
return( rThis );
}
// Unary plus (returns the operand itself).
RationalTBase< UnderlingCRI > operator+() const
{
return( *this );
}
// Unary operator negation – inverts the signd.
RationalTBase< UnderlingCRI > operator-() const
{
return( IsZero() ? *this : RationalTBase< UnderlingCRI >( !bNegative, uiN, uiD ) );
}
// Test if the number is zero.
bool IsZero() const
{
return( 0 == uiN );
}
// Test if the number is positive.
bool IsPositive() const
{
return( !bNegative );
}
// Test if the number is negative.
bool IsNegative() const
{
return( bNegative );
}
// Returns the numerator.
const UnderlingCRI& GetNumerator() const
{
return( uiN );
}
// Returns the denominator.
const UnderlingCRI& GetDenominator() const
{
return( uiD );
}
// This method returns the numerator as double precision floating point number. This method is
// intended for use when the Rational is specialized with the Integer class. If used with another
// specializer type, it must have method double GetAsDouble() const. 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 GetNumeratorAsDouble() const
{
return( uiN.GetAsDouble() );
}
// This method returns the denominator as double precision floating point number. This method is
// intended for use when the Rational is specialized with the Integer class. If used with another
// specializer type, it must have method double GetAsDouble() const. 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 GetDenominatorAsDouble() const
{
return( uiD.GetAsDouble() );
}
// The method returns the rational number as a double precision floating point number. This method
// is intended for use when the Rational is specialized with the Integer class. If used with another
// specializer type, it must have method double GetAsDouble() const. Note that a number from the
// Rational class may be much larger than the larger number that a double precision floating point
// could represent and is also PRECISE. Also, note that floating point numbers are not evenly
// distributed having irregularly sized gaps between them. In difference the Rational specialized
// with Integer are evenly distributed and PRECISE. This means that Rational specialized with Integer
// number could be in fact very rarely represented using a floating point number. This function is
// useful for displaying Rational numbers for informative purpoces.
double GetAsDouble() const
{
return( (bNegative ? -1 : 1) * GetNumeratorAsDouble() / GetDenominatorAsDouble() );
}
// This method returns a signed pair +/-( numerator, denominator) representing the rational number exactly.
// This method is intended for use when the Rational is specialized with the Integer class. If used with
// another specializer type, it must have method string Print() const, where string must have LPCTSTR
// overloaded operator. Although this method returns the exact rational number, in some circumstances
// one may want to also consider using the float representations for informative purposes as their results
// may be easier to interpret.
MStringEx< TCHAR > Print() const
{
return( MStringEx< TCHAR >( MStringEx< TCHAR >::FF, TEXT("%c(%s,%s)"), bNegative ? TCHAR('-') : TCHAR('+'), (LPCTSTR)uiN.Print(), (LPCTSTR)uiD.Print() ) );
}
// This method returns the double representation of the rational number as a string in decimal notation.
// The parameter sets the required number of digits after the decimal point, max number is 16. Note that
// the floating point representation is most likely inaccurate to some degree depending on the represented
// number. Floating point numbers cannot represent proper rational numbers satisfactory.
MStringEx< TCHAR > PrintAsDoubleInDecimalNotation( const BYTE b1Precision ) const
{
return( MStringEx< TCHAR >( MStringEx< TCHAR >::FF, TEXT("%+.") + MStringEx< TCHAR >( MStringEx< TCHAR >::FF, TEXT("%d"), (0x0F & (b1Precision-1))+1 ) + TEXT("f"), GetAsDouble() ) );
}
// This method returns a HTML table containing the rational number in rational notation and floating point
// notation. This method is intended for use when the Rational is specialized with the Integer class. If
// used with another specializer type, it must have defined the methods used by this function. The parameter
// passed to the method is string which is inserted in the HTML table. Thus one can pass additional
// information to be printed together with the rational number, inside the returned HTML table.
MStringEx< TCHAR > PrintAsHtmlCell() const
{
// |-table 1---------------------------------------|-----------------------------------------------|
// | |-table 2-----------------------------------| | |
// | | sign | table 3 - rational notation | | double approximation |
// | |-------------------------------------------| | |
// |-----------------------------------------------|-----------------------------------------------|
return( MStringEx< TCHAR >( MStringEx< TCHAR >::FF,
L"<table border='0' cellpadding='0' cellspacing='0' style='text-align: right;'>\
<tr><td style='padding-right:10px; text-align: right; width: 500px;'>\
<table border='0' cellpadding='0' cellspacing='0'>\
<tr>\
<td style='font-size:" Minus_Char_TextSize L"px;'>%c </td>\
<td><table border='0' cellpadding='0' cellspacing='0' style='text-align: right; font-size:" Rational_Notation_TextSize L"px;'><tr><td style='border-bottom:solid black thin;'>%s</td></tr><tr><td>%s</td></tr></table></td>\
</tr>\
</table>\
</td>\
<td style='padding-left:20px; text-align: left; font-size:" Decimal_Notation_TextSize L"px; width: 200px;'>%s</td>\
</tr></table>", bNegative ? TCHAR('-') : TCHAR('+'), (LPCTSTR)uiN.Print(), (LPCTSTR)uiD.Print(), (LPCTSTR)PrintAsDoubleInDecimalNotation( 16 ) ) );
}
private:
void Normalize()
{
if( 0 != uiN )
{
UnderlingCRI uiDivident( MMAX< UnderlingCRI, UnderlingCRI >( uiN, uiD ) );
UnderlingCRI uiDivisor( MMIN< UnderlingCRI, UnderlingCRI >( uiN, uiD ) );
UnderlingCRI uiQuotient( uiDivident.DivideBy_ReturnQuotient( uiDivisor ) );
for( UnderlingCRI uiReminder( uiDivident - uiDivisor * uiQuotient ); 0 != uiReminder; uiReminder = uiDivident - uiDivisor * uiQuotient )
{
uiDivident = uiDivisor;
uiDivisor = uiReminder;
uiQuotient = uiDivident.DivideBy_ReturnQuotient( uiDivisor );
}
if( 1 != uiDivisor )
{
uiN /= uiDivisor;
uiD /= uiDivisor;
}
}
else
{
bNegative = false;
uiD = specialize< UnderlingCRI as sX::Denominator >::Initialize( 1 );
}
}
// External operators - friend operators.
// Standard comparison operator equal to.
friend inline bool operator ==( const RationalTBase< UnderlingCRI >& rLeft, const RationalTBase< UnderlingCRI >& rRight )
{
return( (rLeft.bNegative == rRight.bNegative) && (rLeft.uiN == rRight.uiN) && (rLeft.uiD == rRight.uiD) );
}
// Standard comparison operator not equal to.
friend inline bool operator !=( const RationalTBase< UnderlingCRI >& rLeft, const RationalTBase< UnderlingCRI >& rRight )
{
return( (rLeft.bNegative != rRight.bNegative) || (rLeft.uiN != rRight.uiN) || (rLeft.uiD != rRight.uiD) );
}
// Standard comparison operator less than.
friend inline bool operator <( const RationalTBase< UnderlingCRI >& rLeft, const RationalTBase< UnderlingCRI >& rRight )
{
if( rLeft.bNegative ^ rRight.bNegative )
{
// One is negative, the other positive.
return( rLeft.bNegative );
}
return( rLeft.bNegative ? (rLeft.uiN * rRight.uiD) > (rRight.uiN * rLeft.uiD) : (rLeft.uiN * rRight.uiD) < (rRight.uiN * rLeft.uiD) );
}
// Standard comparison operator greater than.
friend inline bool operator >( const RationalTBase< UnderlingCRI >& rLeft, const RationalTBase< UnderlingCRI >& rRight )
{
if( rLeft.bNegative ^ rRight.bNegative )
{
// One is negative, the other positive.
return( rRight.bNegative );
}
return( rLeft.bNegative ? (rLeft.uiN * rRight.uiD) < (rRight.uiN * rLeft.uiD) : (rLeft.uiN * rRight.uiD) > (rRight.uiN * rLeft.uiD) );
}
// Standard comparison operator less than or equal to.
friend inline bool operator <=( const RationalTBase< UnderlingCRI >& rLeft, const RationalTBase< UnderlingCRI >& rRight )
{
if( rLeft.bNegative ^ rRight.bNegative )
{
// One is negative, the other positive.
return( rLeft.bNegative );
}
return( rLeft.bNegative ? (rLeft.uiN * rRight.uiD) >= (rRight.uiN * rLeft.uiD) : (rLeft.uiN * rRight.uiD) <= (rRight.uiN * rLeft.uiD) );
}
// Standard comparison operator greater than or equal to.
friend inline bool operator >=( const RationalTBase< UnderlingCRI >& rLeft, const RationalTBase< UnderlingCRI >& rRight )
{
if( rLeft.bNegative ^ rRight.bNegative )
{
// One is negative, the other positive.
return( rRight.bNegative );
}
return( rLeft.bNegative ? (rLeft.uiN * rRight.uiD) <= (rRight.uiN * rLeft.uiD) : (rLeft.uiN * rRight.uiD) >= (rRight.uiN * rLeft.uiD) );
}
// Standard arithmetic operator plus.
friend inline RationalTBase< UnderlingCRI > operator +( const RationalTBase< UnderlingCRI >& iSummandL, const RationalTBase< UnderlingCRI >& iSummandR )
{
const UnderlingCRI uiL( iSummandL.uiN * iSummandR.uiD );
const UnderlingCRI uiR( iSummandR.uiN * iSummandL.uiD );
Rational r;
if( iSummandL.bNegative ^ iSummandR.bNegative )
{
// Both operands are have different signs.
r.uiN = specialize< UnderlingCRI as sX::Numerator >::Initialize( MMAX< UnderlingCRI, UnderlingCRI, UnderlingCRI >( uiL, uiR ) - MMIN< UnderlingCRI, UnderlingCRI, UnderlingCRI >( uiL, uiR ) );
r.bNegative = uiL > uiR ? iSummandL.bNegative : iSummandR.bNegative;
}
else
{
// Both operands are the same sign.
r.uiN = specialize< UnderlingCRI as sX::Numerator >::Initialize( uiL + uiR );
r.bNegative = iSummandL.bNegative;
}
r.uiD = specialize< UnderlingCRI as sX::Denominator >::Initialize( iSummandL.uiD * iSummandR.uiD );
r.Normalize();
return( r );
}
// Standard arithmetic operator minus.
friend inline RationalTBase< UnderlingCRI > operator -( const RationalTBase< UnderlingCRI >& rMinuend, const RationalTBase< UnderlingCRI >& rSubtrahend )
{
return( rMinuend + (-rSubtrahend) );
}
// Standard arithmetic operator minus.
friend inline RationalTBase< UnderlingCRI > operator -( const Integer& iMinuend, const RationalTBase< UnderlingCRI >& rSubtrahend )
{
return( RationalTBase< UnderlingCRI >( specialize< UnderlingCRI as sX::Numerator >::Initialize( iMinuend ), specialize< UnderlingCRI as sX::Denominator >::Initialize( 1 ) ) + (-rSubtrahend) );
}
// Standard arithmetic operator minus.
friend inline RationalTBase< UnderlingCRI > operator -( const RationalTBase< UnderlingCRI >& rMinuend, const Integer& iSubtrahend )
{
return( rMinuend + (-RationalTBase< UnderlingCRI >( specialize< UnderlingCRI as sX::Numerator >::Initialize( iSubtrahend ), specialize< UnderlingCRI as sX::Denominator >::Initialize( 1 ) )) );
}
// Standard arithmetic operator multiplication.
friend inline RationalTBase< UnderlingCRI > operator *( const RationalTBase< UnderlingCRI >& rFactorL, const RationalTBase< UnderlingCRI >& rFactorR )
{
return( Rational( rFactorL.bNegative ^ rFactorR.bNegative, specialize< UnderlingCRI as sX::Numerator >::Initialize( rFactorL.uiN * rFactorR.uiN ), specialize< UnderlingCRI as sX::Denominator >::Initialize( rFactorL.uiD * rFactorR.uiD ) ) );
}
// Standard arithmetic operator multiplication.
friend inline RationalTBase< UnderlingCRI > operator *( const RationalTBase< UnderlingCRI >& rFactorL, const Integer& iFactorR )
{
return( Rational( rFactorL.bNegative, specialize< UnderlingCRI as sX::Numerator >::Initialize( iFactorR * rFactorL.uiN ), specialize< UnderlingCRI as sX::Denominator >::Initialize( rFactorL.uiD ) ) );
}
// Standard arithmetic operator multiplication.
friend inline RationalTBase< UnderlingCRI > operator *( const Integer& iFactorL, const RationalTBase< UnderlingCRI >& rFactorR )
{
return( Rational( rFactorR.bNegative, specialize< UnderlingCRI as sX::Numerator >::Initialize( iFactorL * rFactorR.uiN ), specialize< UnderlingCRI as sX::Denominator >::Initialize( rFactorR.uiD ) ) );
}
// Standard arithmetic operator multiplication.
friend inline RationalTBase< UnderlingCRI > operator *( const RationalTBase< UnderlingCRI >& rFactorL, const unsigned __int64& iFactorR )
{
return( Rational( rFactorL.bNegative, specialize< UnderlingCRI as sX::Numerator >::Initialize( Integer( iFactorR ) * rFactorR.uiN ), specialize< UnderlingCRI as sX::Denominator >::Initialize( rFactorL.uiD ) ) );
}
// Standard arithmetic operator multiplication.
friend inline RationalTBase< UnderlingCRI > operator *( const unsigned __int64& iFactorL, const RationalTBase< UnderlingCRI >& rFactorR )
{
return( Rational( rFactorR.bNegative, specialize< UnderlingCRI as sX::Numerator >::Initialize( Integer( iFactorL ) * rFactorR.uiN ), specialize< UnderlingCRI as sX::Denominator >::Initialize( rFactorR.uiD ) ) );
}
// Standard arithmetic operator division. This operator throws
// NumberException exception when dividing by zero.
friend inline RationalTBase< UnderlingCRI > operator /( const RationalTBase< UnderlingCRI >& rDividend, const RationalTBase< UnderlingCRI >& rDivisor )
{
NumberException< RationalTBase< UnderlingCRI >, true >::TestDivisionByZero( rDivisor );
return( Rational( rDividend.bNegative ^ rDivisor.bNegative, specialize< UnderlingCRI as sX::Numerator >::Initialize( rDividend.uiN * rDivisor.uiD ), specialize< UnderlingCRI as sX::Denominator >::Initialize( rDividend.uiD * rDivisor.uiN ) ) );
}
};
typedef RationalTBase< Integer > Rational;