Side-channel silent division

[Torbjorn Granlund]

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

  Torbjorn Granlund <tg at gmplib.org> writes:
  
  > Any opinions on this approach?
  
  Makes sense to me. I can see some alternative ways to avoid the initial
  quotient adjustment (udiv_qrnnd_preinv), but to avoid handling carry out
  from the update of the partial remainder, I see no way besides using a
  quotient smaller than a full limb.
  
  If we can arrange for a loop which does a full quotent limb, and applies
  it using mpn_submul_1 followed by an mpn_add_cnd_n per quotient3B, would
  that be faster or otherwise preferable to your loop with two submul_1
  per quotient limb?
  
"Quotient3B"?  Is "3B" a typo for " limb"?  :-)

A loop around submul_1 + mpn_addcnd_n would get a smaller n^2 term on
almost all machines, I think.  I am not sure the linear n term would be
improved, it might in fact become somewhat worse.

I considered something hairier that got us almost a quotient limb per
iteration, but ended up with lots of lshift calls.  I didn't make a real
effort.

I suspect an SB based on tese ideas could actually beat the current SB
code for small operations, since there the linear term is not dominated
by the quadratic term.  We could save some constant time by computing te
limb inverse sloppily.

-- 
Torbjörn