CNL
2.0.2 (development)
Compositional Numeric Library
|
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
The CNL project is published under the Boost licence and can be found online at github.com/johnmcfarlane/cnl.
The core numeric types of CNL are:
Each of these types solves a single problem when used alone.
In combination, the core types produce composites which address multiple concerns.
Provided composite types include:
Many more combinations are possible. For example:
safe_integer
(overflow_integer and elastic_integer);wide_elastic_integer
(elastic_integer and wide_integer) andsafe_fraction
(fraction and safe_integer
).The following examples can be found in the test suite.
The scaled_integer type adds a scaling exponent to integers. This enables the integer to represent very big or very small values.
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.
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.
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.
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?
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
:
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:
int
with cnl::overflow_integer to detect all such errors at runtime (example);int
with cnl::elastic_integer to avoid many such errors at compile-time (example);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.
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:
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.
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.