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