On Monday 30 October 2006 19:04, Jason Papadopoulos wrote: > > Ernst Mayer assumed the output digits of the product had a size > dictated by the statistics of a random walk. My understanding is that > it's entirely possible to get a digit in the output that's larger than > 53 bits, in which case the convolution will fail even with zero > roundoff error. > Well - random walk seems to be a better model than a (continuous) normal distribution, but there is still a complication caused by the step length doubling when the mantissa increases through 0.999999... causing the exponent to increase by 1.
An alternative model which is easy to describe is like the following game: I toss a fair coin and pay you nothing if it falls heads immediately. If it falls tails k times before the first time it falls heads, I pay you $2^(k-1). How much should you pay me for the privilege of playing this game? Well, your expected winnings are 0.25*1 + 0.125*2 + 0.0625*4 + .... which is clearly an infinite amount. Even if you were to pay me $1,000,000 per game you'd still expect to win in the long term. It's just that I'd almost always win any particular game; in fact, if we were to play thousands or even millions of games, I'd almost always end up ahead. (But, when I did lose, my losses would tend to be astronomical!) Similarly in the FFT it is possible that the errors will all go the same way and we'll round to the wrong integer, it's just that, if we choose the run length sensibly, this problem will occur only vary rarely. And, even if it does, changing the offset for the double check means that the elements generating the errors will be combined differently, making it vanishingly unlikely that the same incorrect rounding will occur at the same point in the double check. Regards Brian Beesley _______________________________________________ Prime mailing list [email protected] http://hogranch.com/mailman/listinfo/prime
