search

binkley / kotlin-rational

An immutable, infinite-precision Rational (ratio, fraction) class for Kotlin
The Unlicense
12 stars 2 forks source link

readme

<img src="./images/public-domain.svg" alt="Public Domain" align="right" width="20%" height="auto"/>

Kotlin Rational

build coverage pull requests issues vulnerabilities license

Immutable, infinite-precision FixedBigRational and FloatingBigRational (ratio, fraction) classes for Kotlin, that is ℚ (quotient), akin to BigInteger (ℤ) and BigDecimal (ℝ, but not really: actually infinite-precision decimals [base 10]) in the JDK.

The library has two main forms of expressing rational numbers on the JDK, FixedBigRational and FloatingBigRational, providing finite and pseudo-IEEE 754 versions, respectively.

DISCLAIMER
This code has not been vetted by a numerical analyst in the ways that the JDK's BigDecimal or BigDecimal have been. For example, sqrt behaves poorly for extrema. It is a pleasure project, not a reviewed library.

The build is obsessive. The author uses this library to explore better ways for building locally, and building in CI with GitHub: the goal of the build is to discover issues before they impact others; the goal of the code is to represent rationals on the JVM in a sensible fashion.

This code is a "finger exercise", trying out Kotlin operator overloading and extension methods, and writing clean, clear, concise Kotlin. (If you find the Kotlin API unclear, please file a PR. What is clear to the author may not be clear to others.) It also explores the impact of NaN as a value for FloatingBigRational (FixedBigRational treats these circumstances by raising exceptions). This code prefers readability and expressiveness to performance.

A secondary goal is to model the Kotlin standard library, and Java's BigDecimal and BigInteger types, as well as Number (an implementation base class in the JDK for numeric types).

Build and try

To build, use ./mvnw clean verify. Try ./run for a demonstration.

To build as CI would, use ./batect build. Try ./batect run for a demonstration as CI would.

This project assumes JDK 17. There are no run-time dependencies beyond the Kotlin standard library.

This code builds and passes tests and checks on JDK 11-17.

TOC

Releases

NB — public releases are on hold pending selection and setup of a public repository.

Use

Examples

See these examples:

Gradle

This snippet uses Kotlin syntax for the build script:

repositories {
    maven {
        url = uri("https://dl.bFixedray.com/binkley/maven")
    }
}

dependencies {
    implementation("hm.binkley:kotlin-rational:2.0.1")
}

Maven

This snippet is an elided pom.xml:


<project>
    <dependencies>
        <dependency>
            <groupId>hm.binkley</groupId>
            <artifactId>kotlin-rational</artifactId>
            <version>2.0.1</version>
        </dependency>
    </dependencies>

    <repositories>
        <repository>
            <snapshots>
                <enabled>false</enabled>
            </snapshots>
            <id>bFixedray-binkley-maven</id>
            <name>bFixedray</name>
            <url>https://dl.bFixedray.com/binkley/maven</url>
        </repository>
    </repositories>
</project>

Caveats

Publishing open source projects has become more challenging with the demise of JCenter. An alternative like GitHub packages has its own challenges. For now, JitPack is usable though with drawbacks.

To use JitPack, change the Maven coordinates for this project to: com.github.binkley:kotlin-rational:kotlin-rational-2.1.1. Note the version is a git tag, not the actual version.

And add a repository declaration:


<repositories>
    <repository>
        <id>jitpack.io</id>
        <url>https://jitpack.io</url>
    </repository>
</repositories>

See kunits for a small if whimsical example of a library using kotlin-rational with the JitPack repository.

API

In general, when properties, methods, and operations do not have documentation, they behave similarly as their floating-point counterpart. In general, follow the lead of BigDecimal and BigInteger, and add features when sensible from popular math libraries, such as F77.

These are algebraic Fields with supporting overloaded operators and manifest constants:

Public functions and types follow Kotlin's explicit API in strict mode.

Constructors and factories

All constructors are private in the API. Please use:

After experiments with alternative infix operators, for example, "2 ⁄ 1" with the UNICODE fraction slash, or the various UNICODE forms of the solidus, the English way to pronounce fractions, ie, "two over one" was found to be the most clear.

Pretty printing

Rationals print (toString) using the fraction slash:

"$nearPi" // evaluates to "22⁄7"

To leverage UNICODE for particular rationals, use the display property (which falls back to toString if there is no specific UNICOCE character):

(1 over 2).display // evaluates to "½"

Properties

Methods

Operators

Types

This code attempts to ease programmer typing through overloading. Where sensible, if a FixedBigRational and FloatingBigRational are provided as argument or extension method types, then so are BigDecimal, Double, Float, BigInteger, Long, and Int.

FixedBigRational and FloatingBigRational are both of type JDK Number and Comparable. The exception:

