Static Numbers

    Papers:

  1. P0828R1: elastic_integer
  2. P0037R7: scaled_integer
  3. P0554R1: Composition

1. P0828R1: elastic_integer

The Type

integer that generalizes promotion to avoid overflow

template<int Digits, class Narrowest>
class elastic_integer {
  // the actual number of digits allocated
  static constexpr int digits_ = ...;
public:
  using rep = set_digits_t<Narrowest, digits_>;
  // ...
private:
  rep rep_;
};

The Type

The gory details of rep.

template<int Digits, class Narrowest>
class elastic_integer {
  static constexpr int min_digits_ = digits_v<Narrowest>;
  static constexpr int digits_ = max(min_digits_, Digits);
public:
  using rep = set_digits_t<Narrowest, digits_>;
  // ...
private:
  rep rep_;
};

The Operators

operands promoted to prevent overflow

auto a = elastic_integer<7>{100};

// elastic_integer<14>, uses int32_t
auto b = a*a;

movsx   ecx, byte ptr [rdi]
movsx   eax, byte ptr [rsi]
imul    eax, ecx
ret
auto c = elastic_integer<15>{10000};

// elastic_integer<30>, uses int32_t
auto d = c*c;
movsx   ecx, word ptr [rdi]
movsx   eax, word ptr [rsi]
imul    eax, ecx
ret
auto e = elastic_integer<31>{1000000000};

// elastic_integer<62>, uses int64_t
auto f = e*e;
movsxd  rcx, dword ptr [rdi]
movsxd  rax, dword ptr [rsi]
imul    rax, rcx
ret

The Operators

native promotion to int width is observed

auto a = elastic_integer<7>{100};

// elastic_integer<14>, uses int32_t
auto b = a*a;

movsx   ecx, byte ptr [rdi]
movsx   eax, byte ptr [rsi]
imul    eax, ecx
ret
auto c = elastic_integer<15>{10000};

// elastic_integer<30>, uses int32_t
auto d = c*c;
movsx   ecx, word ptr [rdi]
movsx   eax, word ptr [rsi]
imul    eax, ecx
ret
auto e = elastic_integer<31>{1000000000};

// elastic_integer<62>, uses int64_t
auto f = e*e;
movsxd  rcx, dword ptr [rdi]
movsxd  rax, dword ptr [rsi]
imul    rax, rcx
ret

The Operators

further promotion happens when necessary

auto a = elastic_integer<7>{100};

// elastic_integer<14>, uses int32_t
auto b = a*a;

movsx   ecx, byte ptr [rdi]
movsx   eax, byte ptr [rsi]
imul    eax, ecx
ret
auto c = elastic_integer<15>{10000};

// elastic_integer<30>, uses int32_t
auto d = c*c;
movsx   ecx, word ptr [rdi]
movsx   eax, word ptr [rsi]
imul    eax, ecx
ret
auto e = elastic_integer<31>{1000000000};

// elastic_integer<62>, uses int64_t
auto f = e*e;
movsxd  rcx, dword ptr [rdi]
movsxd  rax, dword ptr [rsi]
imul    rax, rcx
ret

The Operators

How operands affect width of result:

    • widen: +, -, *, <<†
    • narrow: >>†
    • wider operand: |, ^
    • narrower operand: &, %
    • same: =, @=, ++, --, ~,
    • Boolean: &&, ||, <=> etc.
    • 1st operand: /
  • There's a separate set of rules for signedness of result
  • †when 2nd operand is integral_constant

Run-time Overflow

some operations cannot avoid overflow, e.g.

  • assignment
  • conversion
  • bitwise shift left†
  • some compound assignment
  • increment/decrement

†unless 2nd operand is integral_constant

Run-time Overflow

Run-time range errors are a separate concern.

A complete safety solution is a composite type.

// Overflow is a contract violation.
template<class Rep>
class overflow_integer;

// a type that widens when it can, and traps when it can't
template<int Digits, class Narrowest=int>
using safe_integer =
    overflow_integer<elastic_integer<Digits, Narrowest>>;

(see P0554)

Further Composition

static arbitrarily wide integer

// similar type to P0539
template<int Digits=31, class Narrowest=int>
class wide_integer;

// a type that widens arbitrarily
template<int Digits, class Narrowest=int>
using wide_elastic_integer =
    elastic_integer<Digits, wide_integer<1, Narrowest>>;

Most Negative Number

MNN poses a dilemma

  • rare edge case
  • is costly to test at run-time
  • promotion-based avoidance costs bits
  • making it an illegal value is appealing

Numeric Traits

