Multiplication of unbalanced operands [Toom]

[Marco Bodrato]

Dear Torbjörn,

On 22 Nov 2006 16:51:25 +0100, Torbjorn Granlund wrote
> Interesting m:n relations might be 3:2, 4:3, 5:3, 5:4.
[...]
> 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.

Yes, there are algorithms for n:m, in our paper we call them
Toom-(n+m)/2 . So, the algo you are looking for are all described
in the paper. They are named this way:

Ratio  Name in Paper   #of balanced multiply
3:2 -> Toom2.5         4
4:3 -> Toom3.5         6
5:3 -> Toom4  !!!      7
5:4 -> Toom4.5         8
...and remember...
4:2 -> Toom3           5 (1/4 size)
2:1 -> straightforward 2 (1/2 size) meaning, with kara, 6 (1/4 size)
... and so on...
5:2 -> Toom3.5


I'll explain in some detail 5:3 -> Toom4.

Let's start from a = [a4,a3,a2,a1,a0] and b= [b2,b1,b0], we want to compute
c = [c6,c5,c4,c3,c2,c1,c0] = a*b.

>From our paper you can take the sequence:
- consider the two polynomials A(x) = a4*x^4+...+a0 , B(x)=b2*x^2+...+b0
- compute C(0) = A(0)*B(0), C(1), C(-1), C(2), C(-2), C(1/2), C(\inf)
- use inversion sequence for Toom4, obtaining values c6,c5,...,c0 to combine

The only tricky notes are that:
- C(\inf) = A(\inf)*B(\inf) = a4*b2
- C(1/2)  = A(1/2) *B(1/2)  = (a4+2*a3+4*a2+8*a1+16*a0)*(b2+2*b1+4*b0)

You can use _exactly_the_same_code_ as for the inversion used in Toom4. 
All maximal and minimal values computed for any intermediate value are
still valid. But, as Paul noted, you have to change "evaluation" code.

You could borrow the evaluation code for A(x) from Toom5 and extend the
code taken from Toom3 for B(x)... but I do not know if that's easy.

Regards,
Marco