From: David Brady <ruby_talk@...>
Date: 2005-07-16T05:10:58+09:00
Subject: Re: [QUIZ] Sampling (#39)

Belorion wrote:

>I think Jim's point was that if your last digit is 462470382 then you
>don't have a random sample... which is specified as a criteria for the
>quiz.
>
"People who think about this topic almost invariably get into 
philosophical discussions about what the word "random" means.  In a 
sense, there is no such thing as a random number; for example, is 2 a 
random number?"
-- Donald Knuth, The Art of Computer Programming, Vol II (2nd Edition), 
page 2.

Knuth, in turn, quotes John Von Neumann, on the preceding page:
"Any one who considers arithmetical methods of producing random digits 
is, of course, in a state of sin."

Knuth goes on to quantify various properties of randomness; Cassio's 
method fails the very first one (uniform distribution).  But meh: Cassio 
has just steeped in the evil a little longer. :-)

I would be interested to see a uniform solution approach Cassio's solution.

This is a GREAT Quiz, by the way.  I've keyed in a standard, textbook 
solution to this problem and my runtime is 9.5 minutes for ONE TENTH of 
the sample (sampling 500K from 100M).  Assuming purely O(n), that's 1.6 
*hours* to run the full sample on my Athlon 2200.  So, I have a 
solution, and I could quit now.  But now I want to try my hand playing 
with the profiler.  :-)

-dB

-- 
David Brady
ruby-talk@shinybit.com
I'm having a really surreal day... OR AM I?