chamalulu.Numerics.BigRational 1.0.0

chamalulu.Numerics.BigRational

BigRational provides an implementation of arbitrary precision rational numbers.

It implements INumber<BigRational> and IShiftOperators<BigRational, int, BigRational> to provide generic maths functionality.

A number is internally represented as a numerator and a denominator. They are of type BigInteger which allows for arbitrary precision integer numbers.

Quick Start

using chamalulu.Numerics;

var half = BigRational.Create(1, 2);
var third = BigRational.Create(1, 3);

var sum = half + third;           // 5/6
var product = half * third;       // 1/6
var reciprocal = !half;           // 2/1

// Canonicalize reducible values
var reducible = BigRational.Create(2, 4);
var canonical = reducible.ToCanonicalForm();  // 1/2

// Non-normal values
var nan = BigRational.NaN;
var inf = BigRational.PositiveInfinity;
var negInf = BigRational.NegativeInfinity;

Design Choices

BigRational models the extended real number line (including signed zero, infinities and NaN) as a value space, and takes deliberate positions where the convention in other numeric systems differs from mathematical rigor.

Signed zero and infinities

+0 and -0 are distinct representations but compare equal. Infinities (+∞ and -∞) are produced by division by zero and propagate through arithmetic following the IEEE 754 pattern. See Value Representation.

NaN as the default value

default(BigRational) is NaN, not zero. This is a consequence of the value-space encoding where (0, 0) maps to NaN. Consumers should use the static Zero or NegativeZero fields instead. See NaN.

! operator and Reciprocal

The unary ! operator returns the reciprocal of a value, not logical negation. The named method Reciprocal(BigRational) is the canonical implementation. See Unary operator ! / Reciprocal.

>>> operator and ReduceByPowerOfTwo

The >>> operator is repurposed to reduce a value by a factor of $2^c$, rather than performing an unsigned bit shift (which has no meaningful interpretation for rational numbers). The named method ReduceByPowerOfTwo(BigRational, int) is the canonical implementation. See ReduceByPowerOfTwo / Reduce by $2^c$ (>>>).

Pow(x, 0) = 1 for all inputs

The zero exponent returns One for all inputs, including NaN, ±0 and ±∞. This follows the IEEE 754 / Math.Pow convention — the mathematically indeterminate limits ($0^0$, $\infty^0$) are absorbed for practical consistency. See Pow.

Classification helpers

The public helpers IsRealNumber and IsComplexNumber use strict mathematical definitions (normal values only). The INumberBase<BigRational> interface implementations follow the broader .NET convention (infinities count as real). Generic code operating through the interface gets cross-type consistency; direct callers get the precise answer.

Value Representation

The complete value space of BigRational and its corresponding semantic value is covered by the following table.

	$n<0$	$n=0$	$n>0$
$d<0$	$\frac{n}{d}$	$-0$	$\frac{n}{d}$
$d=0$	$-\infty$	$NaN$	$+\infty$
$d>0$	$\frac{n}{d}$	$+0$	$\frac{n}{d}$

The first and third rows, where $d \ne 0$, represent normal numbers.
The second row, where $d = 0$, represents non-normal numbers.

Infinities

There are two infinities, positive and negative. These semantically match the infinities of IEEE 754 floating point numbers.

NaN

There is only one representation of NaN. The representation of NaNs in IEEE 754 floating point numbers is wider but ISA dependent and not very well-documented. BigRational does not bother preserving NaN signaling and payload.

Canonical Forms

The values $\frac{n}{d}$, $\pm0$ and $\pm\infty$ have multiple representations in the value space. Their canonical representations are as follows:

$-\infty$ : $(n=-1)\land(d=0)$

$-0$ : $(n=0)\land(d=-1)$

$\frac{n}{d}$ : $(n\perp d)\land(d\in\mathbb{N}_1)$

$+0$ : $(n=0)\land(d=1)$

$+\infty$ : $(n=1)\land(d=0)$

ToCanonicalForm

ToCanonicalForm() reduces a value to its canonical form.

A normal non-zero value can be known to be irreducible or not. If the value is known to be irreducible, this method returns the value as is. This is an $\mathcal{O}(1)$ operation. Otherwise, the method calculates the canonical form of the value.

Calculating the canonical form of a possibly reducible normal non-zero value is an $\mathcal{O}(n^2)$ or $\mathcal{O}(T(n)\log n)$ operation, where $T(n)$ is the time complexity of BigInteger multiplication.

For non-normal or zero numbers this is also an $\mathcal{O}(1)$ operation.

