User Manual

Introduction

The Compositional Numeric Library (CNL) is a C++ library of fixed-precision numeric classes which enhance integers to deliver safer, simpler, cheaper arithmetic types.

CNL improves on numbers the same way that the STL improves on arrays and smart pointers improve on pointers.

Uses include

• simulations that rely on precision, determinism, and predictability,
• financial applications handling decimal fractions and
• resource-critical systems where floating-point arithmetic is too costly.

The CNL project is published under the Boost licence and can be found online at github.com/johnmcfarlane/cnl.

Components

Core Components

The core numeric types of CNL are:

• scaled_integer - scales integers by any exponent and base with zero-overhead and minimal precision loss;
• elastic_integer - prevents overflow at compile-time by generalizing promotion rules;
• overflow_integer - handles integer overflow at runtime;
• rounding_integer - improves rounding behavior of integers;
• wide_integer - provides integers wider than 64 and 128 bits using multi-word arithmetic;
• fraction - low-level dividend/divisor pair aids refined division handling and
• constant - a numerics-friendly alternative to std::integral_constant.

Each of these types solves a single problem when used alone.

Composite Types

In combination, the core types produce composites which address multiple concerns.

Provided composite types include:

• elastic_scaled_integer (scaled_integer and elastic_integer) - real-number approximation which uses promotion to avoid overflow;
• static_integer (rounding_integer, overflow_integer, elastic_integer and wide_integer) - fully-featured safe, accurate integer type and
• static_number (scaled_integer and static_integer) - a fully-featured safe, accurate real number approximation.

Many more combinations are possible. For example:

• safe_integer (overflow_integer and elastic_integer);
• wide_elastic_integer (elastic_integer and wide_integer) and
• safe_fraction (fraction and safe_integer).

Examples

The following examples can be found in the test suite.

Declaration

The scaled_integer type adds a scaling exponent to integers. This enables the integer to represent very big or very small values.

#include <cnl/all.h>
#include <iostream>
 
using cnl::power;
using cnl::scaled_integer;
using namespace std;
 
void declaration_example()
{
    // x is represented by an int and scaled down by 1 bit
    auto x = scaled_integer<int, power<-1>>{3.5};
 
    // under the hood, x stores a whole number
    cout << to_rep(x) << endl;  // "7"
 
    // but it multiplies that whole number by 2^-1 to produce a real number
    cout << x << endl;  // "3.5"
 
    // like an int, x has limited precision
    x /= 2;
    cout << x << endl;  // "1.5"
}

Arithmetic Operators

Specializations of scaled_integer behave a lot like native C/C++ numeric types. Operators are designed to behave in an way which is both predictable and efficient.

void basic_arithmetic_example()
{
    // define a constant signed value with 3 integer and 28 fraction bits (s3:28)
    auto pi = scaled_integer<int32_t, power<-28>>{3.1415926535};
 
    // expressions involving integers return scaled_integer results
    auto tau = pi * 2;
    static_assert(is_same<decltype(tau), scaled_integer<int32_t, power<-28>>>::value);
 
    // "6.28319"
    cout << tau << endl;
 
    // expressions involving floating-point values return floating-point results
    auto degrees = tau * (180 / 3.1415926534);
    static_assert(is_same<decltype(degrees), double>::value);
 
    // "360"
    cout << degrees << '\n';
}

Arithmetic Functions

But one size does not fit all. Different applications of the same operation might call for different trade-offs between storage, precision, safety and speed. Named functions provide fine-tuned control over arithmetic results.

using cnl::elastic_scaled_integer;
 
