Multiplication of unbalanced operands

[Paul Zimmermann]

> From: Torbjorn Granlund <tege at swox.com>
> Date: 22 Nov 2006 16:51:25 +0100
> 
> Paul Zimmermann pointed out hickups for multiplying unbalanced
> operands, and in discussions with Emmanuel Thom=E9 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.

Marco and Alberto give an efficient way of implementing the 3:2 case,
using 0, infinity, 1 and -1 as evaluation points. Let v0, vinf, v1 and vm1
be the products evaluated at 0, infinity, 1 and -1. If the product is 
c0 + c1*x + c2*x^2 + c3*x^3, we have v0 = c0, v1 = c0+c1+c2+c3,
vm1 = c0-c1+c2-c3, vinf = c3, then perform:

v1  = (v1 - vm1) / 2 # c0+c2
vm1 = vm1 + vinf     # c0-c1+c2
vm1 = v1 - vm1       # c1
v1  = v1 - v0        # c2

Paul Zimmermann