2010/1/3 David Harvey <[email protected]>: <SNIP> > See the recent discussion on the GMP list, for > example the thread > > http://gmplib.org/list-archives/gmp-devel/2009-October/001053.html
Interesting discussion. Seems they've reached the same conclusions as me regarding the "dyadic product" business. But I actually thought this was why the MPIR FFT was fast for small coefficients, because we already have this mpn_mulmod_2expm1, which Jason implemented. The issue with the principal roots of unity for the pointwise multiplications mod 2^2B-1 is precisely the issue I hit with the radix 3 FFT. It probably does stop you doing an FFT for the 2^B-1 part of the "dyadic product". But I'm not even up to that problem yet. And I don't see that one would even want to do an FFT for that part of the product. Simply keep splitting, as MPIR's hypothetical mpn_mulmod_2expm1 does. Eventually everything is a multiplication modulo 2^B+1 for some sized B or a very small multiplication mod 2^B-1 which you just perform using classical or Toom multiplication. I suppose in the Toom range one can save a little bit of effort by working out how to get it to wrap around automatically. But as we are about to replace all the toom code with something completely different, I've decided to hold off on looking into that. I don't think you could save much anyway. Bill. -- You received this message because you are subscribed to the Google Groups "mpir-devel" group. To post to this group, send email to [email protected]. To unsubscribe from this group, send email to [email protected]. For more options, visit this group at http://groups.google.com/group/mpir-devel?hl=en.
