Quoting "Steinar H. Gunderson" <[EMAIL PROTECTED]>: > /* Steinar */ > - who was been on the list for almost ten years now, and still doesn't > understand the magical trick to halve the FFT length :-/
Coding it is tricky, but understanding why it works isn't too hard. If you multiply two N-digit numbers you get a 2N-digit product. This is called a convolution. If you then insist that the answer fit in N digits, then the high-order N digits 'wrap around' and get added to the low-order N digits. That's just a property of convolutions. Arithmetic modulo a mersenne number behaves in exactly the same way. Multiplication mod (2^p - 1) is equivalent to forming the 2p-bit product and wrapping the high p bits around, adding to the low p bits. Hence a convolution will do Mersenne-mod arithmetic when N = p. The problem is that when p is big, you want the convolution to be performed via FFT methods, and getting the automatic wraparound requires an FFT of a prime number of elements. While that's possible and even can be made efficient, it's much more efficient to do the convolution when the FFT size is highly composite. The Discrete Weighted Transform basically does that. It's a way to pack a prime number of bits into smaller number of 'words', using a 'variable-base' representation. Once you've done that, your convolution can use FFTs of the array of *words*, which is efficient (you get to pick the number of words, and it may as well be a number of words for which FFTs execute efficiently), and convolutions will still wrap around and give you a mersenne mod for free. The only wrinkle is that some of your words will have X bits and some will have X+1 bits, and this requires a correction in order for the FFT to work. Basically, all of this is not a trick to halve the length, but a trick to avoid doubling the length, i.e. forming the 2p-bit product. jasonp ------------------------------------------------------ This message was sent using BOO.net's Webmail. http://www.boo.net/ _______________________________________________ Prime mailing list [email protected] http://hogranch.com/mailman/listinfo/prime
