.. am I the only one who is beginning to feel that 'random quest' needs its own forum ? Sharuff
IBM Mainframe Assembler List <[email protected]> wrote on 18/05/2017 15:35:57: > From: Paul Gilmartin <[email protected]> > To: [email protected] > Date: 18/05/2017 15:36 > Subject: Re: random quest > Sent by: IBM Mainframe Assembler List <[email protected]> > > 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 > Unless stated otherwise above: IBM United Kingdom Limited - Registered in England and Wales with number 741598. Registered office: PO Box 41, North Harbour, Portsmouth, Hampshire PO6 3AU
