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 06:11:22PM +0000, Joseph S. Myers wrote:
> On Thu, 14 Feb 2013, Siddhesh Poyarekar wrote:
>
> > 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.
>
> The reference I have to hand (Brent and Zimmermann, Modern Computer
> Arithmetic) suggests that for multiplication below the Karatsuba range you
> should use a simple algorithm in which the fundamental operation to
> optimize is multiplying an array of words by another word and accumulating
> the result in another array of words - not anything involving more
> complicated tricks as in your patch. In GMP's lowlevel interface that
> fundamental operation is mpn_addmul_1.
>
A choice of range depends how good you optimize smaller multiplications.
Optimizing small no is quite tricky if you want effectively use avx.
You for fixed size expand loop and with shuffles try to rearange multiplicantions (Possibly using karatsuba)
it in no logical order to maximize troughput.
A of generic karatsuba depends on how good was optimization above.
> Unless you have evidence from other implementations of multiple-precision
> arithmetic that the tricks in your patch form a useful part of optimal
> implementations in some range, I'd suggest looking elsewhere for causes of
> slowness in the mpa code (and maybe even considering reimplementing it in
> terms of the __mpn_* functions from GMP that are included in libc,
> although any partial conversion to those functions might be inefficient
> because of converting between different representations of
> multiple-precision numbers - the mpa one, and the GMP array of limbs).
>