Prev: Call for Papers: International Conference on Chemical Engineering ICCE 2010
Next: The Final Anlysis.
From: Mok-Kong Shen on 18 Jun 2010 03:29
Martin Lauridsen wrote:
> On p. 385 of The art of Computer programming vol. 2 by Knuth, he
> states that the function f(x) = ax + c is not random enough for the
> purpose of Pollard's Rho method, referring back to Chapter 3. I can't
> seem to find where he states that in Chapter 3.
>
> Can anyone help me out here? Why is f(x) = ax + c not random enough?

I suppose he simply meant that the discussions on the linear
congruential method there don't result in clear indications of how
best to choose the values of a and c to obtain a good PRNG. He gave
also the notorious example RANDU.

I have on the other hand a related question: Knuth wrote there further
(quotes mean in different font):

The next-simplest case is quadratic, say f(x) = x^2 + 1. We don't
"know" that this function is sufficiently random, .......
In fact, f is probably slightly "better" than random.

On could in practice in all branches of sciences and engineering
barely get something that is perfect in the theoretical sense. So
a PRNG could at best be designed such that its output is fairly well
random, but how could one ever obtain one that is "better" than random?
There must be some linguistic issue here that is unfamiliar to me.

Thanks.

M. K. Shen



 | 
Pages: 1
Prev: Call for Papers: International Conference on Chemical Engineering ICCE 2010
Next: The Final Anlysis.