Improved binvert algorithm

[Niels Möller]

marco.bodrato at tutanota.com writes:

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

I would expect David's code to win on any machine where there's any
pipelining of multiplication (i.e., two independent multiplies
significantly faster than two dependent ones).

And even if it may be a slowdown (I think it's 6 multiplies rather than
5, which could be a 20% slowdown) on rare machines without any
pipelining, it may be worth it if we can have a table-free binvert_limb
and delete both binvert_limb_table and sec_binvert_limb.

> Are there machines whit a so slow multiplication that saving some is a good
> idea?

E.g., the decade old Intel Atom processors seem to lack mul pipelining
(if I read https://gmplib.org/~tege/x86-timing.pdf correctly, 18
cycles). Looks like there's at least one atom machine, "glm", in the gmp
farm that could be used to test performance. Any other examples?

Regrads,
/Niels

-- 
Niels Möller. PGP key CB4962D070D77D7FCB8BA36271D8F1FF368C6677.
Internet email is subject to wholesale government surveillance.