Reducibility

Values can be reducible or irreducible. For most normal numbers, the computation of reducibility can be computationally expensive. As such, normal non-zero values known to be irreducible are internally represented with a positive denominator. Normal non-zero values where reducibility is unknown are internally represented with a negative denominator.

Reducibility is defined as follows:

$$\frac{0}{-1}\text{ is irreducible}$$

$$\frac{n}{d}\text{ is reducible}\iff \exists x\in\mathbb{Z}\setminus\lbrace0,1\rbrace:(x|n)\land(x|d)\land\left(\frac{d}{x}\geq0\right)$$

By this definition the canonical form of any value, including $NaN$, is irreducible. The special case of $-0$ being irreducible by definition is necessary because reducing it by $-1$ would change its sign.

Construction

Numbers are naturally constructed by performing operations on other numbers. There is also a factory method, Create, for creating normal numbers.

Create

Create(BigInteger numerator, BigInteger denominator) takes a numerator and a denominator and creates a normal number. It does not accept a zero denominator. It accepts negative denominators and preserves the sign of the number but may flip numerator and denominator signs to indicate known reducibility.

Static Fields

Zero

Canonical $+0$. Also, the returned value from the properties INumberBase<BigRational>.Zero and IAdditiveIdentity<BigRational, BigRational>.AdditiveIdentity.

NegativeZero

Canonical $-0$.

One

Canonical $1$. Also, the returned value from the properties INumberBase<BigRational>.One and IMultiplicativeIdentity<BigRational, BigRational>.MultiplicativeIdentity.

NaN

$NaN$, a value which is not a representable number. This is the default value of BigRational. It has only one representation.

PositiveInfinity

Canonical $+\infty$.

NegativeInfinity

Canonical $-\infty$.

Arithmetics

Binary operator +

Addition is defined according to the table for floating point addition in 12.10.5 Addition operator. The adjoining description of overflow is not applicable to BigRational since its magnitude and precision is only limited by the available memory.

Binary operator -

Subtraction is implemented by adding the left operand to the negation of the right operand, $x-y=x+(-y)$.

Binary operator *

Multiplication is defined according to the table for floating point multiplication in 12.10.2 Multiplication operator. The adjoining description of representable magnitude and rounding is not applicable to BigRational since its magnitude and precision is only limited by the available memory.

Binary operator /

Division is implemented by multiplying the left operand by the reciprocal of the right operand, $\frac{x}{y}=x\frac{1}{y}$.

Binary operator %

Remainder is defined according to the table for floating point remainder in 12.10.4 Remainder operator.

Unary operator +

Returns the value as is.

Unary operator -

Returns the negation of the value.

Unary operator ++

Increases the value by one. For normal numbers $\frac{n}{d}$, $\frac{n+d}{d}$ is returned.

Unary operator --

Decreases a value by one. For normal numbers $\frac{n}{d}$, $\frac{n-d}{d}$ is returned.

Unary operator ! / Reciprocal

Reciprocal(BigRational value) returns the reciprocal of a value. The unary ! operator provides the same operation as a shorthand.

Note that this operator does not return the logical negation of the value, whatever that would mean, but rather the reciprocal. I think it's a common enough operation to warrant its own operator, but the set of overloadable operators in C# is quite sparse.

Pow

Pow(BigRational value, int exponent) raises a value to an integral power.

Negative exponents return the reciprocal power.

The zero exponent returns $1$ for all inputs, including $NaN$, $\pm0$, and $\pm\infty$. This follows the IEEE 754 / Math.Pow convention: the constant function $f(x) = x^0$ has a removable singularity at $x = 0$, and treating it uniformly as $1$ avoids surprising base cases in algorithms that use Pow(x, 0) as a terminal case (e.g. polynomial evaluation, exponentiation by squaring). The mathematically indeterminate limits $0^0$, $\infty^0$ and $NaN^0$ are absorbed into this convention for practical consistency.

For even exponents, sign information of zero and infinity values is lost:

Input	Positive exponent	Negative exponent
$+0$	$+0$	$+\infty$
$-0$	$+0$	$+\infty$
$+\infty$	$+\infty$	$+0$
$-\infty$	$+\infty$	$+0$

For odd exponents, the sign of zero and infinity values is preserved:

Input	Positive exponent	Negative exponent
$+0$	$+0$	$+\infty$
$-0$	$-0$	$-\infty$
$+\infty$	$+\infty$	$+0$
$-\infty$	$-\infty$	$-0$

Log

