Hey folks,

During the Croydon meeting, I have talked to a few other committee members,
and there seems to be a bit of enthusiasm for a "big int" type. That is, an
infinite-precision integer, as compared to _BitInt(N), which has fixed
width and does not "type erase" the width.

I think the motivation is obvious at this point. Unbounded integers are a
feature of standard libraries in many languages, are incredibly useful, and
are a vocabulary type. Specifically in C++, it may also be possible to make
std::big_int an intrinsic for the compiler's infinite-precision integer
type (such as llvm::APInt) during constant evaluation. This has the
potential of making a standard std::big_int dramatically faster than any
constexpr library implementation could ever be.

I believe that there are a few key design decisions (most also made in
Boost.Multiprecision) which are desirable to standardize:

   - Make it constexpr.
   - Separate the sign bit from the rest of the representation. This makes
   negation and absolutes incredibly cheap, regardless of the dynamic size of
   the integer. It also makes it cheap to query whether the integer is
   negative.
   - Perform small object optimizations, at least for up to 64 bits. In
   standardese, it should be possible to represent any standard signed or
   standard unsigned integer type as std::bit_int without having to perform
   memory allocation. This covers the common use case of merely using
   std::big_int for the eventuality that it is big, but rarely working with
   big values.
   - Perform reference counting (and copy on write) for the dynamic
   representation. This has key benefits:
      - std::big_int would typically be passed by value because it is
      cheaply copyable and cheaply movable, which is really natural in
      mathematical code. It also means there is no need to pass std::big_int
      by forwarding reference or to add extra rvalue overloads to avoid extra
      allocations. Whenever a function is given a std::big_int by value, it
      can check the reference counter and repurpose the allocation if it holds
      the sole reference.
      - It is possible to implement abs like (x < 0 ? -x : x) without
      dynamic allocation. Negation is just creating a
reference-counted copy with
      the sign bit flipped.
      - std::big_int can be cheaply returned by value from a function by a
      getter. If the class of the getter holds an int, it can create a
      std::big_int without allocating thanks to SSO. If it holds a
      std::big_int internally, it can cheaply copy that std::big_int. By
      comparison, returning a const std::string& or std::string_view from
      getters leaks internal representation details of classes.


One design aspect I'm not so sure about is whether std::big_int would be
allocator-aware and whether the "limb type" should be configurable. If
neither of these is true, it could be a non-templated class, which is
attractive.

It's worth noting that I walk on a sea of corpses. N1692, N1744, and N4038
tried to add a big integer type previously, but all died in the process.
N4038 got the furthest, but died in SG6. In any case, if we want to have
this in C++29, we need to act soon. This proposal is a massive effort, and
I could not do it myself I think given how many papers I already have, so
if anyone else is interested in supporting the effort, please reach out.


Jan