Jason writes: > > 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.
B=20 , N=1024K, log2(N)=20 and you are asking for 800 bits??? > > 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. That's neat! > > 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. The rounding errors are presumably now normally distributed with mean zero. If the RMS (standard deviation) of the rounding errors is 0.05, the probability of a rounding error exceeding 0.5 is of the order e^(-50) or 10^-22. Quite adequate for 10^15 rounding operations (one LL-test) to be error free. Putting one more bit into the length of the integer (or its square?) doubles the RMS of the rounding error, giving a probability of ~e^(-12.5) or 10^-6. Totally inadequate! I believe this is the reason the cutoff for the exponent ranges is so clear cut: a small change in exponent size produces a dramatic change in the probabiliy of a rounding error>0.5 Thanks to you and Brian for your help. David _________________________________________________________________ Be one of the first to try Windows Live Mail. http://ideas.live.com/programpage.aspx?versionId=5d21c51a-b161-4314-9b0e-4911fb2b2e6d _______________________________________________ Prime mailing list [email protected] http://hogranch.com/mailman/listinfo/prime
