sqrt algorithm
Torbjörn Granlund
tg at gmplib.org
Mon Jul 20 17:20:53 UTC 2015
nisse at lysator.liu.se (Niels Möller) writes:
To make this fast, we need some variant of divappr_q which don't require
any of the uninteresting low limbs. Or alternatively, resurrect the
notion of fraction limbs.
I would say that padding out the numerator and use divappr_q won't be
the make-or-break for the algorithm. It might not be pretty, but except
for perhaps < 10 limbs it will be hard to measure the added cycles.
Compare to bdiv_q functions, which computes N / D mod B^n, where both
inputs and the output are n limbs. A divappr_q function ought to compute
an approximation of N B^n / D, but possibly with a little mmore
flexibility in the input and output sizes.
The most flexible way is perhaps to mimic the "fraction
limbs"-interface. Say we have inputs N = {np, nn}, D = {dp, dn}, and a
scaling factor k, and compute an approximation of
Q = floor (N B^k / D)
of qn = nn + dn + 1 + k limbs. Or we could tie things together a bit
more, by requiring that dn = nn = qn + 1 or so.
I haven't thought carefully about this, but we should probably provide
plain fllor(n/q) functions as the main entry points. We could then add
fraction limb development functions as a parallel set.
--
Torbjörn
Please encrypt, key id 0xC8601622
More information about the gmp-devel
mailing list