Division with on-the-fly normalization

Niels Möller nisse at lysator.liu.se
Wed Mar 16 12:22:32 CET 2011

I'm trying to figure out what is needed to integrate division code with
on-the-fly normalization. I think the following should be done:

* Extend gmp_pi1_t to something like

  typedef struct {
    /* Normalized most significant divisor limbs */
    mp_limb_t dh[3];
    mp_limb_t inv32;
    int shift;
  } gmp_pi1_t;

* Rename current invert_pi1 to invert_3by2.

* Write a new invert_pi1 which normalizes d, uses invert_3by2, and fills
  in the other fields. Needs three limbs of d as input (pointer or
  separate arguments?). Or maybe it's getting too large for a macro, so
  it should be a function instead?

* Change mpn_sbpi1_div_qr and friends to take a gmp_pi1_t * as argument
  (or it should really be const gmp_pi1_t *, right?)

* Update callers to the new conventions.

At this stage, the code ought to compile again. Next:

* Add actual support for the unnormalized case (gmp_pi1_t->shift > 0) to
  one sb function at a time, and remove the normalization shifting in

* Fix any other normalization dependences, beyond the
  schoolbook functions. Are there any known dependencies, e.g.,
  in mpn_mu_div_*, and the inversion functions?


Niels Möller. PGP-encrypted email is preferred. Keyid C0B98E26.
Internet email is subject to wholesale government surveillance.

More information about the gmp-devel mailing list