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, Feb 14, 2013 at 01:19:32PM +0000, Joseph S. Myers wrote:
> 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.
No, your analysis is spot on w.r.t. the number of operations being
larger; 1.5x in fact, so I don't have any analysis that says
otherwise. The reason this works though, is that most numbers falling
into the slow path will have a large enough number of digits. If
there is a computation that requires less number of digits (say, < 4
in mp_no) then it should never get into the mpa code since the fast
paths should take care of them.
Siddhesh