Hi all, I've been working away at this new FFT I've been writing (for 2 years).
There's a multitude of functions, FFT, IFFT, truncated FFT and IFFT, matrix fourier algorithm FFT and IFFT and truncated matrix fourier algorithm FFT and IFFT. Each of these needs a new version which handles the sqrt2 trick. So there's lots of FFT's to write. Then there's test code for each pair. In total there's four new butterflies that I needed to handle sqrt2, two for the ordinary FFT's (truncated or otherwise) and two for the mfa FFT's (truncated or otherwise). I've managed to complete the first two of those. I've done the sqrt2 versions of the ordinary FFT's and most of the code for the two versions of the mfa FFT's. Already I can get some timings of integer multiplications. On my machine the MPIR FFT kicks in at about 160,000 bits. Because there are no iterative versions of the FFT's and IFFT's (yet another pile of functions that need writing) the new code is slightly slower, about 5-10% I think. >From about 260,000 bits onwards the new code very slowly starts to win. At 66,000,000 bits the new code is 50% faster and it tapers off to about the same speed at integers of about 4,000,000,000 bits (or at least it will when I finish off the sqrt versions of the mfa FFT's). Still a lot of work to do. To keep ahead of MPIR for very large multiplications we'll need fast Nussbaumer convolution code. I've written most of that, but I still need some convolutions with word sized coefficients and possibly double word sized coefficients and some CRT code which will combine these convolutions with the Nussbaumer FFT convolution code. Some of these various FFT's and IFFT's need to be combined so there aren't quite so many functions. Anyhow, it's conceivable that by the end of this coming week I'll have all the FFT's and IFFT's working and all that will remain is the Nusbaumer convolution stuff. I'll keep everyone updated as I go. Bill. -- You received this message because you are subscribed to the Google Groups "mpir-devel" group. To post to this group, send email to mpir-devel@googlegroups.com. To unsubscribe from this group, send email to mpir-devel+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/mpir-devel?hl=en.
