On 2017-05-18, at 04:57, Martin Ward wrote:
> On 2017-05-17, at 18:18, Robin Vowels wrote:
>>> Presuming that the table fits in main memory.
> >> On the first mainframes I used, 99,999 wouldn't have fit.
>> You don't need to store all the numbers.
>> One bit for each number was sufficient.
>
> If you have enough random access backing store
> (eg disk or drum storage) to hold the numbers
> then Fisher-Yates will require at most one disk seek
> (or drum seek) per number. Writing the output will
> require one I/O operation per number anyway:
> so any algorithm will be I/O bound.
>
Random access is a myth. Even a fixed-head drum has
rotational latency, though not seek latency. The IBM
650 had both hardware and software accommodations to
this uncomfortable fact:
http://www.drdobbs.com/the-ibm-650/184404809
I'd expect paged virtual memory to have a dramatic
WSS-dependent performance threshold.
Writing the output benefits greatly from QSAM buffering.
> The "random bit probe" algorithm is an example of
> a "coupon collector's problem":
>
> https://en.wikipedia.org/wiki/Coupon_collector%27s_problem
>
Thanks for enriching my vocabulary. In commercial coupon
promotions the entrepreneur introduces a deliberatg bias.
There's ample evidence of this on eBay.
> The expected number of trials (and therefore runtime)
> is n log n (plus smaller terms). This might still
> take too long on a mainframe of the era we are talking about,
> given that it took over two seconds on a modern PC.
>
> Also: if the random number generator does not have a long enough cycle,
> then the last bit might never be found by random probing!
> (On some early microcomputers the built in interpreted
> BASIC language had a random number generator which repeated
> after about 1,700 numbers!)
>
I wonder what's the cycle length of the hardware (millicode?)
PRNG of the z?
-- gil