Build

Use ./mvnw (Maven) or ./batect build (Batect) to build, run tests, and create a demo program. Use ./run or ./batect run to run the demo.

Batect works "out of the box". However, an important optimization is to avoid re-downloading plugins and dependencies from within a Docker container.

This shares Maven plugin and dependency downloads with the Docker container run by Batect.

Maintenance

Type aliases

Use type aliases when sensible:

Formatting

When providing two versions of reflexive functions, please keep them together in this order:

fun ReceiverType.func(arg: ArgumentType)
fun ArgumentType.func(receiver: ReceiverType)

When providing function overloads, please include these types as applicable, and keep them together in this order:

When providing function overloads for complex or imaginary types, please include these types as applicable, and keep them together in this order:

Standard notation is "2+3i" (2+3.i) rather than "3i+2" (3.i+2). Example: extension functions for the plus operator in this order ("real" comes first):

operator fun Int.plus(imag: FixedBigImaginary): FixedBigComplex =
    toBigRational() + imag

operator fun FixedBigImaginary.plus(real: Int): FixedBigComplex =
    real + this

Improper ordering is supported for calculations such as "a + b" where either "a" or "b" could be pure imaginary numbers. There is no proper order for adding real numbers to complex numbers. For consistency, code should provide the real value first in extension functions (the this receiver) followed by inverting this and the non-real function parameter.

Design choices

Two choices

This code provides FixedBigRational and FloatingBigRational. They differ by:

FloatingBigRational
An approximation of IEEE 754 behaviors, with NaN, POSITIVE_INFINITY, and NEGATIVE_INFINITY
FixedBigRational
A more mathematically correct representation, but raises ArithmeticException for operations requiring IEEE 754 behaviors

Note that floating point negative zero is mapped to rational unsigned zero.

Sources

These were great help:

The code for FloatingBigRational extends ℚ, the field of rational numbers, with division by zero, "not a number", -∞, and +∞, following the lead of IEEE 754, and using the affinely extended real line as a model. However, this code does not consider +0 or -0, treating all zeros as 0, and distinguishes +∞ from -∞ (as opposed to the projectively extended real line). As a result FloatingBigRational does not represent a proper Field.

The code for FixedBigRational, however, should simply be ℚ, and raises ArithmeticException when encountering impossible circumstances; hence, it is a Field when not raising exceptions.

Prefer readability

This code prefers more readable code over harder-to-read, but more performant code (often though, more readable is also more performant).

Always proper form

This code always keeps rationals in proper form (lowest terms):

  1. The numerator and denominator are coprime
  2. The denominator is positive exception the next point
  3. For FloatingBigRational, the denominator is 0 for three special cases: NaN ("0 / 0"), POSITIVE_INFINITY ("1 / 0") and NEGATIVE_INFINITY ("-1 / 0")

One may conclude that FixedBigRational is a Field under addition and multiplication, and FloatingBigRational is not.

Representation of not a number and infinities

This section applies only to FloatingBigRational, and not to FixedBigRational. See Division by 0, infinities for discussion.

FloatingBigRational represents certain special cases via implied division by zero:

Preserving standard IEEE 754 understandings:

Hence, NaN.denominator, POSITIVE_INFINITY.denominator, and NEGATIVE_INFINITY.denominator all return zero.

Division by an infinity is 0, as is the reciprocal of an infinity. FloatingBigRational does not have a concept of infinitesimals ("ϵ or δ"). (See Infinitesimal for discussion.)

Single concept of zero

In this code there is only ZERO (0). There are no positive or negative zeros to represent approaching zero from different directions.

FixedBigRational and FloatingBigRational are Numbers

FixedBigRational and FloatingBigRational are a kotlin.Number to implement Kotlin handling of numeric types. However, in this the Kotlin stdlib API errs: it requires a conversion to Char unlike the Java equivalent. One consequence: this code raises UnsupportedOperationException for conversion to and from Character in all cases. This conversion seemed perverse, eg, to what language character should 3/5 convert?

This code supports conversion among Double and Float, and FixedBigRational and FloatingBigRational for all finite values, and non-finite values for FloatingBigRational. The conversion is exact: it constructs a power-of-2 rational value following IEEE 754; so reconverting returns the original floating-point value, and for FloatingBigRational converts non-finite values to their corresponding values (for FixedBigRational this raises ArithmeticException).

floating-point FloatingBigRational FixedBigRational
0.0 ZERO ZERO
NaN NaN Raises exception
POSITIVE_INFINITY POSITIVE_INFINITY Raises exception
NEGATIVE_INFINITY NEGATIVE_INFINITY Raises exception

When narrowing types, conversion may lose magnitude, precision, and/or sign (there is no overflow/underflow). This code adopts the behavior of BigDecimal and BigInteger for narrowing.

