Multiplication of unbalanced operands

Marco Bodrato bodrato at mail.dm.unipi.it
Mon Nov 27 17:21:18 CET 2006


Dear Torbjörn,

>   Start: a0+ a1*x + a2*x^2 ; b0 + b1*x

> Do you have the corresponding convenient formulas for 4:2 (using the
> Toom3 interpolation) by any chance?

Start: a(x) = a0+ a1*x + a2*x^2 + a3*x^3;   b(x) = b0 + b1*x

Eval:
v0  =  a0             * b0       # a(0)*b(0)
v1  = (a0+ a1+ a2+ a3)*(b0+ b1)  # a(1)*b(1)
vm1 = (a0- a1+ a2- a3)*(b0- b1)  #a(-1)*b(-1)
v2  = (a0+2a1+4a2+8a3)*(b0+2b1)  # a(2)*b(2)
vinf=              a3 *     b1   #a(\infty)*b(\infty)

Then, you can reuse toom3_interpolate(), with some care on placements.


BTW, it seems you downloaded the latest version of my experiments on toom
at mpz_level. So you have the newly added 5:3 shape with Toom4. Obtained
with small changes on Paul's code. Now the function mpz_tc4 handles either
balanced 4:4 or unbalanced 5:3 multiply... On timings side, perhaps the
stragest point is that: on 5:2 shape, Toom4-5:3 is only a bit slower than
Toom3.5-5:2.

Regards,
Marco

--
http://bodrato.it/


More information about the gmp-devel mailing list