// Rational.h: Rational with arbitrary precision.

// Proper Numbers Library

//******************************************************************************************************

// Open Source License – The MIT License

// 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-----------------------------------| | |

// | |-------------------------------------------| | |

// |-----------------------------------------------|-----------------------------------------------|

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&nbsp</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 ) )) );

}