On Tue, Oct 24, 2006 at 09:03:29PM -0400, Jason Papadopoulos wrote: > 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.
Well, at least of circular convolutions, but all convolutions calculated via the FFT are circular in some sense, so yes. > 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. Speaking of which; what kind of FFT does Prime95 compute? (I'd normally guess it's a Cooley-Tukey variant, but you never know with George's magical assembler, and I have no idea about DIT/DIF and radices :-) ) > 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. Well, there's the magic part :-) But thanks, it's a bit clearer now. /* Steinar */ -- Homepage: http://www.sesse.net/ _______________________________________________ Prime mailing list [email protected] http://hogranch.com/mailman/listinfo/prime