Division by 0, infinities

There are two ways to handle division by 0:

For FloatingBigRational, as with floating-point, NaN != NaN, and finite values equal themselves. As with mathematics, infinities are not equal to themselves, so POSITIVE_INFINITY != POSITIVE_INFINTY and NEGATIVE_INFINITY != NEGATIVE_INFINITY. (FloatingBigRational does not provide the needed sense of equivalence, nor does it cope with infinitesimals

FloatingBigRational represents infinities as division by 0 (positive infinity reduces to 1 / 0, negative infinity to -1 / 0). The field of rationals (ℚ) is complex (in the sense of "difficult") when considering infinities.

Infix constructor FloatingBigRational FixedBigRational
0 over 1 ZERO ZERO
0 over 0 NaN Raises exception
1 over 0 POSITIVE_INFINITY Raises exception
-1 over 0 NEGATIVE_INFINITY Raises exception

Conversions and operators

This code provides conversions (toBigRational and ilk) and operator overloads for these Number types:

In addition, there is conversion to and from FixedContinuedFraction and FloatingContinuedFraction, respectively.

Adding support for Short and Byte is straight-forward, but I did not consider it worthwhile without more outside input. As discussed, support for Character does not make sense (and it is unfortunate Java's java.lang.Number—which kotlin.Number models—includes this conversion.)

Note that toBigDecimal(limitPlaces, roundingMode) defaults to FLOOR rounding when truncating decimal places.

Sorting

All values sort in the natural mathematical sense, excepting that with FloatingBigRational, NaN sorts to the position where Double.NaN would sort, regardless of other values. There is no sense of natural order for NaN, so this code chooses to sort NaN the same as does Double, or, to the end.

For FloatingBigRational, all NaN are "quiet"; none are "signaling", including sorting. This follows the Java convention for floating-point, and is a complex area. (See NaN.)

Implementation choices

Always keep in lowest terms

(See Always proper form.)

The code assumes rationals are in lowest terms (proper form). The valueOf factory method ensures this. However, you should usually use the over infix operator instead, eg, 1 over 2 or 2 over 1.

Negative values

The canonical form of negative values for rational numbers depends on context. For this code, the denominator is always non-negative, and for values with absoluteValue < 0, the numerator is negative.

Identity of constants

Rather than check numerator and denominator throughout for special values, this code relies on the factory constructor (valueOf) to produce known constants, and relevant code checks for those constants.

See:

Factory constructor

Rather than provide a public constructor, always use the over infix operator or valueOf factory method. This maintains invariants such as "lowest terms" (numerator and denominator are coprime), sign handling, and reuse of special case objects.

Special case handling vs sealed class

This code uses special case handling for non-finite values. An alternative would be to use a sealed class with separate subclasses for special cases. This would potentially provide handling of infinitesimals; however, this abstraction bleeds between subclasses. It is unclear if a sealed class makes the code clearer.

Avoid duplication

One of the implementation choices was to share common code between FixedBigRational and FloatingBigRational as much as possible. To do this in Kotlin, these types extend a common base class, BigRationalBase and either member functions, or extension functions on a generic type.

More interesting is avoiding duplication of class-level properties (constants) and functions while retaining subtype-specific behavior. An example is a constant like ONE or a shared factory method like valueOf. An example of subtype-specific behavior is that FloatingBigDecimal.valueOf produces NaN for a rational like 1 over 0, but FixedBigRational.valueOf raises an ArithmeticException.

To avoid duplication for class-level features, the companion objects for FixedBigRational and FloatingBigRational extend BigRationalCompanion. That companion objects are full types and can extend base classes and implement interfaces is an underappreciated feature of Kotlin.

GCD vs LCM

There are several places that might use LCM (eg, dividing rationals). This code relies on the factory constructor (valueOf) for GCM in reducing rationals to proper form, and gcm and lcm methods are recursive between themselves.

[!NOTE] This code implements GCD and LCM recursively in terms of each other.

Continued fractions

This code uses a separate class for representation of rationals as continued fractions, FixedContinuedFraction and FloatingContinuedFraction. This becomes more complex for FloatingBigRational when dealing with NaN and the infinities.

The representation is for finite simple continued fractions, that is:

  1. The numerator is always 1
  2. There are a finite number of terms

Restriction 1 would need to be loosened to accommodate using continued fractions for computing square roots of rationals. A function signature might look like FixedBigRational.sqrt(n: Int): FixedContinuedFraction to do so.

Algebra

Though not strictly required for the code or implementation, this project uses interfaces for applicable abstract algebra concepts: Monoid (+ and 0), Group (-), Ring (* and 1), and Field (/). This is an indulgence.

These also provide simple demonstration of Kotlin companion objects as themselves a type hierarchy mirroring hierarchy of types the companions go with.

Further reading