void advanced_arithmetic_example()
{
    // this variable uses all of its capacity
    auto x = scaled_integer<uint8_t, power<-4>>{15.9375};
 
    // 15.9375 * 15.9375 = 254.00390625 ... overflow!
    auto xx1 = scaled_integer<uint8_t, power<-4>>{x * x};
    cout << xx1 << endl;  // "14" instead!
 
    // fixed-point multiplication operator obeys usual promotion and implicit conversion rules
    auto xx = x * x;
 
    // x*x is promoted to scaled_integer<int, -8>
    static_assert(is_same<decltype(xx), scaled_integer<int, power<-8>>>::value);
    cout << xx << endl;  // "254.00390625" - correct
 
    // you can avoid the pitfalls of integer promotion for good by using the elastic_scaled_integer
    // type
    auto named_xx = make_elastic_scaled_integer(x) * make_elastic_scaled_integer(x);
 
    // this type tracks both the number of digits and the exponent to ensure lossless multiplication
    static_assert(is_same<decltype(named_xx), elastic_scaled_integer<16, power<-8>, unsigned>>::value);
    cout << named_xx << endl;  // "254.00390625" - also correct but prone to overflow
}

Extensible

Because one size does not fit all, scaled_integer is designed to make it easy to tailor new arithmetic types. The elastic_scaled_integer type illustrates this. As each calculation requires more digits, so the results of elastic_scaled_integer operations allocate more storage.

using cnl::elastic_integer;
 
void elastic_example1()
{
    // Consider an integer type which keeps count of the bits that it uses.
    auto a = elastic_integer<6, int8_t>{63};
 
    // Results of its operations widen as required.
    [[maybe_unused]] auto aa = a * a;
    static_assert(is_same<decltype(aa), elastic_integer<12, int8_t>>::value);
 
    // Obviously, this type no longer fits in a byte.
    static_assert(sizeof(aa) == 2);
 
    // Addition requires smaller results.
    [[maybe_unused]] auto a2 = a + a;
    static_assert(is_same<decltype(a2), elastic_integer<7, int8_t>>::value);
}
 
using cnl::elastic_scaled_integer;
 
void elastic_example2()
{
    // A type such as elastic_integer can be used to specialize scaled_integer.
    // Now arithmetic operations are more efficient and less error-prone.
    auto b = elastic_scaled_integer<31, power<-27>, unsigned>{15.9375};
    auto bb = b * b;
 
    cout << bb << endl;  // "254.00390625"
    static_assert(is_same<decltype(bb), elastic_scaled_integer<62, power<-54>, unsigned>>::value);
}

FAQ

Fixed-point Overflow

Q: Why do calculations using cnl::scaled_integer result in completely wrong results?

A: Most surprises reported by CNL users occur when a cnl::scaled_integer value exceeds the range that its type can represent. This is normally caused by arithmetic operations (especially multiplication) and from conversion between different scales. It typically results in 'modulo' or overflow behavior.

Consider the multiplication of 1*1. What could possibly go wrong?

void overflow_example1()
{
    // fixed-point value of 65,536 * 2^-16
    auto num = cnl::scaled_integer<int, cnl::power<-16>>{1};
 
    // fixed-point value of 4,294,967,296 * 2^-32
    auto square = num * num;
 
    std::cout << square;
}

cnl::scaled_integer does nothing more here than perform integer multiplication. But the product is too great to be stored in an int (on a typical system). Here is the equivalent operation being performed directly on the int:

void overflow_example2()
{
    // integer variable with value 65,536
    auto num = 65536;
 
    // integer variable with value 4,294,967,296
    auto square = num * num;
 
    std::cout << square;
}

This value is too great to be stored in a 32-bit integer. In both cases overflow will occur and the result will not be valid.

Q: Why do calculations using cnl::scaled_integer result in a static_assert error?

Errors with the message "attempted operation will result in overflow" may be the result of conversion between types whose ranges do not intersect as described above. For example, when converting from a 32-bit cnl::scaled_integer to a 64-bit cnl::scaled_integer, you may find that the 32-bit number is being scaled up or down by 32 bits before being converted to 64-bits. This would result in overflow. Read on for suggested solutions...

