divrem_1 and mod_1

Torbjorn Granlund tg at gmplib.org
Fri Nov 22 17:51:39 UTC 2013

Just to make sure I start from the right spot: You're talking about
Hensel norm division here, right?

When Paul posted results in March, I thought your work was on plain old
Euclidean norm.

We (mainly I and Niels, I suppose) have spent much more time on
Euclidean norm division/mod that on the corresponding Hensel norm

Current functions:

mpn_divexact_1      (file name dive_1.{c,asm})
mpn_modexact_1_odd  (file name mode1o.{c,asm})

We intend to rename things to follow the Euclidean naming scheme, but
using 'bdiv' instad of 'div'.  (There is nothing uniquely "exact" about
the functions, the naming is just weird.)

We also played with two-word inverses, i.e., d^{-1} mod \beta^2, where d
is the divisor and \beta is the implied limb base.  That's the
bdiv_qr_1_pi2 line of https://gmplib.org/devel/asm.html.

It would be interesting to incorpoate your work into GMP.


More information about the gmp-devel mailing list