hgcd1/2

Niels Möller nisse at lysator.liu.se
Tue Sep 3 13:10:58 UTC 2019


tg at gmplib.org (Torbjörn Granlund) writes:

> So I think plain / is the way to go for certain systems!

Then we should use that for the double limb loop too! It gets a bit
tricky, since we need special handling of large quotients, but something
like this should work:

   mp_limb_t q = ah / bh;
   mp_limb_t th, tl;
   if (UNLIKELY (q > bh))
     {
       /* Poor accuracy, q may be more than one unit too small.
          Need normalize bh, and get quotient
          approximation with udiv_qrnnd */
       ...
       /* And this will always be the last double-limb iteration.  */
     }
   else
     {
        ah -= q * bh;
        umul_ppmm (th, tl, q, bl);
        /* Unlikely because th < q, which usually is small */ 
        if (UNLIKELY (th >= ah) && (th > ah || tl > al))
          {
            ASSERT_ALWAYS (q > 0);
            /* Must be one off */
            q--;
            ah += bh;
            sub_ddmmss (th, tl, th, tl, 0, bl);
          }
        sub_ddmmss (ah, al, ah, al, th, tl);
     }

Regards,
/Niels

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


More information about the gmp-devel mailing list