How do you manipulate number of digits?

  • new traits
    • digits_v<T> - P0437-friendly numeric_limits::digits
    • set_digits_t<T, int Digits> - type with at least that many digits
  • existing traits
    • make_signed_t/make_unsigned_t
    • is_signed_v/is_unsigned_v

(More traits possible for fractional digits)

2. P0037R7: Fixed-Point Real Numbers

The Type

scales integers to approximate real-numbers, i.e. fixed-point arithmetic

template<int Exponent, int Radix=2>
class power;
template<class Rep=int, class Scale=power<0>>
class scaled_integer;
template<class Rep, class Scale>
class scaled_integer {
public:
  ...
private:
  Rep rep_;  // value is rep_*Radix^Exponent
};

The Type

Like a span of digits over a number...

 
scaled_integer<short, power<-8>> a{10.75}
 
…00000000000000001010.11000000000000000000…

The Type

Becomes an integer when Exponent=0...

 
scaled_integer<int> b{42}
 
…0000000000000000000000000000000101010.0000000…

Conversion

conversion to/from integer scales

scaled_integer<int, power<-16>>
from_int(int n)
{
    return n;
}
from_int(int):
	mov     eax, edi
	sal     eax, 16
	ret
int
to_int(scaled_integer<int, power<-16>> f)
{
    return static_cast<int>(f);
}
to_int(scaled_integer<int, power<-16>>):
	test    edi, edi
	lea     eax, [rdi+65535]
	cmovns  eax, edi
	sar     eax, 16
	ret
int
to_int(scaled_integer<int, power<-16>> f)
{
    Expects(f>=0);
    return static_cast<int>(f);
}
to_int(scaled_integer<int, power<-16>>):
	mov     eax, edi
	sar     eax, 16
	ret

Conversion

-ve right-shift prevents efficient down-scaling

scaled_integer<int, power<-16>>
from_int(int n)
{
    return n;
}
from_int(int):
	mov     eax, edi
	sal     eax, 16
	ret
int
to_int(scaled_integer<int, power<-16>> f)
{
    return static_cast<int>(f);
}
to_int(scaled_integer<int, power<-16>>):
	test    edi, edi
	lea     eax, [rdi+65535]
	cmovns  eax, edi
	sar     eax, 16
	ret
int
to_int(scaled_integer<int, power<-16>> f)
{
    Expects(f>=0);
    return static_cast<int>(f);
}
to_int(scaled_integer<int, power<-16>>):
        mov     eax, edi
        sar     eax, 16
        ret

Conversion

Rep must be unsigned or known non-negative

scaled_integer<int, power<-16>>
from_int(int n)
{
    return n;
}
from_int(int):
	mov     eax, edi
	sal     eax, 16
	ret
int
to_int(scaled_integer<int, power<-16>> f)
{
    return static_cast<int>(f);
}
to_int(scaled_integer<int, power<-16>>):
	test    edi, edi
	lea     eax, [rdi+65535]
	cmovns  eax, edi
	sar     eax, 16
	ret
int
to_int(scaled_integer<int, power<-16>> f)
{
    Expects(f>=0);
    return static_cast<int>(f);
}
to_int(scaled_integer<int, power<-16>>):
        mov     eax, edi
        sar     eax, 16
        ret

The Operators

Arithmetic operators are pass-throughs.

auto
add(int l,
    int r) {

    return l+r;
}
add:
	lea     eax, [rdi+rsi]
	ret
auto
mult(int l,
     int r) {

    return l*r;
}
mult:
	mov     eax, edi
	imul    eax, esi
	ret
auto
divide(int l,
       int r) {

    return l/r;
}
divide:
	mov     eax, edi
	cdq
	idiv    esi
	ret

The Operators

Arithmetic overloads are pass-throughs.

auto
add(scaled_integer<int, power<-8>> l,
    scaled_integer<int, power<-8>> r) {
    // scaled_integer<int, power<-8>>
    return l+r;
}
add:
	lea     eax, [rdi+rsi]
	ret
auto
mult(scaled_integer<int, power<-8>> l,
     scaled_integer<int, power<-8>> r) {
    // scaled_integer<int, power<-16>>
    return l*r;
}
mult:
	mov     eax, edi
	imul    eax, esi
	ret
auto
divide(scaled_integer<int, power<-8>> l,
       scaled_integer<int, power<-8>> r) {
    // scaled_integer<int, power<0>>
    return l/r;
}
divide:
	mov     eax, edi
	cdq
	idiv    esi
	ret

The Operators

Multiplication is lossless but susceptible to overflow.

