Tuning

[Torbjorn Granlund]

Josh Liu <zliu2 at student.gsu.edu> writes:

  I have a working multiple precision arithmetic library that I have written
  over the last six months. It is based upon the threshold system that GMP
  uses to partition the effective algorithm used for certain input sets. What
  is the best way to find these thresholds? I know that a binary search is
  definitely out of the question as the inaccuracies make the comparison
  function poorly defined. How does tuneup work? I want to know how the
  precision parameter comes into play as well. The other possibility is to do
  curve fitting of the time function and solve for the thresholds. This
  possibility would reduce the inherent inaccuracies by working with well
  behaved functions, instead of the inaccurate and seemingly random nature of
  empirical timing.
  
The current GMP tuneup steps towards larger and larger operands,
adding one limb (or a few limbs) for each measurement.  Then when
the algorithm with better complexity gets faster, some magic is
done to determine where to put the cutoff point, by minimizing a
"badness" metric.  Kevin knows more.

I think some sort of least squares approximation would be the
best way to do this.  Also, I think one would want to start with
large steps, then do a least squares approximation, then tak
smaller steps around a preliminary cutoff determined from the
previous least squares approximation.  This process would then be
iterated a few times.

-- 
Torbjörn