> On 14 Jan 2026, at 00:25, Thiago Macieira <thiago_at_[hidden]> wrote:
>
> On Tuesday, 13 January 2026 13:49:30 Pacific Standard Time Hans Åberg wrote:
>> The traditional multiprecision division algorithm uses a loop in order to be
>> able to handle all multiword sizes. For 2-by-1 word division, it can be
>> removed by hand, and I suggest doing it for higher multiword sizes by
>> recursive templates. So the loop can be removed, it is only very
>> complicated to do so.
>
> And have you done that complicated thing?

Yes, that is how I discovered it was much faster. It is a template, essentially an implementation of div_wide in this proposal:
https://www.open-std.org/jtc1/sc22/wg21/docs/papers/2025/p3161r4.html#functions.div_wide

LLVM implements it with a loop. I made recursive templates, removing the loop and all multiplications except one per halfword.

Tiago Freire has a copy which might be used for a reference implementation, in case you would like to add requirements that compilers have it, not merely being optional.

> And if so, why can't the compiler do
> the same? What is the reason it cannot do the same?

Why don't you ask the compiler or compiler writer? :-)

In order to remove the loop, one has to restructure the condition. For a full word implementation, one has to use two's complement features. Then in addition, using the mathematical facts that preliminary division overshoots with at most 2, that the add back step is not needed, and can further be exploited to eliminate a final multiplication.