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. The "random bit probe" algorithm is an example of a "coupon collector's problem": https://en.wikipedia.org/wiki/Coupon_collector%27s_problem 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!) -- Martin Dr Martin Ward STRL Principal Lecturer & Reader in Software Engineering [email protected] http://www.cse.dmu.ac.uk/~mward/ Erdos number: 4 G.K.Chesterton web site: http://www.cse.dmu.ac.uk/~mward/gkc/ Mirrors: http://www.gkc.org.uk and http://www.gkc.org.uk/gkc
