As the code for this FFT is quite involved, I plan to incrementally release a set of notes about it, starting tomorrow morning (today already), which may take hours to days for me to complete. I got the code working for the first time this afternoon, so please be patient with me.
Here is the rough list of topics I hope to cover in the notes: Table of Contents ============= 1) The formal code release. I need to check all the test code still passes and make it easy for people to build and run. That will take an hour or so for me to do. 2) FFT's for nitwits (like me). How does an FFT help in multiplying numbers, basically, and what are the important algorithms and techniques. 3) Why a new FFT? This is an important question which needs answering. I will discuss what led me to work on a new FFT implementation, rather than improve or port another implementation. 4) The strategy. What does this FFT actually do? Which algorithms does it use? I tried many things, most of which completely failed. In section 3 I will have already discussed other strategies I tried which did not work. Here I will discuss what did work. Whilst many of the details came from my head, I'm pretty sure the general outline will contain few surprises. 5) References. Few. I purposely tried to be creative. 8) Implementors notes. A long list of things that can be improved. In releasing the code publicly it is my hope that contributors will help make this the best FFT implementation it can be. The list will include many trivial items which anyone could work on, all the way through to fairly advanced topics which would probably require original research to do really well. I'll rank the items according to how hard I think they'd be to do. The code will be under revision control, so it is my hope that people will be willing to contribute to it. I believe I spent between 150 and 200 hours writing it, all told. Till tomorrow. Bill. 2010/1/1 Bill Hart <goodwillh...@googlemail.com>: > Ha! I forgot to mention, those numbers represent the size of the > integers in bits. I multiply two different integers with the same > number of bits, though that is not a limitation of the code. It will > accept integers of different lengths and adjust accordingly. > > Bill. > > 2010/1/1 Bill Hart <goodwillh...@googlemail.com>: >> I re-timed that point and I believe I may have just mistranscribed it. >> Here it is with the corrected time. Thanks for pointing it out! >> >> I've also included some times from the FLINT FFT, though only >> non-truncated ones (i.e. where FLINT uses a convolution which is an >> exact power of 2 length - not a limitation of FLINT, I just didn't get >> around to timing it at the other points yet). >> >> 8364032: 6.8s / 8.0s >> 9409536: 9.8s / 8.7s >> 10455040: 10.8s / 9.6s >> 11500544: 12.3s / 12.6s >> 12546048: 12.7s / 15.3s >> 13591552: 14.0s / 14.2s >> 14637056: 14.9s / 15.3s >> 15682560: 16.0s / 14.5s >> 16728064: 16.8s / 19.5s >> >> 20910080: 24.3s / 23.2s >> 25092096: 28.5s / 33.1s >> 29274112: 33.1s / 31.8s >> 33456128: 37.4s / 47.7s >> >> 519168: iters 10000: 30.7s / 32.2s / 32.3s >> 2084864: iters 1000: 13.9s / 15.2s / 13.0s >> 8364032: iters 100: 6.8s / 8.0s / 7.6s >> 33497088: iters 100: 37.4s / 47.7s / 37.5s >> 134103040: iters 10: 17.0s / 24.8s / 19.6s >> 536608768: iters 1: 8.6s / 9.4s / 8.6s >> 2146959360: iters 1: 42.3s / 40.3s / 38.9s >> >> Bill. >> >> >> 2009/12/31 Bill Hart <goodwillh...@googlemail.com>: >>> It's either a tuning issue or timing instability on the machine. >>> >>> Bill. >>> >>> On 31/12/2009, Robert Gerbicz <robert.gerb...@gmail.com> wrote: >>>> Hi! >>>> >>>> How is it possible that to multiple longer numbers takes less time, for >>>> example: >>>> >>>> 12546048: 14.7s / 15.3s >>>> 13591552: 14.0s / 14.2s >>>> >>>> -- >>>> >>>> You received this message because you are subscribed to the Google Groups >>>> "mpir-devel" group. >>>> To post to this group, send email to mpir-de...@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. >>>> >>>> >>>> >>> >> > -- You received this message because you are subscribed to the Google Groups "mpir-devel" group. To post to this group, send email to mpir-de...@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.