auto
add(scaled_integer<int, power<-8>> l,
    scaled_integer<int, power<-8>> r) {
    // scaled_integer<int, power<-8>>
    return l+r;
}
add:
	lea     eax, [rdi+rsi]
	ret
auto
mult(scaled_integer<int, power<-8>> l,
     scaled_integer<int, power<-8>> r) {
    // scaled_integer<int, power<-16>>
    return l*r;
}
mult:
	mov     eax, edi
	imul    eax, esi
	ret
auto
divide(scaled_integer<int, power<-8>> l,
       scaled_integer<int, power<-8>> r) {
    // scaled_integer<int, power<0>>
    return l/r;
}
divide:
	mov     eax, edi
	cdq
	idiv    esi
	ret

The Operators

Division is surprising.

auto
add(scaled_integer<int, power<-8>> l,
    scaled_integer<int, power<-8>> r) {
    // scaled_integer<int, power<-8>>
    return l+r;
}
add:
	lea     eax, [rdi+rsi]
	ret
auto
mult(scaled_integer<int, power<-8>> l,
     scaled_integer<int, power<-8>> r) {
    // scaled_integer<int, power<-16>>
    return l*r;
}
mult:
	mov     eax, edi
	imul    eax, esi
	ret
auto
divide(scaled_integer<int, power<-8>> l,
       scaled_integer<int, power<-8>> r) {
    // scaled_integer<int, power<0>>
    return l/r;
}
divide:
	mov     eax, edi
	cdq
	idiv    esi
	ret

Composition

  • Problems faced by scaled_integer are orthogonal
  • int already suffers from them
  • They become acute when using int to replace float
  • Easiest to solve is multiplication...

Lossless Multiplication

template<int Digits, class Narrowest=int>
class elastic_integer;

template<int Digits, int Exponent, typename Narrowest=int>
using elastic_scaled_integer =
    scaled_integer<
        elastic_integer<
            Digits,
            Narrowest>,
        power<Exponent>>;

Lossless Multiplication

No risk of overflow; no loss of precision.

auto add(elastic_scaled_integer<31, -16> l,
         elastic_scaled_integer<31, -16> r) {
    // returns elastic_scaled_integer<32, -16>
    return l+r;
}
add:
	movsx   rsi, esi
	movsx   rax, edi
	add     rax, rsi
	ret
auto mult(elastic_scaled_integer<31, -16> l,
          elastic_scaled_integer<31, -16> r) {
    // returns elastic_scaled_integer<62, -32>
    return l*r;
}
mult:
	movsx   rax, esi
	movsx   rdi, edi
	imul    rax, rdi
	ret
auto divide(elastic_scaled_integer<31, -16> l,
            elastic_scaled_integer<31, -16> r) {
    // returns elastic_scaled_integer<31, 0>
    return l/r;
}
divide:
	mov     eax, edi
	cdq
	idiv    esi
	ret

Lossless Multiplication

Wrapper over simple integer arithmetic.

auto add(int l,
         int r) {

    return (long long)l+r;
}
add:
	movsx   rsi, esi
	movsx   rax, edi
	add     rax, rsi
	ret
auto mult(int l,
          int r) {

    return (long long)l*r;
}
mult:
	movsx   rax, esi
	movsx   rdi, edi
	imul    rax, rdi
	ret
auto divide(int l,
            int r) {

    return l/r;
}
divide:
	mov     eax, edi
	cdq
	idiv    esi
	ret

Fixed-point Division

vs

'Quasi-Exact' Division

Subject of P1368R0

  • Quasi-exact division pre-widens dividend
  • Avoids imprecise results where possible
  • Typically feels like floating-point division
  • scaled_integer supports with a free function
  • Finance is compelling case for scaled_integer division

'Quasi-Exact' Division

Multiply: operand digits contribute to result

5.5 * 5.5 = 30.25
55. * .55 = 30.25
5.5 * 55. = 302.5

AAA.BBBBB * CCCCCC.DD = AAACCCCCC.BBBBBDD

Division: operand digits cross-contribute to result

10 / 100 = 00.10
1 / 1000 = 0.001

AAA.BBBBB / CCCCCC.DD = AAADD.BBBBBCCCCCC

scaled_integer Division.

€0.80 / €0.25 = 3 r €0.05

template<int Exponent>
using currency = scaled_integer<int, power<Exponent, 10>>;

auto n = currency<-2>(.80);
auto d = currency<-2>(.25);

auto q = n / d;  // currency<0>(3)
auto r = n % d;  // currency<-2>(.05)

