> > > Grr, that was a mistake. It should be 2*B+log2(N) and 2*(B-2)+log2(N) > > > for ordinary and balanced representation, respectively. > > Nitpick: my response should have used 2*(B-1)+log2(N)
I thought so, > > > > 56 bits is nearer the mark! 58 bits isn't far off either > > I assume statistics along the lines I suggested (normal distribution) > > explains the 4 bit discrpancy. Or is it the varying integer length of > > a weighted transform? > 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. > > jasonp N steps of +/- 1 chosen at random gives a normal distribution. The maximum possible is N but the standard deviation is SQR(N). This suggests replacing log2(N) (depth of the butterfly tree FFT) with log2(N)/2. This gives 48 bits for a roughly evens chance of a roundoff error. The extra 5 bits decrease the probability of error as desired. Is this as plausible as it sounds? 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
