a function to get multiplication threshold?
18 Dec 2002 23:22:50 +0100
Kevin Ryde <firstname.lastname@example.org> writes:
Serge Winitzki <email@example.com> writes:
> I think this is too much work for what it's worth. For me, the reason
> for using the rough thresholds like the MUL_THRESHOLD instead of
> independent measurements is not to get an extra 10% speedup but to avoid
> an a priori 300% slowdown.
It's worth bearing in mind that often-quoted things like O(n^2) are
only mostly true in practice. At small sizes there's fixed overheads
and a significant linear term, and when Karatsuba is used for only one
or two recursions it's nothing like O(n^1.585).
A good point.
We're of course really abusing the O() notation in this
discussion. To speak about what O() GMP multiplication
has for 45-limb numbers is dubious. It takes a constant
amount of time, dammit!
It would of course be possible to give a function for the
number of various elementary operations required for a
n-limb multiplication, and then another function derived
from that with cycle times for the various elementary
operations. But that latter function would only be a rough
approximation to run time for n-limb multiplication.
Caching effects, branch predication accuracy, and various
sources of bookeeping costs, will affect the timing very
Those sort of considerations have lead us to what might be called a
positivist approach, by which we measure things we want to optimize,
rather than trying to proceed from theory.
I couldn't have put it better myself. :-)