Division with on-the-fly normalization

[Niels Möller]

nisse at lysator.liu.se (Niels Möller) writes:

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

I'm attaching a patch to do the above (relative to my hack tree, so
might need a little fuzz to apply). Passes make check for me (but I'm
not sure all the code is exercised, I didn't compile with
--disable-asembly).

Comments? I think it would be nice to get something like this in
reasonably soon. The only point where it's obvious that one can disagree
on aesthetics is the invert_pi1 macro,

  #define invert_pi1(dinv, d) ...

which one might want to do as 

  #define invert_pi1(dinv, d2, d1, d0) ...

instead, or (since it's getting fairly large) as a function, whatever
that should be called. What does "*_cps" (used for the mod_1 functions)
mean?

Regards,
/Niels

-------------- next part --------------
A non-text attachment was scrubbed...
Name: phase-1.diff
Type: text/x-patch
Size: 22207 bytes
Desc: not available
URL: <http://gmplib.org/list-archives/gmp-devel/attachments/20110317/378ad987/attachment.bin>
-------------- next part --------------

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