scaled_integer Division.

€0.80 / 3 = €0.26 r €0.02

template<int Exponent>
using currency = scaled_integer<int, power<Exponent, 10>>;

auto n = currency<-2>(.80);
auto d = currency<0>(3);

auto q = n / d;  // currency<-2>(.26)
auto r = n % d;  // currency<-2>(.02)

As an alternative to float

  • Floating-point uses as much as 10× silicon and energy
  • Fixed-point is sometimes faster, sometimes slower
  • Applications include finance, CNNs, FPGAs, DSPs
  • Plus modelling of systems with determinism and tight control over precision

3. P0554R1: Composition

Background

  • Two competing fixed-point papers presented in Jacksonville 2016:
    • P0106R0 proposed few types that each bundled many features
    • P0037R1 proposed a single type which addressed a single concern
  • SG6 asked authors to coordinate
  • P0554 was written to explain:
    • why library types should address a single concern
    • how they could be combined to address multiple concerns
    • what the individual concerns (and therefore types) are
  • Provides a context for P0037 and P0828

Motivation

  • Subject is fixed-size numeric types
  • A well-established list of concerns exists
  • Types typically enhance integers in some way
  • Should be class templates with integer/family as parameter
  • Allows any 3rd-party or non-standard integers to be used (DSPs, Boost.Multiprecision, std::pack)
  • Allows chaining of one type within another to build up functionality
  • Referred to as The Compositional Approach

The Compositional Approach

  • All numeric types are Components
  • Can be used as parameters in wrapper types
  • These in turn make new components
  • Wrappers can be chained together to make composites
  • Not all combinations work or are useful
  • A named set of components is proposed
  • Ultimate goal (for some) is a pair of composites:
    • static_integer - a 'smart' integer
    • static_number - a 'smart' real number approximation

The Concerns

The main concerns to be addressed:

  • Run-time handling of out-of-range errors
  • More consistent promotion rules to prevent range errors
  • Arbitrary-width integers
  • Scaled integers to approximate real numbers
  • 'Quasi-exact' division of fixed-point numbers
  • Rounding

Out-of-range Handling

template<class Rep, class Tag=contract_tag>
class overflow_integer;

// makes out-of-range a pre/post-condition violation
struct contract_tag;

// clamps out-of-range values to minimum/maximum value
struct saturate_tag;

// wraps out-of-range value a la unsigned
struct modulo_tag;

// saturates and stays saturated (like IEEE 754)
struct sticky_tag;

Out-of-range Avoidance

Subject of P0828

template<int Digits, class Narrowest=int>
class elastic_integer;

(likely decomposed further into two separate concerns)

Wide Integers

A.K.A. fixed-size bignum; associated with multi-word

template<int Digits, class Narrowest>
class wide_integer;

Narrowest denotes the least wide representational type to use. For example, wide_integer<12, short>, would fit into 2 bytes. However, wide_integer<24, short>, would use at least 4 bytes.

Scaled Integers

Subject of P0037

template<int Exponent, int Radix=2>
class power;
template<class Rep, class Scale>
class scaled_integer;
scaled_integer<int32_t, power<-16>> q15_16{13.75};

Quasi-exact Division

Subject of P1368R1

template<int Exponent, int Radix=2>
class quasi_exact_division_integer;
  • Thin wrapper over scaled_integer
  • Provides alternative operator/ behavior
  • Deletes operator%

Rounding

Consistent rounding following float-to-int, right-shift and division operations.

template<class Rep, class Tag=nearest_tag>
class rounding_integer;

struct nearest_tag;     // traditional round-to-nearest
struct native_tag;      // do whatever Rep 'wants'
struct truncate_tag;    // lop off the fractional part
struct round_down_tag;  // toward -ve infinity
// etc.

Composite Type

static_integer is similar to P0106's integral.

template<
    int Digits = digits<int>::value,
    class RoundingTag = nearest_tag,
    class OverflowTag = contract_tag,
    class Narrowest = int>
using static_integer =
  rounding_integer<
    overflow_integer<
      elastic_integer<
        Digits,
        wide_integer<1, Narrowest>>,
      OverflowTag>,
    RoundingTag>;

Composite Type

static_number is similar to P0106's negatable.

template<
    int Digits,
    int Exponent = 0,
    class RoundingTag = nearest_tag,
    class OverflowTag = contract_tag,
    class Narrowest = int>
using static_number =
    quasi_exact_division_integer<
      static_integer<
        Digits,
        RoundingTag,
        OverflowTag,
        Narrowest>,
      power<Exponent, 2>>;