Yes, I've seen it before. Don't use the FFT multiplication routines in it for integer computations that require proven results. He uses a real FFT subject to roundoff error, with a sum of digits test, which is not proven. There is an option to switch to NTT's which are 4 times slower, but these are not competitive with the SSA implementation of Gaudry, Kruppa, Zimmermann in MPIR.
There is also disk based convolution code which is the main reason I have investigated it before. Not a huge big deal, but fxt is licensed under GPL v3, so it cannot be used at MSR, and should not be included in any version of Sage which is intended to be used by them, and obviously it cannot be used in LGPL projects or GPL v2+ projects. It is useful to have all the descriptions of the various FFT algorithms available in one place. These are described at an introductory level, with a few references in each case. It is hard to comment on the quality or performance of the code, as I have not run any of it and only inspected a small portion of it. From what I have actually inspected, it appears to be competently written and well commented. It also appears that a lot of effort over a long period of time has been invested in the library as a whole. It doesn't appear to be insanely optimised, but does appear to use a lot of standard tricks. Of course this is just the hurried opinion of one (relatively ignorant) individual. The best way to get an idea of what it is like in practice is to check it out and give it a whirl. I'd be interested in hearing how that goes or if others have actually used the program in serious work and have comments on it. Bill. On Dec 11, 4:13 am, Jason Grout <jason-s...@creativetrax.com> wrote: > William Stein wrote: > > Hi Sage-Devel, > > > Have you ever wondered about the mathematics behind how MPFR, GMP, > > MPIR, etc., work under the hood? Fortunately, Paul Zimmerman and > > Richard Brent just published a new very-accessible book about exactly > > this, and has the foresight to release their book under a Creative > > Commons license (in addition to publishing it in traditional book > > form). > > > "Modern Computer Arithmetic" > > > http://www.loria.fr/~zimmerma/mca/mca-0.4.pdf > > While browsing this book's pages, I was led to the FXT library: > > http://www.jjj.de/fxt/#fxt > > Does anyone know anything about it? Can you comment on it? > > It's GPL, in C++, and has a Linux Software Map description of: > > fxt is a library package implementing various algorithms for: > Fast Fourier Transform (FFT), complex and real-valued, > Fast Hartley Transform (FHT). Convolution (cyclic, linear and > weighted), correlation and power spectrum. > Mass storage convolution and fast multiplication routines. > Number Theoretic Transform (NTT), Walsh Transform, > Reed-Muller transform, Haar Transform, Wavelet Transform. > Combinatorial generation: Combinations, Permutations, subsets. > Sorting, Searching, Stack (FIFO), Queue (LIFO), heap and priority-queue. > Bit-manipulations, shift registers (LFSR), modular arithmetics and > computations in binary finite fields GF(2**n). > > It looks like it is fantastically documented, with a 1000 page reference > manual that explains the algorithms. > > Thanks, > > Jason > > -- > Jason Grout -- To post to this group, send an email to sage-devel@googlegroups.com To unsubscribe from this group, send an email to sage-devel+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/sage-devel URL: http://www.sagemath.org
