This is the mail archive of the
libc-alpha@sourceware.org
mailing list for the glibc project.
Re: [PATCH] Another tweak to the multiplication algorithm
On Thu, 14 Feb 2013, Siddhesh Poyarekar wrote:
> Right, it's not really Karatsuba, just that it shares the basic step,
> which is to reduce the equation:
>
> x[i]*y[j] + x[j]*y[i]
>
> to
>
> (x[i] + x[j]) * (y[i] + y[j]) - (x[i]*y[i] + x[j]*y[i])
But for single-word numbers, that basic step is a pessimization - it
substantially increases the number of operations required. It's only an
optimization when the numbers are long enough that multiplications are
much more expensive than additions (and in particular, at some point in
the Karatsuba multiplication, the operations on shorter numbers should be
done in a straightforward O(n^2) way that is faster than Karatsuba on
shorter numbers). If it's faster in a particular case, that seems likely
to be very system-specific, unless you have a more detailed analysis
showing that actually the numbers of both multiplications and additions
have gone down with your approach. It may also indicate that the original
code was doing something silly, as it would be surprising for doing
something more complicated but still quadratic to improve over a
well-optimized implementation of the usual quadratic approach.
--
Joseph S. Myers
joseph@codesourcery.com