Division call in mpn_gcd

[Torbjorn Granlund]

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

  You're right that the quotient is not wanted, mpn_div_r would make more
  sense, but that function doesn't exist.
  
Indeed it doesn't.  Nor does bdiv_r (for independent dividend and
divisor sizes).

  We don't require that v is odd (maybe it was a mistake to drop that
  requirement?). So to use any bdiv funtions, we'd first have to deal with
  powers of two upfront. And the quotient is still not needed, so I think
  one would want to use bdiv_r, aka redc.
  
Except that redc does not accept independent sizes.  Therefore we need
to use bdiv_qr.

  So I think the right method is:
  
  1. In case both u and v are even, do needed book-keeping for the power
     of two in the gcd.
  
  2. Drop trailing zeros of v.
  
  3. Reduce the size of u using redc. Unlike the use in powm, there's no
     amortization of the inverse computation, so we may need new
     thresholds.
  
Or perhaps slightly differently:

1. Drop trailing zeros of v, keep the count as vcnt

2. If u is even, drop its trailing zeros (might be lazy about that, only
   dropping <= vcnt zeros to save time in this part and keep u > v
   (approximatively u > v, I know this is not the precice mpn_gcd args
   criteria) but I think that's sub-optimal.

3. Now, if u < v swap them (this can only happen if we dropped all u
   zero bits).

4. Your point 3.  Which thresholds are you talking about?

-- 
Torbjörn