Log(BigRational value) computes the natural logarithm of the value. The natural logarithm is defined according to the following table where $n$ and $d$ are positive integers:

Value	Result
$\frac{n}{d}$	$\ln{n}-\ln{d}$
$+0$	$-\infty$
$\frac{-n}{-d}$	$\ln{(-n)}-\ln{(-d)}$
$+\infty$	$+\infty$
otherwise	$NaN$

Note that this method uses BigInteger.Log(BigInteger) and, as such, returns a double approximation of $\ln{\frac{n}{d}}$.

Log(BigRational value, double baseValue) computes the base $x$ logarithm of the value. The base $x$ logarithm is defined according to the following table where $n$ and $d$ are positive integers:

Value	Result
$\frac{n}{d}$	$\log_x{n}-\log_x{d}$
$+0$	$-\infty$
$\frac{-n}{-d}$	$\log_x{(-n)}-\log_x{(-d)}$
$+\infty$	$+\infty$
otherwise	$NaN$

Note that this method uses BigInteger.Log(BigInteger, double) and, as such, returns a double approximation of $\log_x{\frac{n}{d}}$.

Log10(BigRational value) computes the decimal logarithm of the value. The decimal logarithm is defined according to the following table where $n$ and $d$ are positive integers:

Value	Result
$\frac{n}{d}$	$\log_{10}{n}-\log_{10}{d}$
$+0$	$-\infty$
$\frac{-n}{-d}$	$\log_{10}{(-n)}-\log_{10}{(-d)}$
$+\infty$	$+\infty$
otherwise	$NaN$

Note that this method uses BigInteger.Log10(BigInteger) and, as such, returns a double approximation of $\log_{10}{\frac{n}{d}}$.

Log2(BigRational value) computes the integer binary logarithm of the value. The integer binary logarithm is defined according to the following table where $n$ and $d$ are positive integers:

Value	Result
$\frac{n}{d}$	$\lfloor\log_2{n}\rfloor-\lfloor\log_2{d}\rfloor$
$+0$	$-\infty$
$\frac{-n}{-d}$	$\lfloor\log_2{(-n)}\rfloor-\lfloor\log_2{(-d)}\rfloor$
$+\infty$	$+\infty$
otherwise	$NaN$

Note that this method uses BigInteger.Log2(BigInteger) and, as such, returns an integer approximation of $\log_2{\frac{n}{d}}$. The error of the approximation is doubled by subtracting the integer logarithms of the numerator and the denominator. If this is problematic, use Log(BigRational value, double baseValue) with base $2$.

Calculations

Iterative calculations (ArcCot, Pi, Sqrt) and the continued fraction bridge methods (ContinuedFractionCoefficients, Convergents) have moved to the chamalulu.Numerics.Calculations package. See the Calculations README for API documentation.

Comparisons

Normal numbers are compared by value. $+0$ and $-0$ are considered equal in this regard. If any comparand is non-normal, the comparison logic of double is followed.

The hash code is based on the canonical form of the number. It is guaranteed to be equal for all forms of the value considered equal, including $\pm0$. This requires that the canonical form is calculated upon invocation. This calculation can be costly for values which are not known to be irreducible. If you need to amortize the cost of this calculation, e.g., when storing many values in a set or dictionary, consider storing only values in their canonical form.

Conversions

Implicit cast operators are implemented from decimal, double, BigInteger, int, uint, long and ulong to BigRational. These casts are lossless. Roundtripping to BigRational and back will result in the same value with some caveats. Scale of decimal may not be preserved, although the value is the same. IEEE754 $sNaN$ and $qNaN$, which are not differentiated in dotnet anyway, are just $NaN$.

Regular explicit and checked explicit cast operators are implemented from BigRational to decimal, double, BigInteger, int, uint, long and ulong. These casts are generally lossy. Regular explicit casts are truncating and don't throw exceptions. Checked explicit casts throw OverflowException if the value is outside the range of the target type.

INumberBase<BigRational>.TryConvertFrom(Checked|Saturating|Truncating)<TOther>(TOther value, out BigRational result) are implemented. If TOther is one of BigInteger, double or decimal, the implicit cast is used. If TOther implements IFloatingPoint<TOther>, conversion via double or BigInteger is tried in that order. For any other type, conversion via BigInteger or double is tried in that order. For details, see TryConvertFromHelper source in TryConvert.cs.

