On Monday 11 December 2006 13:32, david eddy wrote: > > It does seem a pity that we can't use the output of a LL test proving > a number composite to help in some way with finding factors.
In practise we don't find recurrences in the first p iterations. However for small exponents (say less than 2000) it is realistic to run hundreds of millions of iterations in the hope of finding recurrences. I did this a few years ago with a few small exponents which then had no known factors without finding any recurrences. But the point is that there are many chains of residues which repeat in short periods - in particular 0, -2, 2, 2, 2, ... and +1, -1, -1, -1, ... which both work for _any_ p>1 - which suggest that R(n+1) = R(n)^2 - 2 (mod 2^p-1) is not a particularly satisfactory pseudorandom number generator. Look at it another way. In general there will be either two or zero values of R such that R^2-2 (mod 2^p-1) is equal to any particular value. We can't enter a "forbidden state" so, every time we run an iteration, our solution space is likely to be halved. > > These are the numbers I take to be "pseudo random" although I don't think > this is necessary to produce normally distributed roundoff errors. Well if the whole series is a poor PRNG then the elements must also be so... > > I wish someone would step in and help here. We seem to be > at loggerheads due to some mutual misunderstanding. > It sounds to me as if you think you have found a counter example > to the Central Limit Theorem :-) No. The Central Limit Theorem states that if a number of samples are drawn from independent distributions then there is a tendency for the sum of the samples to approximate to a sample drawn from a normal distribution. Unfortunately we are not combining samples in this way. Therefore the CLT appears to be inapplicable. > It is the signed actual roundoff errors which I maintain are > normally distributed with mean zero. 1. The signed actual roundoff errors are drawn from a discrete not a continuous distribution. 2. The Central Limit Theorem does not apply because the individual outliers are exactly that, not some combination of independent data points drawn from similar distributions. 3. The difference between possible values varies in a non-uniform way - think of this as graininess increasing as the effective number of guard bits drops. 4. Occasionally the number of guard bits may drop so far that the graininess of the round-off error "sample" drops to 0.125, 0.25, possibly 0.5 or even worse 1.0 if we're really unlucky with the contributory values in "phase space" and have been too optimistic with our choice of run length. 5. Because of the graininess effect, the rarity of these events doesn't seem to be amenable to arguments based on standard deviations from an assumed underlying normal distribution. At the very best we have to deal with a curve which periodically halves its height but doubles its length e.g. what appears to be a safe 12 s.d. from the mean may in fact only be a distinctly dodgy 6 s.d. or a completely unsafe 3 s.d. away depending on how many steps in the exponent have been crossed. (6 s.d. is dodgy because we are dealing with a sample size of the order of p/20 elements in each iteration, i.e. p^2/20 in total - with p ~ 30,000,000 we have to get all ~4.5*10^14 roundings correct.) > The probability of a given bit in the FP representation being in > error is bell shaped centred on the standard deviation of the > actual errors, and is not normal, but equally well defined. Hmm. Every bit is either 0 or 1 (irrespective of the data format!). This is a very discrete distribution which bears no relationship whatsoever to the bell curve. However this is a red herring. It's the (grossly nonlinear) combination of the 53 bits of the mantissa and the 11 bits of the exponent which is crucial to the argument. Regards Brian Beesley _______________________________________________ Prime mailing list [email protected] http://hogranch.com/mailman/listinfo/prime
