On 2017-05-18, at 08:07, Martin Ward wrote: > On 18/05/2017 11:57, Martin Ward wrote: >> >> 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: for those who worry about such things, the "worst case runtime" > is infinite :-) > In many practical applications the constant coefficient overwhelms the theoritical asymptotic behavior. And DFSORT designers took pains to accommodate real DASD characteristics.
Might "random bit probe" fail surprisingly early because of the "Birthday paradox"? It's disappoinging that the Rexx RANDOM() function does not accommodate the NUMERIC DIGITS setting. -- gil
