a function to get multiplication threshold?

Kevin Ryde user42@zip.com.au
Thu, 19 Dec 2002 07:47:45 +1000

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

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.

You'll probably want to do some measuring to confirm your theory
anyway, and with luck from those a "typical" threshold will reveal

> Thanks, I'll take a look... but these functions are undocumented and
> also not guaranteed to remain in GMP in the future?

True, they're only development tools.  But I'm not in a hurry to make
work by changing things that have been doing their job quite well :-).