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:
> 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.
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).
--
Joseph S. Myers
joseph@codesourcery.com