a function to get multiplication threshold?

[Torbjorn Granlund]

Kevin Ryde <user42@zip.com.au> writes:

  Serge Winitzki <serge@cosmos.phy.tufts.edu> 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
significantly.

  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.  :-)  

-- 
Torbjörn