Tuning
Torbjorn Granlund
tg at swox.com
Thu Jun 17 14:01:51 CEST 2004
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
More information about the gmp-discuss
mailing list