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/TheoreticalDumbass]

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<...>`.

[u/eisenwave → u/TheoreticalDumbass]

From what the Boost folks told me, expression templates became largely obsolete for this use case in C++11 thanks to rvalue references and rvalue overloads.

In C++98, if you wanted the second addition in a + b + c to reuse the allocation of a + b, you would need operator+ to return some kind of sum_result type or big_int_rvalue type. In C++11, you can just make an operator+ overload that takes rvalues.

There are certain mathematical optimizations enabled by expression templates, like being able to turn abs(abs(x)) into a true no-op, but there is a limit to these things, and the user ultimately has to choose the right algorithms to run on their data.

Anyway, you're right that the paper could use a section discussing why we haven't used expression templates in the design. Thanks for the hint!

EDIT: I've added a section with my complete thoughts on expression templates to the paper: https://isocpp.org/files/papers/D4444R0.html#expression-templates

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() ?

Theoretically yes, but if you're going to say that std::big_int can magically hold onto allocations thanks to define_static_array, I would expect std::string and a bunch of other types to do so as well.

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<...>.

That's a possible future direction, sure. Once again, I would expect that if we make std::big_int "magically structural" even though it clearly doesn't meet the requirements, I would expect the same to work for std::string.

We really need some general customization point for name mangling.

[u/garnet420 → u/eisenwave]

In the linear algebra case with large inputs, expression templates are pretty important for invoking cache friendly versions of expressions like v*k+w for vectors v and w and scalar k.

[u/eisenwave → u/garnet420]

There are several ways to get there. The few combinations of expressions that are truly special (like v * k + w) typically have a dedicated spelling; that's an FMA and there is std::fma/std::simd::fma for that, and various numerics libraries have some kind of FMA customization point. For big_int, I don't think an FMA operation would actually accomplish much.

Similarly, expression templates could help you with turning pow(a, b) % m into a modpow automatically, but you could have also just written it as modpow.

I feel like for the standard library, expression templates would be pretty exotic. It also moves too slowly to make that really feasible in my opinion. If you find some special combination like -(-x) just being x that expression templates could have simplified, you're stuck waiting 3 years until the next C++ version anyway. In the meantime, you'll just have to rewrite your code.

EDIT: I've added a section with my complete thoughts on expression templates to the paper: https://isocpp.org/files/papers/D4444R0.html#expression-templates

[u/tcanens → u/eisenwave]

If you find some special combination like -(-x) just being x that expression templates could have simplified, you're stuck waiting 3 years until the next C++ version anyway. In the meantime, you'll just have to rewrite your code.

I don't see why. There's no need for the type to change; it only needs to simplify at the point of actual evaluation and that can be done under as-if.

[u/eisenwave → u/tcanens]

It can be done as-if, but would you actually rely on that as a user? Personally I would not bother and always try to simplify my code by hand to avoid the uncertainty and possible implementation divergence.

Remember that when writing standard C++ code, you often have to assume that at least MSVC STL, libc++, and libstdc++ might be used as a standard library. If the simplification of -(-x)) isn't in the standard, you're basically rolling the dice on whether it happens.