Multiplication of unbalanced operands
Paul Zimmermann
Paul.Zimmermann at loria.fr
Wed Nov 22 18:20:00 CET 2006
> 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
More information about the gmp-devel
mailing list