// David Eberly, Geometric Tools, Redmond WA 98052 // Copyright (c) 1998-2020 // Distributed under the Boost Software License, Version 1.0. // https://www.boost.org/LICENSE_1_0.txt // https://www.geometrictools.com/License/Boost/LICENSE_1_0.txt // Version: 4.0.2019.11.03 #pragma once #include // See the comments in BSNumber.h about the UInteger requirements. The // denominator of a BSRational is chosen to be positive, which allows some // simplification of comparisons. Also see the comments about exposing the // GTE_BINARY_SCIENTIFIC_SHOW_DOUBLE conditional define. namespace WwiseGTE { template class BSRational { public: // Construction. The default constructor generates the zero // BSRational. The constructors that take only numerators set the // denominators to one. BSRational() : mNumerator(0), mDenominator(1) { #if defined(GTE_BINARY_SCIENTIFIC_SHOW_DOUBLE) mValue = (double)*this; #endif } BSRational(BSRational const& r) { *this = r; } BSRational(float numerator) : mNumerator(numerator), mDenominator(1.0f) { #if defined(GTE_BINARY_SCIENTIFIC_SHOW_DOUBLE) mValue = (double)*this; #endif } BSRational(double numerator) : mNumerator(numerator), mDenominator(1.0) { #if defined(GTE_BINARY_SCIENTIFIC_SHOW_DOUBLE) mValue = (double)*this; #endif } BSRational(int32_t numerator) : mNumerator(numerator), mDenominator(1) { #if defined(GTE_BINARY_SCIENTIFIC_SHOW_DOUBLE) mValue = (double)*this; #endif } BSRational(uint32_t numerator) : mNumerator(numerator), mDenominator(1) { #if defined(GTE_BINARY_SCIENTIFIC_SHOW_DOUBLE) mValue = (double)*this; #endif } BSRational(int64_t numerator) : mNumerator(numerator), mDenominator(1) { #if defined(GTE_BINARY_SCIENTIFIC_SHOW_DOUBLE) mValue = (double)*this; #endif } BSRational(uint64_t numerator) : mNumerator(numerator), mDenominator(1) { #if defined(GTE_BINARY_SCIENTIFIC_SHOW_DOUBLE) mValue = (double)*this; #endif } BSRational(BSNumber const& numerator) : mNumerator(numerator), mDenominator(1) { #if defined(GTE_BINARY_SCIENTIFIC_SHOW_DOUBLE) mValue = (double)*this; #endif } BSRational(float numerator, float denominator) : mNumerator(numerator), mDenominator(denominator) { LogAssert(mDenominator.mSign != 0, "Division by zero."); if (mDenominator.mSign < 0) { mNumerator.mSign = -mNumerator.mSign; mDenominator.mSign = 1; } #if defined(GTE_BINARY_SCIENTIFIC_SHOW_DOUBLE) mValue = (double)*this; #endif } BSRational(double numerator, double denominator) : mNumerator(numerator), mDenominator(denominator) { LogAssert(mDenominator.mSign != 0, "Division by zero."); if (mDenominator.mSign < 0) { mNumerator.mSign = -mNumerator.mSign; mDenominator.mSign = 1; } #if defined(GTE_BINARY_SCIENTIFIC_SHOW_DOUBLE) mValue = (double)*this; #endif } BSRational(int32_t numerator, int32_t denominator) : mNumerator(numerator), mDenominator(denominator) { LogAssert(mDenominator.mSign != 0, "Division by zero."); if (mDenominator.mSign < 0) { mNumerator.mSign = -mNumerator.mSign; mDenominator.mSign = 1; } #if defined(GTE_BINARY_SCIENTIFIC_SHOW_DOUBLE) mValue = (double)*this; #endif } BSRational(uint32_t numerator, uint32_t denominator) : mNumerator(numerator), mDenominator(denominator) { LogAssert(mDenominator.mSign != 0, "Division by zero."); if (mDenominator.mSign < 0) { mNumerator.mSign = -mNumerator.mSign; mDenominator.mSign = 1; } #if defined(GTE_BINARY_SCIENTIFIC_SHOW_DOUBLE) mValue = (double)*this; #endif } BSRational(int64_t numerator, int64_t denominator) : mNumerator(numerator), mDenominator(denominator) { LogAssert(mDenominator.mSign != 0, "Division by zero."); if (mDenominator.mSign < 0) { mNumerator.mSign = -mNumerator.mSign; mDenominator.mSign = 1; } #if defined(GTE_BINARY_SCIENTIFIC_SHOW_DOUBLE) mValue = (double)*this; #endif } BSRational(uint64_t numerator, uint64_t denominator) : mNumerator(numerator), mDenominator(denominator) { LogAssert(mDenominator.mSign != 0, "Division by zero."); if (mDenominator.mSign < 0) { mNumerator.mSign = -mNumerator.mSign; mDenominator.mSign = 1; } #if defined(GTE_BINARY_SCIENTIFIC_SHOW_DOUBLE) mValue = (double)*this; #endif } BSRational(BSNumber const& numerator, BSNumber const& denominator) : mNumerator(numerator), mDenominator(denominator) { LogAssert(mDenominator.mSign != 0, "Division by zero."); if (mDenominator.mSign < 0) { mNumerator.mSign = -mNumerator.mSign; mDenominator.mSign = 1; } // Set the exponent of the denominator to zero, but you can do so // only by modifying the biased exponent. Adjust the numerator // accordingly. This prevents large growth of the exponents in // both numerator and denominator simultaneously. mNumerator.mBiasedExponent -= mDenominator.GetExponent(); mDenominator.mBiasedExponent = -(mDenominator.GetUInteger().GetNumBits() - 1); #if defined(GTE_BINARY_SCIENTIFIC_SHOW_DOUBLE) mValue = (double)*this; #endif } BSRational(std::string const& number) { LogAssert(number.size() > 0, "A number must be specified."); // Get the leading '+' or '-' if it exists. std::string fpNumber; int sign; if (number[0] == '+') { fpNumber = number.substr(1); sign = +1; LogAssert(fpNumber.size() > 1, "Invalid number format."); } else if (number[0] == '-') { fpNumber = number.substr(1); sign = -1; LogAssert(fpNumber.size() > 1, "Invalid number format."); } else { fpNumber = number; sign = +1; } size_t decimal = fpNumber.find('.'); if (decimal != std::string::npos) { if (decimal > 0) { if (decimal < fpNumber.size()) { // The number is "x.y". BSNumber intPart = BSNumber::ConvertToInteger(fpNumber.substr(0, decimal)); BSRational frcPart = ConvertToFraction(fpNumber.substr(decimal + 1)); mNumerator = intPart * frcPart.mDenominator + frcPart.mNumerator; mDenominator = frcPart.mDenominator; } else { // The number is "x.". mNumerator = BSNumber::ConvertToInteger(fpNumber.substr(0,fpNumber.size()-1)); mDenominator = 1; } } else { // The number is ".y". BSRational frcPart = ConvertToFraction(fpNumber.substr(1)); mNumerator = frcPart.mNumerator; mDenominator = frcPart.mDenominator; } } else { // The number is "x". mNumerator = BSNumber::ConvertToInteger(fpNumber); mDenominator = 1; } mNumerator.SetSign(sign); } BSRational(const char* number) : BSRational(std::string(number)) { } // Implicit conversions. These always use the default rounding mode, // round-to-nearest-ties-to-even. operator float() const { float output; Convert(*this, FE_TONEAREST, output); return output; } operator double() const { double output; Convert(*this, FE_TONEAREST, output); return output; } // Assignment. BSRational& operator=(BSRational const& r) { mNumerator = r.mNumerator; mDenominator = r.mDenominator; #if defined(GTE_BINARY_SCIENTIFIC_SHOW_DOUBLE) mValue = (double)*this; #endif return *this; } // Support for move semantics. BSRational(BSRational&& r) { *this = std::move(r); } BSRational& operator=(BSRational&& r) { mNumerator = std::move(r.mNumerator); mDenominator = std::move(r.mDenominator); #if defined(GTE_BINARY_SCIENTIFIC_SHOW_DOUBLE) mValue = (double)*this; #endif return *this; } // Member access. inline void SetSign(int sign) { mNumerator.SetSign(sign); mDenominator.SetSign(1); } inline int GetSign() const { return mNumerator.GetSign() * mDenominator.GetSign(); } inline BSNumber const& GetNumerator() const { return mNumerator; } inline BSNumber& GetNumerator() { return mNumerator; } inline BSNumber const& GetDenominator() const { return mDenominator; } inline BSNumber& GetDenominator() { return mDenominator; } // Comparisons. bool operator==(BSRational const& r) const { // Do inexpensive sign tests first for optimum performance. if (mNumerator.mSign != r.mNumerator.mSign) { return false; } if (mNumerator.mSign == 0) { // The numbers are both zero. return true; } return mNumerator * r.mDenominator == mDenominator * r.mNumerator; } bool operator!=(BSRational const& r) const { return !operator==(r); } bool operator< (BSRational const& r) const { // Do inexpensive sign tests first for optimum performance. if (mNumerator.mSign > 0) { if (r.mNumerator.mSign <= 0) { return false; } } else if (mNumerator.mSign == 0) { return r.mNumerator.mSign > 0; } else if (mNumerator.mSign < 0) { if (r.mNumerator.mSign >= 0) { return true; } } return mNumerator * r.mDenominator < mDenominator * r.mNumerator; } bool operator<=(BSRational const& r) const { return !r.operator<(*this); } bool operator> (BSRational const& r) const { return r.operator<(*this); } bool operator>=(BSRational const& r) const { return !operator<(r); } // Unary operations. BSRational operator+() const { return *this; } BSRational operator-() const { return BSRational(-mNumerator, mDenominator); } // Arithmetic. BSRational operator+(BSRational const& r) const { BSNumber product0 = mNumerator * r.mDenominator; BSNumber product1 = mDenominator * r.mNumerator; BSNumber numerator = product0 + product1; // Complex expressions can lead to 0/denom, where denom is not 1. if (numerator.mSign != 0) { BSNumber denominator = mDenominator * r.mDenominator; return BSRational(numerator, denominator); } else { return BSRational(0); } } BSRational operator-(BSRational const& r) const { BSNumber product0 = mNumerator * r.mDenominator; BSNumber product1 = mDenominator * r.mNumerator; BSNumber numerator = product0 - product1; // Complex expressions can lead to 0/denom, where denom is not 1. if (numerator.mSign != 0) { BSNumber denominator = mDenominator * r.mDenominator; return BSRational(numerator, denominator); } else { return BSRational(0); } } BSRational operator*(BSRational const& r) const { BSNumber numerator = mNumerator * r.mNumerator; // Complex expressions can lead to 0/denom, where denom is not 1. if (numerator.mSign != 0) { BSNumber denominator = mDenominator * r.mDenominator; return BSRational(numerator, denominator); } else { return BSRational(0); } } BSRational operator/(BSRational const& r) const { LogAssert(r.mNumerator.mSign != 0, "Division by zero in BSRational::operator/."); BSNumber numerator = mNumerator * r.mDenominator; // Complex expressions can lead to 0/denom, where denom is not 1. if (numerator.mSign != 0) { BSNumber denominator = mDenominator * r.mNumerator; if (denominator.mSign < 0) { numerator.mSign = -numerator.mSign; denominator.mSign = 1; } return BSRational(numerator, denominator); } else { return BSRational(0); } } BSRational& operator+=(BSRational const& r) { *this = operator+(r); return *this; } BSRational& operator-=(BSRational const& r) { *this = operator-(r); return *this; } BSRational& operator*=(BSRational const& r) { *this = operator*(r); return *this; } BSRational& operator/=(BSRational const& r) { *this = operator/(r); return *this; } // Disk input/output. The fstream objects should be created using // std::ios::binary. The return value is 'true' iff the operation // was successful. bool Write(std::ostream& output) const { return mNumerator.Write(output) && mDenominator.Write(output); } bool Read(std::istream& input) { return mNumerator.Read(input) && mDenominator.Read(input); } private: // Helper for converting a string to a BSRational, where the string // is the fractional part "y" of the string "x.y". static BSRational ConvertToFraction(std::string const& number) { LogAssert(number.find_first_not_of("0123456789") == std::string::npos, "Invalid number format."); BSRational y(0), ten(10), pow10(10); for (size_t i = 0; i < number.size(); ++i) { int digit = static_cast(number[i]) - static_cast('0'); if (digit > 0) { y += BSRational(digit) / pow10; } pow10 *= ten; } return y; } #if defined(GTE_BINARY_SCIENTIFIC_SHOW_DOUBLE) public: // List this first so that it shows up first in the debugger watch // window. double mValue; private: #endif BSNumber mNumerator, mDenominator; }; // Explicit conversion to a user-specified precision. The rounding // mode is one of the flags provided in . The modes are // FE_TONEAREST: round to nearest ties to even // FE_DOWNWARD: round towards negative infinity // FE_TOWARDZERO: round towards zero // FE_UPWARD: round towards positive infinity template void Convert(BSRational const& input, int32_t precision, int32_t roundingMode, BSNumber& output) { if (precision <= 0) { LogError("Precision must be positive."); } int64_t const maxSize = static_cast(UInteger::GetMaxSize()); int64_t const excess = 32LL * maxSize - static_cast(precision); if (excess <= 0) { LogError("The maximum precision has been exceeded."); } if (input.GetSign() == 0) { output = BSNumber(0); return; } BSNumber n = input.GetNumerator(); BSNumber d = input.GetDenominator(); // The ratio is abstractly of the form n/d = (1.u*2^p)/(1.v*2^q). // Convert to the form // (1.u/1.v)*2^{p-q}, if 1.u >= 1.v // 2*(1.u/1.v)*2^{p-q-1} if 1.u < 1.v // which are in the interval [1,2). int32_t sign = n.GetSign() * d.GetSign(); n.SetSign(1); d.SetSign(1); int32_t pmq = n.GetExponent() - d.GetExponent(); n.SetExponent(0); d.SetExponent(0); if (n < d) { n.SetExponent(n.GetExponent() + 1); --pmq; } // Let p = precision. At this time, n/d = 1.c in [1,2). Define the // sequence of bits w = 1c = w_{p-1} w_{p-2} ... w_0 r, where // w_{p-1} = 1. The bits r after w_0 are used for rounding based on // the user-specified rounding mode. // Compute p bits for w, the leading bit guaranteed to be 1 and // occurring at index (1 << (precision-1)). BSNumber one(1), two(2); UInteger& w = output.GetUInteger(); w.SetNumBits(precision); w.SetAllBitsToZero(); int32_t const size = w.GetSize(); int32_t const precisionM1 = precision - 1; int32_t const leading = precisionM1 % 32; uint32_t mask = (1 << leading); auto& bits = w.GetBits(); int32_t current = size - 1; int32_t lastBit = -1; for (int i = precisionM1; i >= 0; --i) { if (n < d) { n = two * n; lastBit = 0; } else { n = two * (n - d); bits[current] |= mask; lastBit = 1; } if (mask == 0x00000001u) { --current; mask = 0x80000000u; } else { mask >>= 1; } } // At this point as a sequence of bits, r = n/d = r0 r1 ... if (roundingMode == FE_TONEAREST) { n = n - d; if (n.GetSign() > 0 || (n.GetSign() == 0 && lastBit == 1)) { // round up pmq += w.RoundUp(); } // else round down, equivalent to truncating the r bits } else if (roundingMode == FE_UPWARD) { if (n.GetSign() > 0 && sign > 0) { // round up pmq += w.RoundUp(); } // else round down, equivalent to truncating the r bits } else if (roundingMode == FE_DOWNWARD) { if (n.GetSign() > 0 && sign < 0) { // Round down. This is the round-up operation applied to // w, but the final sign is negative which amounts to // rounding down. pmq += w.RoundUp(); } // else round down, equivalent to truncating the r bits } else if (roundingMode != FE_TOWARDZERO) { // Currently, no additional implementation-dependent modes // are supported for rounding. LogError("Implementation-dependent rounding mode not supported."); } // else roundingMode == FE_TOWARDZERO. Truncate the r bits, which // requires no additional work. // Do not use SetExponent(pmq) at this step. The number of // requested bits is 'precision' but w.GetNumBits() will be // different when round-up occurs, and SetExponent accesses // w.GetNumBits(). output.SetSign(sign); output.SetBiasedExponent(pmq - precisionM1); } // This conversion is used to avoid having to expose BSNumber in the // APConversion class as well as other places where BSRational // is passed via a template parameter named Rational. template void Convert(BSRational const& input, int32_t precision, int32_t roundingMode, BSRational& output) { BSNumber numerator; Convert(input, precision, roundingMode, numerator); output = BSRational(numerator); } // Convert to 'float' or 'double' using the specified rounding mode. template void Convert(BSRational const& input, int32_t roundingMode, FPType& output) { static_assert(std::is_floating_point::value, "Invalid floating-point type."); BSNumber number; Convert(input, std::numeric_limits::digits, roundingMode, number); output = static_cast(number); } } namespace std { // TODO: Allow for implementations of the math functions in which a // specified precision is used when computing the result. template inline WwiseGTE::BSRational acos(WwiseGTE::BSRational const& x) { return (WwiseGTE::BSRational)std::acos((double)x); } template inline WwiseGTE::BSRational acosh(WwiseGTE::BSRational const& x) { return (WwiseGTE::BSRational)std::acosh((double)x); } template inline WwiseGTE::BSRational asin(WwiseGTE::BSRational const& x) { return (WwiseGTE::BSRational)std::asin((double)x); } template inline WwiseGTE::BSRational asinh(WwiseGTE::BSRational const& x) { return (WwiseGTE::BSRational)std::asinh((double)x); } template inline WwiseGTE::BSRational atan(WwiseGTE::BSRational const& x) { return (WwiseGTE::BSRational)std::atan((double)x); } template inline WwiseGTE::BSRational atanh(WwiseGTE::BSRational const& x) { return (WwiseGTE::BSRational)std::atanh((double)x); } template inline WwiseGTE::BSRational atan2(WwiseGTE::BSRational const& y, WwiseGTE::BSRational const& x) { return (WwiseGTE::BSRational)std::atan2((double)y, (double)x); } template inline WwiseGTE::BSRational ceil(WwiseGTE::BSRational const& x) { return (WwiseGTE::BSRational)std::ceil((double)x); } template inline WwiseGTE::BSRational cos(WwiseGTE::BSRational const& x) { return (WwiseGTE::BSRational)std::cos((double)x); } template inline WwiseGTE::BSRational cosh(WwiseGTE::BSRational const& x) { return (WwiseGTE::BSRational)std::cosh((double)x); } template inline WwiseGTE::BSRational exp(WwiseGTE::BSRational const& x) { return (WwiseGTE::BSRational)std::exp((double)x); } template inline WwiseGTE::BSRational exp2(WwiseGTE::BSRational const& x) { return (WwiseGTE::BSRational)std::exp2((double)x); } template inline WwiseGTE::BSRational fabs(WwiseGTE::BSRational const& x) { return (x.GetSign() >= 0 ? x : -x); } template inline WwiseGTE::BSRational floor(WwiseGTE::BSRational const& x) { return (WwiseGTE::BSRational)std::floor((double)x); } template inline WwiseGTE::BSRational fmod(WwiseGTE::BSRational const& x, WwiseGTE::BSRational const& y) { return (WwiseGTE::BSRational)std::fmod((double)x, (double)y); } template inline WwiseGTE::BSRational frexp(WwiseGTE::BSRational const& x, int* exponent) { WwiseGTE::BSRational result = x; auto& numer = result.GetNumerator(); auto& denom = result.GetDenominator(); int32_t e = numer.GetExponent() - denom.GetExponent(); numer.SetExponent(0); denom.SetExponent(0); int32_t saveSign = numer.GetSign(); numer.SetSign(1); if (numer >= denom) { ++e; numer.SetExponent(-1); } numer.SetSign(saveSign); *exponent = e; return result; } template inline WwiseGTE::BSRational ldexp(WwiseGTE::BSRational const& x, int exponent) { WwiseGTE::BSRational result = x; int biasedExponent = result.GetNumerator().GetBiasedExponent(); biasedExponent += exponent; result.GetNumerator().SetBiasedExponent(biasedExponent); return result; } template inline WwiseGTE::BSRational log(WwiseGTE::BSRational const& x) { return (WwiseGTE::BSRational)std::log((double)x); } template inline WwiseGTE::BSRational log2(WwiseGTE::BSRational const& x) { return (WwiseGTE::BSRational)std::log2((double)x); } template inline WwiseGTE::BSRational log10(WwiseGTE::BSRational const& x) { return (WwiseGTE::BSRational)std::log10((double)x); } template inline WwiseGTE::BSRational pow(WwiseGTE::BSRational const& x, WwiseGTE::BSRational const& y) { return (WwiseGTE::BSRational)std::pow((double)x, (double)y); } template inline WwiseGTE::BSRational sin(WwiseGTE::BSRational const& x) { return (WwiseGTE::BSRational)std::sin((double)x); } template inline WwiseGTE::BSRational sinh(WwiseGTE::BSRational const& x) { return (WwiseGTE::BSRational)std::sinh((double)x); } template inline WwiseGTE::BSRational sqrt(WwiseGTE::BSRational const& x) { return (WwiseGTE::BSRational)std::sqrt((double)x); } template inline WwiseGTE::BSRational tan(WwiseGTE::BSRational const& x) { return (WwiseGTE::BSRational)std::tan((double)x); } template inline WwiseGTE::BSRational tanh(WwiseGTE::BSRational const& x) { return (WwiseGTE::BSRational)std::tanh((double)x); } // Type trait that says BSRational is a signed type. template struct is_signed> : true_type {}; } namespace WwiseGTE { template inline BSRational atandivpi(BSRational const& x) { return (BSRational)atandivpi((double)x); } template inline BSRational atan2divpi(BSRational const& y, BSRational const& x) { return (BSRational)atan2divpi((double)y, (double)x); } template inline BSRational clamp(BSRational const& x, BSRational const& xmin, BSRational const& xmax) { return (BSRational)clamp((double)x, (double)xmin, (double)xmax); } template inline BSRational cospi(BSRational const& x) { return (BSRational)cospi((double)x); } template inline BSRational exp10(BSRational const& x) { return (BSRational)exp10((double)x); } template inline BSRational invsqrt(BSRational const& x) { return (BSRational)invsqrt((double)x); } template inline int isign(BSRational const& x) { return isign((double)x); } template inline BSRational saturate(BSRational const& x) { return (BSRational)saturate((double)x); } template inline BSRational sign(BSRational const& x) { return (BSRational)sign((double)x); } template inline BSRational sinpi(BSRational const& x) { return (BSRational)sinpi((double)x); } template inline BSRational sqr(BSRational const& x) { return (BSRational)sqr((double)x); } // See the comments in Math.h about traits is_arbitrary_precision // and has_division_operator. template struct is_arbitrary_precision_internal> : std::true_type {}; template struct has_division_operator_internal> : std::true_type {}; }