Re: random quest

[Martin Ward]

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
mar...@gkc.org.uk  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

Re: random quest

[Paul Gilmartin]

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

Re: random quest

[Martin Ward]

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 :-)

--
Martin

Dr Martin Ward STRL Principal Lecturer & Reader in Software Engineering
mar...@gkc.org.uk  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

Re: random quest

[Paul Gilmartin]

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

Re: random quest

[Sharuff Morsa3]

.. am I the only one who is beginning to feel that 'random quest' needs 
its own forum ? 
Sharuff 


IBM Mainframe Assembler List  wrote on 
18/05/2017 15:35:57:

> From: Paul Gilmartin <0014e0e4a59b-dmarc-requ...@listserv.uga.edu>
> To: ASSEMBLER-LIST@LISTSERV.UGA.EDU
> Date: 18/05/2017 15:36
> Subject: Re: random quest
> Sent by: IBM Mainframe Assembler List 
> 
> 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

Re: random quest

[Gary Weinhold]

It could easily be mistaken for a board game forum until you read the actual 
posts (or maybe even after).

Gary Weinhold
Senior Application Architect

DATAKINETICS | Data Performance & Optimization

Phone:  +1.613.523.5500 x216
Email:  weinh...@dkl.com

[http://www.dkl.com/wp-content/uploads/2015/07/dkl_logo.png]

Visit us online at www.DKL.com

[http://www.dkl.com/wp-content/uploads/2015/08/banner.png]

E-mail Notification: The information contained in this email and any 
attachments is confidential and may be subject to copyright or other 
intellectual property protection. If you are not the intended recipient, you 
are not authorized to use or disclose this information, and we request that you 
notify us by reply mail or telephone and delete the original message from your 
mail system.



__
On 2017-05-18 10:45, Sharuff Morsa3 wrote:

.. am I the only one who is beginning to feel that 'random quest' needs
its own forum ?
Sharuff

Re: random quest

[Richard Kuebbing]

At least the posts are mostly intelligible to one who does not have any degrees 
in mathematics.  I find the article (link below) to be mostly opaque because of 
math jargon: https://en.wikipedia.org/wiki/Randomness_tests

But then the few articles I published when I was a physicist are loaded 
w/physics jargon.

The only thing remotely interesting about the two special elections we just had 
/ are having in GA/USA is seeing the manipulation of language in sending 
messages.  It makes me nostalgic for SNA.  Each byte (aka token) having one 
meaning.

DrK

-Original Message-
From: IBM Mainframe Assembler List [mailto:ASSEMBLER-LIST@LISTSERV.UGA.EDU] On 
Behalf Of Gary Weinhold

It could easily be mistaken for a board game forum until you read the actual 
posts (or maybe even after).



- The information contained in this 
communication (including any attachments hereto) is confidential and is 
intended solely for the personal and confidential use of the individual or 
entity to whom it is addressed. The information may also constitute a legally 
privileged confidential communication. If the reader of this message is not the 
intended recipient or an agent responsible for delivering it to the intended 
recipient, you are hereby notified that you have received this communication in 
error and that any review, dissemination, copying, or unauthorized use of this 
information, or the taking of any action in reliance on the contents of this 
information is strictly prohibited. If you have received this communication in 
error, please notify us immediately by e-mail, and delete the original message. 
Thank you