Improved binvert algorithm

[marco.bodrato at tutanota.com]

Ciao David, ciao Niels

8 feb 2026, 20:13 da nisse at lysator.liu.se:

> David Sparks <sparks05 at proton.me> writes:
>
>> __attribute__((const))
>> uint64_t binvert_64(uint64_t n)
>> {
>>  uint64_t r = 3*n ^ 2;	//  5 bits
>>  uint64_t y = 1 - n*r;
>>  r *= 1+y;		// 10 bits
>>  y *= y;
>>  r *= 1+y;		// 20 bits
>>  y *= y;
>>  r *= 1+y;		// 40 bits
>>  y *= y;
>>  r *= 1+y;		// 64 bits
>>  return r;
>> }
>>
>
> Interesting! To me, the clever thing is that the sequence of y values is
> computed independently of r, with only a single multiply latency.
>
Of course, but also the fact that it does not use a table is interesting. 

> But it looks like the logic (starting from the binvert_limb_table) is
> duplicated in a few places, e.g., mpn/x86_64/dive_1.asm), so to adopt
> this method, there are several places to update.
>
While thinking to binvert I've found another place.
Another implementation can be found in sec_powm, it's role is to avoid
using a table in a sec_ function.
It starts with a 5-bits inverse, but the trick to find it was more complex
than the trick proposed by David. I just changed it.
https://gmplib.org/repo/gmp/rev/1d1aff591461

Then, the current code uses 5 multiplication to obtain the 32-bits inverse
and 6 multiplication to obtain the 64-bits one.
But the current code is complex, and for all machines where a multiplication
is not very slow, the code proposed by David should fit.
Are there machines whit a so slow multiplication that saving some is a good
idea?
Ĝis,
m
-- 
DC: https://vado.li/dc-bodrato