INumberBase<BigRational>.TryConvertTo(Checked|Saturating|Truncating)<TOther>(BigRational value, out TOther result) are implemented. For normal non-zero values conversion of numerator and denominator to TOther is first tried and their quotient is returned. If that fails, conversion via double or decimal is tried in that order. For zeros or non-normal values, conversion via double is tried. For details, see TryConvertToHelper source in TryConvert.cs.

Formatting

TryFormat and overloads of ToString serialize a BigRational to a Span<char> or string respectively. Non-zero normal numbers are represented as "numerator/denominator" with normalized sign handled for the fraction as a whole. Zero or non-normal numbers are delegated to the formatting of double.

Format string and format provider are respected, including all documented cases of NumberNegativePattern.

Parsing

Overloads of TryParse and Parse deserialize a ReadOnlySpan<char> or string to a BigRational. Sign in the form of parentheses, leading or trailing sign is parsed first. Then, attempts to parse the fraction of the form "numerator/denominator", decimal number and non-normal number are performed in that order.

Number styles and format provider are respected. Currency symbols, hexadecimal specifiers, and binary specifiers are not allowed.

Shift Operators

Left shift

Left shift, << (x86: SHL/SAL), is implemented. The shift amount is interpreted similarly as for binary integers. I.e., the shift amount is first truncated to an unsigned 31-bit integer.

The denominator is shifted right as many trailing zero bits it contains or the shift amount, whichever is greatest. The numerator is shifted left the remaining bits of shift amount, if any.

Right shift

Right shift, >> (x86: SAR), is implemented. The shift amount is interpreted similarly as for binary integers. I.e., the shift amount is first truncated to an unsigned 31-bit integer.

The numerator is shifted right as many trailing zero bits it contains or the shift amount, whichever is greatest. The denominator is shifted left the remaining bits of shift amount, if any.

ReduceByPowerOfTwo / Reduce by $2^c$ (>>>)

ReduceByPowerOfTwo(BigRational value, int shiftAmount) reduces a value by a factor of $2^c$. The >>> operator provides the same operation as a shorthand.

The distinction between SHR/SAR is not relevant for BigRational, so the >>> operator is repurposed for this.

Unsigned right shift (x86: SHR) is not implemented.

The >>> operator shifts both numerator and denominator to the right by the given amount, I.e., the operator shifts both numerator and denominator to the right by the given amount, effectively reducing the value by a factor of $2^c$ where $c$ is shift amount. The shift amount is interpreted similarly as for binary integers. I.e., the shift amount is first truncated to an unsigned 31-bit integer.

This operator will not shift out the most significant bit of either the numerator or denominator. Thus, $\pm\infty$, $\pm1$ and $\pm0$ will remain unchanged, and the result will not be $NaN$ except when the value is $NaN$.

If the numerator and denominator have as many or more than shift amount common factors of $2$ the result will remain unchanged.

$$(2^c|n)\land(2^c|d)\implies\left(\frac{n}{d}\ \mathbin{>>>}\ c\right)=\frac{n}{d}$$

Otherwise, for $c>0$, the result will lose precision.

If the magnitude of the value is greater than or equal to $2$, the magnitude of the result will tend towards infinity.

$$2\leq\frac{n}{d}\implies\lim_{c\to\infty}\left(\frac{n}{d}\ \mathbin{>>>}\ c\right)=+\infty$$ $$\frac{n}{d}\leq-2\implies\lim_{c\to\infty}\left(\frac{n}{d}\ \mathbin{>>>}\ c\right)=-\infty$$

If the magnitude of the value is greater than $1$, the magnitude of the value will tend towards $1$.

$$1<\frac{n}{d}<2\implies\lim_{c\to\infty}\left(\frac{n}{d}\ \mathbin{>>>}\ c\right)=1$$ $$-2<\frac{n}{d}<-1\implies\lim_{c\to\infty}\left(\frac{n}{d}\ \mathbin{>>>}\ c\right)=-1$$

If the magnitude of the value is equal to $1$, the result will remain unchanged.

$$\frac{n}{d}=1\implies\left(\frac{n}{d}\ \mathbin{>>>}\ c\right)=1$$ $$\frac{n}{d}=-1\implies\left(\frac{n}{d}\ \mathbin{>>>}\ c\right)=-1$$

If the magnitude of the value is less than $1$, the magnitude of the value will tend towards $0$.

$$0<\frac{n}{d}<1\implies\lim_{c\to\infty}\left(\frac{n}{d}\ \mathbin{>>>}\ c\right)=+0$$ $$-1<\frac{n}{d}<0\implies\lim_{c\to\infty}\left(\frac{n}{d}\ \mathbin{>>>}\ c\right)=-0$$