Quoting John R Pierce <[EMAIL PROTECTED]>: > the FP numbers used are double precision (64 bit) which have ~48 bits of > mantissa, so the 1 million bit FFT size is, I believe, broken into 48 > bit chunks, about 21000 of them?
Without balanced representation, if you have a transform of size N and each element has B bits, then each element of the product must have room for an integer with 2*B*log2(N) bits. Ordinary double-precision floating point has a 52-bit mantissa, so ignoring roundoff error B and N have limits to avoid getting a corrupted answer. With balanced representation, each element to be transformed is represented as an integer between -B/2 and B/2. Because double-precision allocates a bit for the sign of the answer separate from the mantissa, this means you get two more bits for free when calculating the maximum transform length. However, the big difference between standard and balanced representation is in the error analysis. When all FFT elements are positive, errors accumulate in a relatively predictable way. With balanced representation, approximately half of all errors are positive and half are negative. When they're added together, the average error is zero. This puts us in the weird position where 2*(B-1)*log2(N) can actually be allowed to exceed the size of the mantissa and we can still expect to get the correctly rounded digits of the answer with overwhelmingly high probability. For an analysis, see 'The 24th Fermat Number is Composite' by Crandall, Meyer and myself. As an example, years ago I wrote a fast hartley transform based convolution with a fixed digit size of 16 bits per element. With balanced representation you could perform multiplies of size 2^27 and still get roundoff errors that were strictly less than 0.25. Now, it would technically be possible to perform a convolution where some portion of the answer would exceed 52 bits in absolute value, but this is so unlikely that it isn't worth worrying about (as long as an extremely rare wrong answer could be tolerated, or you have a double-check of some sort available) 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
