On Thursday 14 December 2006 14:05, david eddy wrote: > Quote from the "Math" page > << > There is another error check that is fairly cheap. One property of FFT > squaring is that: > (sum of the input FFT values)^2 = (sum of the output IFFT values) > Since we are using floating point numbers we must change the "equals sign" > above to "approximately equals". > > > If we were workong to infinite precison, shouldn't the output IFFT values > be integers?
Yes. > > In which case rounding these values to integers before summing them should > provide exactly the stringent checksum we want? Yes. But in any case it's a moot point because the (input) "phase space" values aren't integers, and adding (FFT run length) strictly positive values together is likely to cause a loss of precision even if they were. (Run length = 2^20 is likely to lose about 20 bits of precision in the sum, compared with the precision of the inputs, if you're thinking in fixed point terms. When working in floating point, you won't actually get a wraparound type error like integer overflow, but you do lose the least significant bit of the mantissa every time you add two values with the same sign and the same exponent as the exponent of the result has to increase.) In fact, as the FFT run length increases, the checksum criterion becomes increasingly poor as a predictor of accuracy compared with the roundoff error check criterion, as the imprecision of the checksum is proportional to the logarithm of the number of elements in the computation whereas the roundoff error increases much more slowly. Also, the "special features" of the transform used for the L-L test give us the "subtract 2" part of the L-L algorithm for free; this may interfere in some way with the exact equality mentioned in the basic theory. Regards Brian Beesley _______________________________________________ Prime mailing list [email protected] http://hogranch.com/mailman/listinfo/prime
