a function to get multiplication threshold?

Serge Winitzki serge@cosmos.phy.tufts.edu
Tue, 17 Dec 2002 01:25:28 -0500 (EST)


I was trying to see at what precision GMP is starting to use
subquadratic multiplication and realized that this is currently an
implementation detail that is not exposed to the users. However I think
it's a useful piece of information to have. I have been writing
arbitrary-precision algorithms for various special functions and there
is frequently a choice between algorithms that depends on the speed of
the multiple-precision multiplication. For $n$ bits of precision, one
algorithm may cost $O(n^2)$ or $O(n^2 \log n)$ operations and another
algorithm may be $O(M(n)\log n)$ where $M(n)$ is the cost of a
multiplication or a squaring with $n$ bits. One cannot make a good 
choice between the algorithms without knowing the cost of 

It is clear that there are many multiplication algorithms and it would
be impractical to expose all thresholds. But I think that in most cases
it is enough to know whether $M(n)$ is faster than $O(n^2 / \log n)$. In
other words, it would be good to have a macro or a function to get the
former is probably always larger than the latter), multiplied by the 
number of bits per limb.