On Friday 27 October 2006 02:31, david eddy wrote: > > > > You seem to be assuming that > > > > a) all iterations will have the same probability of rounding error, and > > that b) the probabilities are independent. > > > > I'm not sure if I want to accept any of those off-hand, especially as the > > end result doesn't go well with real-life data. > > > > /* Steinar */ > > Under very general assumptions: > The chance of 30,000,000 successful iterations is zilch unless each > iteration is practically a certainty.
Given allowance for imprecise wording this statement is pretty well accurate. However the unit is actually not per iteration but per floating point operation. The number of floating point operations per iteration is a step function as it is dependent on the FFT run length, but is clearly comparable to the number of iterations per L-L test. So th number of places that an error can occur, for an exponent around 30,000,000, is something of the order of 10^15. (Yeah, there's a multiplier in there, and a complication caused by the FFT being done in multiple phases for various reasons e.g. memory organisation, but I think you should get my drift.) So, if e is the error rate per floating point operation, then the probability of the L-L test being correct is of the order of (1-e)^(p^2). Which, as David points out, tends to zero very rapidly as e increases from infinitesimal values. Coming back to Steiner's point (a), the uniformity of rounding error rate across all iterations is clearly incorrect. You can pick a ludicrously small FFT run length and still get away without errors in the first few iterations - because we start with a small number (4) it takes of the order of log (run length) iterations before rounding errors _can_ occur. As for (b); this is also an unfounded assumption though I'm not sure it's important except for exact calculation of the relative probability of an error in an operation affecting the result for an iteration and/or the final result. Which is something of a moot point. Accuracy of a FFT convolution seems to be dependent on the distribution of 0 & 1 bits in the mantissae of the floating-point elements of the deconvoluted work vector being "not too random". If there is a totally random distribution then sometimes the transformations will run into rounding errors & sometimes they won't. If we pick a sufficiently large run length & run a few thousand iterations we can start to examine the raw rounding errors as the difference between floating-point values as stored and the nearest integer (we know the deconvoluted values _must_ be integers). Then, with the experience we have, we can say that if the average rounding error is less than a critical value, it is unlikely that we have rounded any FP values to the wrong integer (which is the true cause of the rounding error). If we find the average error is too high then the best thing to do is to abandon and start again with the next bigger run length. This computation is expensive so we save time by omitting it for exponents which are well below the sane upper bound for a particular run length. > > The point I have been trying to make is that IF the probability of an > erroneous LLtest for a particular exponent were say 5% for a particular > FFT length, then it would cost more time to test and check it using a > 20% larger FFT (with negligible chance of error). > We may still prefer not to risk the 5% chance of error on a first time > LL test, but anyway the number of exponents involved in the debate > is negligible since the chance of error rises so abruptly from zero to 100% Sure, but with all the work which has been done (including analysis of many, many actual results where roundoff errors were detected and corrected as well as results which were apparently OK) the selection of run length for optimum performance is still something of an art rather than a science. If we plot average, or maximum observed, rounding error at, say, iteration 1000 against exponent for a fixed (but reasonable) run length, we do not get a smooth monotonic rise, as logic would expect - rather a graph suggestive of white noise superimposed on an exponentially rising trend line (but clipped at y=0.5 because of the way the error is measured!). For a small range of exponents, even around the FFT run length cutoff point, the "noise" actually dominates the underlying trend. I'm not saying that a modest efficiency improvement couldn't be achieved by tinkering with (generally reducing) run length cutoffs. However I believe that anything which could be done would be marginal to the project as a whole - well under 1% - and could easily be offset by the psychological effect on users of returning excess "bad" results for reasons outside their control. Regards Brian Beesley _______________________________________________ Prime mailing list [email protected] http://hogranch.com/mailman/listinfo/prime
