Multiplication of unbalanced operands
tege at swox.com
Wed Nov 22 16:51:25 CET 2006
Paul Zimmermann pointed out hickups for multiplying unbalanced
operands, and in discussions with Emmanuel Thomé and Pierrick Gaudry
this afternoon, we got an idea how to address that.
Assume U and V are the operands, with U > V.
If U is just a few percent larger than V, pad V with zeros, and
perform a balanced multiply.
If U's size and V's size are close to a size relation m:n for m, n
small, split U in m pieces and V in n pieces, do any needed zero
padding, and perform m*n smaller balanced multiplies.
Interesting m:n relations might be 3:2, 4:3, 5:3, 5:4.
But if we really perform m*n smaller balanced multiplies, we might not
see much improvements, except possibly for 3:2. What is really needed
are Toom-ish algorithms for these ratios.
Are there such algorithms already designed? I'd be very interested in
any input you might have about that.
More information about the gmp-devel