Multiplication of unbalanced operands

[Torbjorn Granlund]

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.

-- 
Torbjörn