GMP 4.3 multiplication performance

[Niels Möller]

bodrato at mail.dm.unipi.it writes:

> Toom43 exists too! I announced it on this list some months ago :-) but the
> list was silent that times:
> http://gmplib.org/list-archives/gmp-devel/2009-February/000818.html .

Cool. I missed/forgot that. I've spent a few hours on
toom_interpolate_6pts, using a sequence basically taken from your
paper but with slightly different signs, to avoid explicit negation
operators:

     w0 = f(0),
     w1 = f(1),
     w2 = f(-1)
     w3 = f(2)
     w4 = f(-2)
     w5 = limit at infinity of f(x) / x^5,
     
     w1 -= w2
     w3 -= w4
     w3 /= 2
     w4 += w3
     w4 -= w0
     w3 -= w1
     w1 /= 2
     w2 += w1
     w2 -= w0
     w3 /= 6
     w4 -= 4 * w2
     w3 -= 4 * w5
     w1 -= w3
     w4 /= 12
     w2 -= w4
     w3 -= w5

But I didn't waste too much time; I haven't spent the time needed to
test, debug and optimize my interpolation function.

One comment on your interpolation function: You don't need any scratch
space. But then for the operation

  /* W2 =(W2 - W4)/3 - W0<<2 */

you use mpn_submul_1 with a constant multiplier of 4, which I imagine
is more costly than a shift. toom_interpolate_7pts has the same
problem, and that code does the opposite, it uses mpn_lshift to a
scratch area followed by mpn_sub_n.

I'm not sure what's fastest, but it's definitely annoying that you
can't shift without using a scratch area.

Regards,
/Niels