brainwagon

Well, my excursion into FFT multiplication the other day left me with some more interesting questions, including trying to find out more information about the integer version of the FFT called the NTT (number theoretic transform). Instead of computing the transform to an orthogonal basis consisting of the complex roots of unity, the NTT transforms to a basic formed by discrete vectors over an orthogonal basis consisting of the primitive roots of some prime power. Any of that make any sense to you? Yeah, it’s pretty hard going for me too, requiring me to dust off some of my number theory knowledge that has been dormant for quite some time. But while digging, I found this link:

Jörg’s useful and ugly FXT page

Jörg Arndt is working on a textbook which appears chocked full of good stuff that actually has to do with computing things (as opposed to the stylish modern trend of merely using gigaflops of compute power to wait for mouse clicks). Very neat stuff: I suspect that if I read the chapter on the NTT a few more times, I’ll have it figured out.