Design

This document is intended to describe design goals, invariants and implementation notes for the various types

SafeLong

The design goal of SafeLong is to provide worry-free arbitrary precision integers that nevertheless have performance approaching boxed Longs for calculations that remain within the range of a 64bit signed integer.

This is achieved by having two cases: SafeLongLong(x: Long) is used for numbers within the long range. SafeLongBigInt(x: BigInt) is used if this is not the case.

Invariants

Implementation notes

Operations of SafeLongBigInt use the underyling BigInt and create the appropriate kind of result depending on whether the result is a valid long.

Operations on SafeLongLong use the Checked macro to perform operations using long integers, and only fall back to using BigInt in case of numeric overflow.

Performance tips

Rational

The design goal of Rational is to provide good performance and low memory overhead in the very frequent case of rational numbers with small magnitude, while still being able to represent rational numbers of arbitrary size.

To achieve this goal, there are two different cases. LongRational(n: Long, d: Long) is used to represent small rational numbers. BigRational(n: BigInt, d: BigInt) is used whenever either numerator or denominator are too large to be stored in a LongRational.

Invariants

Rationals are always stored in a normalized form so that there is an unique representation for each number:

In addition to these invariants that are quite common in many rational implementations, there are additional invariants related to the usage of LongRational or BigRational:

When implementing operations for Rationals, it is important to make sure that the invariants are not violated. E.g. when performing an operation with two BigRational that results in a small number that can be represented in a LongRational, the result must be a LongRational.

Implementation notes

The implementation of BigRational is pretty straightforward. Usually, operations will be performed using SafeLong, and the result will be created using a builder method that takes a SafeLong for both numerator and denominator and produces the right kind of rational number given the invariants.

LongRational operations are a bit more complex: Basic operations use the Checked macro to try to perform the operation with just long integers, and only fall back to using SafeLong when there is a numeric overflow. The advantage of this approach is that there are no unnecessary object allocations in the very common case that there is no overflow.

Performance tips

The performance characteristics of rational operations are a bit different to normal integer or floating point operations.