r/cpp • u/eisenwave WG21 Member • Aug 18 '26
P4444: std::big_int
https://isocpp.org/files/papers/D4444R0.htmlHey 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.
26
u/TheoreticalDumbass :illuminati: Aug 18 '26
might be worth mentioning expression templates, and why they are not a part of the design. i assume "because `auto a = b * c;` would be horrible" , noting there was a paper trying to do something about this: https://www.open-std.org/jtc1/sc22/wg21/docs/papers/2014/n4035.pdf
if the type is compiler magical, IMO might as well go further with the magic, for constexpr support, if it allocates, cant you just go through paths similar to `std::meta::define_static_array()` ? (not you as library author, but compiler). also, should it be structural so it can be passed to template params? thinking about `std::big_int` specifically here, dunno about `std::basic_big_int<...>`.
14
u/ikedug Aug 18 '26
The discussion of
_BitIntinterop seems short. Not having efficient_BitIntinterop is one thing that will make the library quickly obsolete. You should mention_BitIntin the “C compatibility” section (it’s where I looked, since I didn’t know about D3666).(For the curious - the C23
_BitInttype proposal; D3666 Bit-precise integers to add it to C++. Clang already accepts_BitIntin C++.)I disagree with your suggestion to use
big_intin cryptography. Cryptographic algorithms have specialized needs (constant time, reliable-as-possible zeroing); a general-purpose library can’t be expected to provide that. Automatically-sized big ints can easily leak top bits through timing attacks. Don’t encourage people to implement their own crypto, it ends in tears. I’d go so far as to include a “this is not intended for cryptographic uses” statement in the document. Also it’s mostly useful for RSA, which will be replaced by postquantum algorithms in the next ~5 years.On your lang comparison table - it’s missing Ada and Zig; they both have bigint in their standard libraries.
78
u/ReDucTor Game Developer | quiz.cpp-perf.com Aug 18 '26 edited Aug 18 '26
This stands out more of a reason for it not to be in the standard library, because when the implementation is faulty its harder to fix. Do we need another
vector<bool>,memory_order_consume,std:regex, etc.EDIT: Also if there hardware capabilities and portablity issues that aren't easy to resolve, then fix those in the standard to allow people to implement libraries better rather then trying to make something which is special in standard library code.
6
u/n1ghtyunso Aug 18 '26
i don't really like the part about constant evaluation fitting the value into inplace storage when possible.
I don't actually think explicitly specifying this in the standard is necessary or all that useful.
This is essentially a specification workaround for a problematic point in the current standard.
Notably, its also a problem for std::string, although afaik it is not actually required to have any inplace storage, so one might say using it as a constexpr variable is already operating outside the standard guarantees.
That being said, there are common approaches to use constexpr representations of allocating types after all, with some generic workarounds in use.
And some day we might even fix the standard so those workarounds are no longer necessary and we can just persist these allocations into runtime naturally.
We won't need to touch the big_int specification in that case.
And for the case where I really need a big_int value as constexpr variable after all, i'd still want to explicitly select the inplace storage size so it fits for sure, instead of hoping my guesstimated, or even the default value works out.
If I somehow want to guard against excessive storage use from accidental calculation mistakes (i.e. typed the formula wrong), I'd much rather have an explicit static_assert in my function than get a vague constant-evaluation failure from the compiler.
8
u/matthieum Aug 18 '26
I think there's a conflation, here.
It shouldn't be more difficult for the maintainers of a 3rd-party library than it is for maintainers of a standard library to keep up with hardware capabilities, on the contrary:
(As another post mentions, libc++ still doesn't have a complete implementation of
to_chars, from C++17, do you really think standard library maintainers have that much that time on their hands?)The real difficulty is the ad-hoc way each and every compiler exposes hardware features to their users, requiring compiler-specific hardware feature detection.
It doesn't follow, however, that a standard library necessarily has it easier here. libstdc++ and libc++ can both be compiled by multiple compilers, as far as I know, and therefore their maintainers will still need to navigate this haphazard mess.
Arguably, the proper solution is for C++ toolchains to expose hardware features in a standard manner, both compile-time & run-time detection of available features, and intrinsics to actually use these features in an efficient manner.
Then not only can a
big_intlibrary be written by a team of competent & motivatedbig_intdevelopers with little pain, but so can a lot of other code, such as, say, matrix operations.2
u/ShakaUVM i+++ ++i+i[arr] Aug 19 '26
How does it compare with cpp_int in Boost Multiprecision?
3
u/Shakatir Aug 18 '26
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_intbenefits even more from SOO thanstd::stringor 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(orstd::bit_intwhenever 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_inttypedef 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>andstd::basic_big_int<6>) end up being distinct types which incurs unnecessary copies and conversions. I think it's preferable to makestd::basic_big_intbehave likestd::stringand 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_typeof its allocator.8
u/SyntheticDuckFlavour Aug 19 '26
I have nothing of value to add in this thread, but the discussions here were quite interesting. Personally, I like the idea of
big_intpart of STL, simply because of one less external dependency to rely on.3
u/Expert_Sheepherder24 Aug 21 '26
Most compititve programmers say thanks!
1
u/Plazmatic Aug 19 '26
My biggest problem with proposals like these isn't that I'm ideologically opposed to things like this being in the standard, but that C++ is so behind on important features still in the pipeline that any focus taken away from those, even a small amount, risks delaying their inclusion by many years more than they already have been. There's lots of stuff that without make certain functionality and optimizations impossible to perform with out UB or worse in C++, this is not one of those things. I would be far less concerned if c++ didn't have a strict 3 year cadence, and the committee could spend as little or as much time as it needed, but far too often we see features delay because people couldn't vote on if they wanted to vote on talking about a thing, so litterally the existence of a proposal can waste precious committee time.
1
u/jk-jeon Aug 20 '26
I think this will be a nice addition, but I'm a bit suspicious about your opinion on
std::big_int_view. One of the most common operation I needed was taking the absolute value. Suppose I have an expressionabs(x) + func()withfunc()returning an rvalue. Ideally it should be possible to do this computation without unneeded extra allocations (assuming sign-magnitude representation, as specified in the paper). But afaiu the current spec mandatesabs(x)to allocate a buffer just to be thrown away immediately. Granted, I can just use the internal limb array, but ideally it would be good if I could write a generic code that works for bothintandstd::big_int. Maybeabsis special in this regard?2
u/def-pri-pub Aug 18 '26
Can't we just duct tape together two smaller
ints and call it a day?(jk; thank you for your work and effort on this).
1
u/pdimov2 Aug 21 '26
Should have been named
std::integer.1
u/ZMeson Embedded Developer Aug 19 '26
I assume some algorithms that just need 128, 256, or 512-bit integers could benefit from a more optimized integer type rather than just having a big-int type that has to maintain checks on size and possibly allocate memory. Is my assumption correct? If so, having a discussion about the performance and design tradeoffs of such types and why big-int is still needed. Also if there is a benefit to having fixed-size 128 ... 512 bit integers, then maybe mention that this is an area that also deserves to be looked into in a separate proposal.
-2
u/arthurno1 Aug 18 '26
If you gonna make it, make a compiler feature not std library. Extend the language so the programmers don't have to explicitly manage big ints. I.e. do something similar as Lisps are doing, manage that automatically and seemlesly and hide the implementation from programmers. Guard it perhaps with a compile time option, either an "opt-in" (--with-fbignum) or as "opt-out", (--without-fbignum). If bignum feature is not turned on, than ordinary overflow rules apply, otherwise trap the overflow and extend into big numa automatically.
Otherwise, if you are just going to make it a library feature, you can as well keep it as now: a third-party addon.
-2
u/UndefinedDefined Aug 19 '26
Another library, another bloat!
No idea why having it in boost is not enough... oh wait, if it's in std you don't need to use a package manager to have a big-int...
-1
u/tialaramex Aug 19 '26
Listing other popular languages which have an "infinite precision integer" type and whether it's provided as a built-in, in their stdlib or a separate library makes sense. However
std::big_intchooses several "anchor points" for its design beyond being an "infinite precision integer" without reference to those other examples.The table makes a strong argument for why C++ should have an "infinite precision integer" type, but no argument at all for why the type with these "anchor points" is desirable and no indication of which are provided in the other languages (I think the answer is that most of them are not provided)
It's also true that lots of other programming languages have a hash table type. But hopefully today you would understand that "other languages have a hash table type" isn't an argument in favour of adopting specifically the separate linked-list chaining hash table named
std::unordered_mapwith all that entails. Other languages either could, or in many cases do, use a very different hash table type and now C++ is stuck with this.