Division interfaces

[Niels Möller]

Torbjorn Granlund <tg at gmplib.org> writes:

> nisse at lysator.liu.se (Niels Möller) writes:
>
>   then do the book-keping needed when doing the mpn_submul_1 calls with
>   unnormalized arguments.
>   
> I don't get this part.

What I mean is that we divide U / D, we don't fully normalize U and D.
We first get the normalized topmost two limbs d1 and d0 of D, and invert
for use with 3/2 division.

We then have a loop that maintains u2,u1,u0 as top limbs of U, shifted
to match the normalization of d1, d0, gets a quotient candidate q from
3/2 division, calls submul_1, handles the unlikely correction step.

Something like

 for (...; un--)
   {
     /* Must also handle unlikely case u2 == d1 && u1 == d0 ... */

     u0 = (up[un] << cnt) | up[un-1] >> (GMP_LIMB_BITS - cnt);
     q = udiv_qr_3by2(q, u2, u1, u2, u1, u0, d1, d0, dinv);
     cy = mpn_submul_1(up + un - dn, dp, dn, q);

     if (... correction step needed ... )
       {
         mpn_add_n(up + un - dn, dp, dn);
	 add_ssaaaa (u2,u1, u2,u1, d1,d0);
	 q--;
       }
      *--qp = q:
   }

The hairy thing I see is to compare (and subtract) the carry from the
submul_1 (an unshifted limb) to u2, u1 which are shifted compared to U.
Don't know if one should attempt to avoid redundant computation on the
topmost limbs (like the current mpn_sbpi1_div_qr does), but there's
going to be some bits of overlap in the partial remainder limbs computed
by udiv_3by2 and submul_1.

Does the old division code provide any inspiration?

Regards,
/Niels

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