From: jason r tibbetts <tibbettj@...>
Date: 2005-07-16T05:27:30+09:00
Subject: Re: [QUIZ] Sampling (#39)

David Brady wrote:
> 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.  :-)

Ezra's output looks like what you're looking for, but it seems to have 
gone unnoticed in the wake of Cassio's post.

> ezra:~/Sites ez$ time ./sample.rb 5_000_000 1_000_000_000 >  big_sample.txt
> 
> real    0m43.838s
> user    0m35.820s
> sys     0m1.360s
> ezra:~/Sites ez$ ls -l big_sample.txt
> -rw-r--r--   1 ez  ez  49444445 Jul 15 10:46 big_sample.txt
> ezra:~/Sites ez$ head big_sample.txt
> 168
> 285
> 566
> 604
> 912
> 1183
> 1335
> 1473
> 1728
> 1919
> ezra:~/Sites ez$ tail big_sample.txt
> 999998155
> 999998313
> 999998484
> 999998680
> 999998825
> 999999151
> 999999330
> 999999465
> 999999621
> 999999877
> ezra:~/Sites ez$

I /really/ want to know how this is possible. Multi-processor solution?