Side-channel silent division
tg at gmplib.org
Wed Nov 14 10:33:54 CET 2012
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
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.
More information about the gmp-devel