Toom-6.5 (Aka: Toom 6'n'half :-P )

[bodrato at mail.dm.unipi.it]

Hi,

> I used it for the Toom-6.5, with points {0, ±¼, ±½, ±1, ±2, ±4, oo}. If
> you want to look at the code, it is on my web-page, as usual:
> http://bodrato.it/software/toom.html#TC6.5

Now I can claim that this code was deeply tested. It contains two main
functions:

- mpn_toom6_n_half_mul(pp, ap, an, bp, bn, NULL)
Computes {pp,an+bn} <- {ap,an} * {bp,bn}
It needs (an >= bn >= 46) and (an*6 <  bn * 17).
It decides at run-time the Toom (6 or 6.5) that fits.

- mpn_toom6_sqr(pp, ap, an, NULL)
Computes {pp,an*2} <- {ap,an}^2
It needs (an >= 40).

/* FIXME: find some more general expressions for 2835^-1, 42525^-1 */
#if GMP_LIMB_BITS == 32
#define BINVERT_2835  (GMP_NUMB_MASK &          CNST_LIMB(0x53E3771B))
#define BINVERT_42525 (GMP_NUMB_MASK &          CNST_LIMB(0x9F314C35))
#else
#if GMP_LIMB_BITS == 64
#define BINVERT_2835  (GMP_NUMB_MASK &  CNST_LIMB(0x938CC70553E3771B))
#define BINVERT_42525 (GMP_NUMB_MASK &  CNST_LIMB(0xE7B40D449F314C35))
#endif
#endif

Suggestions?

Regards,
Marco

-- 
http://bodrato.it/