Date: Tue, 13 Jan 2026 18:33:39 +0100
> On 13 Jan 2026, at 18:03, Marcin Jaczewski <marcinjaczewski86_at_[hidden]> wrote:
>
> wt., 13 sty 2026 o 17:59 Hans Åberg via Std-Proposals
> <std-proposals_at_[hidden]> napisał(a):
>> It is important for pipelining to avoid backward jumps, like in loops. Despite Clang having an efficient 2-word by 1-word 64-bit implementation, its 2-word by 2-word division uses binary division, which is slow. In addition, 2-word by 1-word division can be optimized to only use one multiplication per half-word.
>>
>
> And how do you prevent that in your `int_mod<m>` not use the same
> exact implementation? Like they implement `int_mod` using `_BitInt`
> and call it a day?
The C++ standard does not specify implementations except implicitly by means of algorithm complexity, though one might supply a reference implementation, as in the case of STL in the past.
I made an implementation of essentially Tiago Freire's proposal below, only adding a 2-word by 2-word implementation. For the API, I need to add, for a given word, template selectors for the half-word and double-word.
https://www.open-std.org/jtc1/sc22/wg21/docs/papers/2025/p3161r4.html
One inspiration is the computation of modular inverses, which is simple in the case when squaring the modulus. For powers of 2, one can write recursive templates.
>
> wt., 13 sty 2026 o 17:59 Hans Åberg via Std-Proposals
> <std-proposals_at_[hidden]> napisał(a):
>> It is important for pipelining to avoid backward jumps, like in loops. Despite Clang having an efficient 2-word by 1-word 64-bit implementation, its 2-word by 2-word division uses binary division, which is slow. In addition, 2-word by 1-word division can be optimized to only use one multiplication per half-word.
>>
>
> And how do you prevent that in your `int_mod<m>` not use the same
> exact implementation? Like they implement `int_mod` using `_BitInt`
> and call it a day?
The C++ standard does not specify implementations except implicitly by means of algorithm complexity, though one might supply a reference implementation, as in the case of STL in the past.
I made an implementation of essentially Tiago Freire's proposal below, only adding a 2-word by 2-word implementation. For the API, I need to add, for a given word, template selectors for the half-word and double-word.
https://www.open-std.org/jtc1/sc22/wg21/docs/papers/2025/p3161r4.html
One inspiration is the computation of modular inverses, which is simple in the case when squaring the modulus. For powers of 2, one can write recursive templates.
Received on 2026-01-13 17:33:58