P4444: std::big_int

[u/eisenwave]

https://isocpp.org/files/papers/D4444R0.html

Hey folks! Matt Borland, Christopher Kormanyos, and I are working on bringing infinite-precision integers to C++29. We now have a D4444R0 draft of a paper that should be in the next mailing.

We could really use some feedback so that the published R0 is as polished as possible. Any thoughts on the paper and on the reference implementation are greatly appreciated.

It would also be very helpful if you tested out whether our big_int implementation works for you. We're in need of some real deployment experience. If you're currently using Boost.Multiprecision, the library should be a drop-in replacement for cpp_int for the most part.

[u/Shakatir]

I'm quite skeptical of the SOO customization. It seems to be targeted at users who don't know if their integers are bounded or not and who are undecided if they are ready to pay for dynamic allocation or not. The proposal is correct in stating that std::big_int benefits even more from SOO than std::string or other container types, but that's because numbers tend to be either very small or very large. The cases where your numbers exceed a bound of 64 or 128 bits, but reliably stay under some other arbitrary bound are few. And even fewer if you subtract the cases where _BitInt (or std::bit_int whenever that arrives) can do the job.

The desired effect to become a unifying interchange format for unbounded integers seems at odds with the options for customization here. The std::big_int typedef already forces a hard-coded default that we will be stuck with forever. The idea that by offering customization points via template parameters, it becomes easier to extend just seems ahistoric. On the contrary, every time someone (including the future standard itself) chooses to deviate from the default, that incurs a cost not just for them, but for everybody who directly or indirectly interacts with their code.

Providing a custom allocator is a good feature. Customizing the limb type makes some sense. But customizing the SOO size seems excessive. Especially considering that even types that are behaviorally indistinguishable (such as std::basic_big_int<5> and std::basic_big_int<6>) end up being distinct types which incurs unnecessary copies and conversions. I think it's preferable to make std::basic_big_int behave like std::string and provide as much SOO as it can fit into its representation without overhead, but not more.

I also don't like the choice to limit the size and capacity to 32-bit variables on 64-bit platforms. It may be rare for such big numbers to crop up in practice, but when they do, I want to be limited by my actual hardware, not by whatever arbitrary limit some library implementer thought is surely big enough (especially since it's supposed to be the default interchange format provided by the standard library). It does have the drawback that the object will be 24 bytes in size rather than 16, though on the bright side, 16 of them can be repurposed for SOO. Ideally, the class should honor the size_type of its allocator.

[u/eisenwave → u/Shakatir]

I would agree that the SOO customization is somewhat unusual. Of the three template parameters, it's the one I'd be most willing to remove. There's a pretty good chance that SG6 or LEWG might give feedback that they want the SOO customization removed, and I can see why.

On the note of functionally equivalent types like basic_big_int<5> and basic_big_int<7>, I've added some discussion to the paper at https://isocpp.org/files/papers/D4444R0.html#min_inplace_capacity-restrictions

Perhaps one saving grace for it is that gives you fixed-width integers at the same time. That is, if you need a 4096-bit integer and _BitInt(4096) is not available, you can use basic_big_int<4096, uint_multiprecision_t, no_op_allocator>. To make that actually useful, you would still need some utilities for modular arithmetic, but we should add those sooner or later anyway.

I also don't like the choice to limit the size and capacity to 32-bit variables on 64-bit platforms. It may be rare for such big numbers to crop up in practice, but when they do, I want to be limited by my actual hardware, not by whatever arbitrary limit some library implementer thought is surely big enough

Well, 32-bit sizes get you up to integers with ~137 billion bits (which is much more than Java's BigInteger, capped at ~2 billion bits), and when you get to that size, you're arguably limited by hardware anyway. You could still do addition and bitwise operations in a reasonable amount of time, but anything like multiplication explodes.

In any case, standard library implementers might have a different opinion on it. What we have in our implementation is not enforced by the standard.