hgcd1/2

Torbjörn Granlund tg at gmplib.org
Tue Sep 3 10:39:41 UTC 2019


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

  count_leading_zeros (ncnt, n0)
  count_leading_zeros (dcnt, d0)
  ni = ... extract high k bits from n0 ...
  di = ... extract high \ell bits from d0 ...
  q = qtab[ni<<\ell+di];
  ... adjust ...

Well, perhaps

  q = qtab[ni<<\ell+di] << (ncnt - dcnt)

is closer.

  if (n0 >= (d0 << 3))
    q = n0 / d0;
  else {
    q = 0;
    if (n0 > (d0 << 2))
      q += 4
      n0 -= d0 << 2
    if (n0 > (d0 << 1))
      q += 2
      n0 -= d0 << 1
    if (n0 > (d0 << 0))
      q += 1
      n0 -= d0
    }

All '>' there should be '>='.

-- 
Torbjörn
Please encrypt, key id 0xC8601622


More information about the gmp-devel mailing list