a function to get multiplication threshold?

Torbjorn Granlund tege@swox.com
18 Dec 2002 23:22:50 +0100

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

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