Q: Why doesn't cnl::scaled_integer prevent/avoid/detect overflow?

A: CNL provides a library of components which each address a single concern. The concern of cnl::scaled_integer is the approximation of real numbers with integers. It does this as efficiently as the chosen integer type allows. In the case of int, this is very efficient, but without safety checks.

There are several solutions with different tradeoffs including:

• sanitizers, which can detect many such errors at runtime (example);
• replace int with cnl::overflow_integer to detect all such errors at runtime (example);
• replace int with cnl::elastic_integer to avoid many such errors at compile-time (example);
• consider other Composite Types to find a good balance between efficiency, safety and correctness.

Q: Why do some overflow errors only show up / not show up at run-time?

A: The preferred methods for signaling overflow errors are by trapping them and halting the program, by invoking undefined behavior (UB), or the combination of trapping UB (using a sanitizer). Trapping inevitably has to occur at run-time because the compiler cannot possibly know all the values that a program might compute...

...except when an expression is evaluated at compile time, e.g. a constexpr value. Such an evaluate is not allowed to exhibit UB, and therefore the compiler (helpfully) rejects it.

In the case where CNL is configured to not signal overflow, overflow may go undetected. And further, in the case that the overflow is UB, the program is defective and must be fixed.

Fixed-point Division

Q: Why aren't the results of cnl::scaled_integer division more precise?

A: Integer and floating-point division are fundamentally different. Being integer-based, cnl::scaled_integer uses integer division in its '/' operator.

This is surprising to users who expect fixed-point types to behave like floating-point types. But the floating-point '/' operator returns results with a variable exponent — something a fixed-point type cannot do.

In comparison, the integer '/' operator yields an integer quotient while the '%' operator provides the remainder. This gives lossless results, provided the remainder is taken into account. Integer division is more efficient and more versatile. It's also more intuitive for applications involving discrete values, such as denominations:

    // The _cnl suffix prevents decimal rounding errors.
    using namespace cnl::literals;
 
    // Euros have subunits of 100^-1
    using euros = scaled_integer<int, power<-1, 100>>;
 
    auto funds{euros{5.00_cnl}};
    auto candle_price{euros{1.10_cnl}};
 
    cout << "Q: If I have €" << funds
         << " and candles cost €" << candle_price
         << ", how many candles can I buy?\n";
 
    // 5.00 / 1.10 = 4
    auto num_candles{funds / candle_price};
 
    // 5.00 % 1.10 = 0.60
    auto change{funds % candle_price};
 
    cout << "A: I get "
         << num_candles << " candles and €"
         << change << " change.\n";

Output:

Q: If I have €5 and candles cost €1.1, how many candles can I buy?
A: I get 4 candles and €.6 change.

You can read more on the subject in the paper, Multiplication and division of fixed-point numbers by Davis Herring.

Q: OK, but what if I'm dealing with continuous values?

A: For now, divide numbers using the cnl::quotient API, which makes a best guess about the exponent you want, or consider avoiding division altogether by using the cnl::fraction type.

Due to popular demand an alternative fixed-point type, which implements 'quasi-exact' division is planned for a future revision of the library.

Elastic Limits

Q: Why doesn't the Digits parameter of types such as cnl::elastic_integer include the 'sign' bit?

A: Types, cnl::elastic_integer, cnl::elastic_scaled_integer, cnl::static_integer and cnl::static_number all have a Digits parameter which specifies how many binary digits the type stores. This corresponds to the number if bits in the value, independent of the negated two's complement MSB. It is the same value expressed in the digits member of std::numeric_limits. It is not the same as the width value found in types such as std::int32_t which are defined in <cstdint>.

One reason to choose digits instead of width is that this value indicates the range of a number consistently between signed and unsigned types. While confusing to anyone who is used to dealing in widths (e.g. std::int32_t vs std::uint32_t), it makes the implementation simpler and reduces the risk of overflow errors.