sqrt algorithm

[Torbjörn Granlund]

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