On Thu, Dec 31, 2009 at 9:04 PM, Bill Hart <goodwillh...@googlemail.com> wrote: > 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.
I'm personally eagerly awaiting (3), since I've been watching you work on this for a while. I'm sure there is an excellent argument for (3), and I'm curious what it is. > 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. I hope you list things that failed too. > 5) References. Few. I purposely tried to be creative. Your numbering is creative, in that you went from 5) to 8) below. > > 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. > > > -- William Stein Associate Professor of Mathematics University of Washington http://wstein.org -- 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.
