topic Re: More on Random Number in Operating System - OpenVMS

More on Random Number

Jan van den Ende — Fri, 17 Jun 2005 08:15:33 GMT

Thread

http://forums1.itrc.hp.com/service/forums/questionanswer.do?threadId=910190

has been closed, but I like to add some more.

@Hein:

Watch out (sic) using just the clock, of system page faults, or such as a seed, as it may readily result in steady progression in the low order digits.

Care to explain?

If you read the procedure, the rand begins with the current centi-second reading of the system clock. I have always been convinced that those 100 different values have VERY equal probability of being picked.
Then the current seconds reading is taken, with only last digit used. For the same reasons as above, 10 equal chances.
Or do you happen to know of any relation between integer and fractional part of timestamp seconds reading?
A new call for hundredth gives 2 more digits.
Then "seconds integer last digit" (0 - 9) is used as deci-seconds to wait, before again getting hundredths. Please explain any tendency to drift away from pure randomness here!
Then those digits are string-concatenated.
Given a multiprocessing system, I do believe that the various invocations of f$cvtim will not be spaced predictable if measured in centiseconds.
If you REALLY are afraid that the clock time for processing the first and second determination of hundredths is too predictable, maybe giving predictable relations between the first and forth digit of rand, then do another 'random' decisecond wait (now derived from minute io second?) between those two.

Proost.

Have one on me.

jpe

Re: More on Random Number

Antoniov. — Fri, 17 Jun 2005 09:10:38 GMT

Jan,
your routine works fine if it's not executed repeatly and sequentially. In this case counters of hundredth increase in adjacent numbers.
You understand with attached example.

Antonio Vigliotti

Re: More on Random Number

Hein van den Heuvel — Fri, 17 Jun 2005 09:59:44 GMT

Jan, Thanks for re-opening this topic.
Allthough Niall was happy already. It seemed we were not quite done, but as long as. The old 'what problem are you trying to fix' huh?'

I wanted to thanks Karl for pointed out that nice article:
http://portal.acm.org/citation.cfm?id=63042

The biggest problem I have with a time sampling based algoritme are that they may be too random :-). You can not repeat the run and get the same 'random' numbers.

The algoritmic generator do repeat, and that may or might not be desirable. If not desirable, then use a proper seed.

The time based samplers then to produce patterns.
See attached example build on your suggestions.
The pattern over a (shortened) range appears to be:
'hot cold cold, hot cold cold, ...'

Very very minor comments:
Jan:

$ rand = " ' ' one' ' ' two ' ' ' three ' ' ' four ' "

That's an awful lot of quotes, easy to confuse.
For such construct why not use:
$ rand = one + two + three + four

Antiono:

Your loop needs two labels, two gotos.
I tend to use something like:

$ I=0
$LOOP1:
$ C'F$FAO("!2ZL",I)'=0
$ I=I+1
$ IF I.LT.100 THEN GOTO LOOP1
$show sym c*

versus the original:

$ I=0
$LOOP1:
$ IF I.GT.99 THEN GOTO XIT1
$ C'F$FAO("!2ZL",I)'=0
$ I=I+1
$ GOTO LOOP1
$XIT1:
$show sym c*

Cheers,
Hein

Re: More on Random Number

Jan van den Ende — Fri, 17 Jun 2005 12:06:39 GMT

Antonio,

Yes, on a FAST system, with not much load, if you run a tight loop (as you do) even the hundredths tend to come in sequence.
Note that I did
a. some intermediate processinf
b. a wait for some deciseonds
c. this is _supposed_ to not only generate lists of random number, but to USE them for something. (needed in a symbol, remember?).
This "something" will undoubtably help to enhance the spread over the hundredths.

Hein,
if you call the generated sequence "too random" then I absolutely wish to disagree on the definition of "random".

ANY repeatable sequence (of ANY inbuild complexity) that is repeatable ABSOLUTELY does NOT qualify as RANDOM!!
Unless your mathematics stems from another world than mine :-)

A sequence that is generated by a fixed calculation (and thus gives repeat results if starting from the same seed) is deterministic.
If such sequence forms a valid sample for the purpose, fine.
If repeatabily is wished for, here is a way to do it.
BUT IT IS __NOT__ RANDOM! It is deterministic.

On the recognisable pattern:
I do not know how much you sampled, but even the fact that you noted twice as much "hot" as "cold" is a direct indication that this pattern is NOT for real. Given enough samplings, it is easily demonstrable that for each digit the values 0, 1, .. 9 each rapidly approache 10%, and, even more significant, that the correlation of each value of a digit with each digit on any other position also rapidly approaches 10%.

-- if you are afraid of "clusters" of sub-patterns, then add the concept of the minute as well as the second for determining the wait period. Even combining those to build your sub-second wait is reasonable.

== In a real situation, after each invocation of rand "something: will be done with it. That will surely generate extra randomising of the exact timing.

-- on the syntax of concatenation:
You are right. Although any DCL programming tends to require this rather often, and I hardly notice anymore.
I was trying to force string concatenation and prevent numeric addition, but the values are already strings.

You are MUCH MORE right for another reason:
My syntax will leave out leading zeroes, so any hundredth from 00 to 09 will be shortened, effectively "moving those zeroes to the front position".
So, in about 3 * 10% of the samples RAND will be low by about a factor 10. :-(
Your construct does NOT have this defect.

Proost.

Have one on me.

jpe

Re: More on Random Number

Robert Gezelter — Fri, 17 Jun 2005 12:10:14 GMT

Jan,

WADR, random numbers are a subject with a complex history and an extensive literature. For casual use, the low order part of the clock can be used as a starting seed for a pseudorandom number generator (with provisions for rerunning the same sequence should the computation need reexecution in the future in exactly the same way).

Casual use (and I do mean VERY casual use) is totally different from any large computation or system. Serious use of random numbers requires careful thought and consideration. I recommend Knuth's Seminumerical Algorithms (Volume 2) in the Art of Computer Programming series, although it is a bit dated.

I hope that the above is helpful.

- Bob Gezelter, http://www.rlgsc.com

Re: More on Random Number

Hein van den Heuvel — Fri, 17 Jun 2005 15:31:15 GMT

fwiw... the pattern I suggested was an artifact of the range I happened to have used from an example.
The pattern was very strong:
The top 10 had 8 values divisible by 9
All top 20 values where divisible by 3
No value divisible by 6 under the top 20

This was from 400,000+ samples. The code waited for the first value to get 7500 hits. This was on a modest AS1000 and took 20+ minutes of CPU.

When I changed the value range to 100, they were all hit within a less than 5% range.
When the first value hit 7500, no value was hit less than 7200 times, most more that 7300.

But then I changed the range to 1000 and then a horendous pattern becomes obvious. Ranges of almost 9 were never hit. It drifts over the number space. In the sample algoritme the 'hundreds' digit will always be close to the 'units' digit. so if the 'randumb' number is xxNxM
then M is N or N+1 and effictively the algoritme will only select 10% of the available range. And that's just a first order effect. My pattern with range 56 may well have been a derived pattern from this driving pattern.
I now see that Antonio also spotted this. Good job Antonio!

Try it on your system with the script from my earlier reply and the range stepped up to 1000? (And the FAO param for printout grown a digit also)

Granted, if you actually do something between number generation, like a normal script would then is may well soften.

But I'll warn you already that if all you do is for example to put those numbers in a file (not unreasonable?) then the pattern will still be there.

I shows that if you are worried about true randomness then you can take nothing for granted. Trust but verify and all that!

Have a great weekend you all!
I'm ready for a beer myself.

Hein.

(ps... Jan... I never 'had one on you' last week when we had the chance did I? :-)

Re: More on Random Number

Jan van den Ende — Fri, 17 Jun 2005 15:53:40 GMT

Hein,

I will do some checking myself.
I hope you do not mind my "fakingL some processing duration.

PS.

Entirely your own fault!!

In those two weeks I have not exactly avoided the bar, and I am convinced there are those that can testify I _DID_ offer (and accept as well. Thanks again!).
Only prerequisite: You HAD to be there when I was.
(I am not too good in any throwing games, and throwing a beer at you while trying to guess where to aim has too low a cost/effect ratio).

Proost.

Have one on me.

jpe

Re: More on Random Number

Antoniov. — Sat, 18 Jun 2005 03:18:43 GMT

Jan,
just for precision, look carefully at your routine:

$ one = f$cvtime( "" ,, " hundredth " )
$ two = f$cvtime( "" ,, " second " )
$! need odd number of digits:
$ two = f$extract(1,1, " ' ' two ' " )
$ three = f$cvtime( "" ,, " hundredth " )
$ wait 0:0:0. ' two '
$ four = f$cvtime( "" ,, " hundredth " )
$
$ rand = "''one'''two'''three'''four'"

You call f$cvtime( "" ,, " hundredth " ) two time sequentially without time out therefore "one" and "three" have the same value or else the two value are adjacent.
Your idea is good but implementation is slight poor.

Antonio Vigliotti

Re: More on Random Number

Jan van den Ende — Sat, 18 Jun 2005 06:10:16 GMT

Antonio,
your are right, as I already noted in my answer to Hein:
Insert a tiny wait between "one" and "three" as well.

Remark: if this is going to be used for a huge amount of numbers (say 1 M + ), then those WAITs add up to a LONG time. In those cases, something else is needed.

It starts to be more complex, but I think the routine given by Kalle in
http://forums1.itrc.hp.com/service/forums/questionanswer.do?threadId=910190
would do well there. Although, for true randomness, I would still add a 'peek of the clock' as extra term in the calculation.

fwif,

Proost.
Have one on me.

jpe

Re: More on Random Number

John Gillings — Mon, 20 Jun 2005 00:40:51 GMT

If you're V7.3-2 or above, here's a one liner that might have adequate randomness

$ r=%X'F$EX(30,2,F$UN())''F$EX(26,2,F$UN())''F$EX(28,2,F$UN())'

r will be a decimal number in the range 0 through 16777215

If you want to get 7 digits more accurately, use:

$ r=%X'F$EX(30,2,F$UN())''F$EX(28,2,F$UN())''F$EX(26,2,F$UN())'*127/213

that gives range [0..10003315]

This is similar to using the clock.

Re: More on Random Number

Willem Grooters — Mon, 20 Jun 2005 05:59:52 GMT

As I understood there is, or will be, a good random number generator within VMS. At least, I know FORTRAN and PASCAL have a function returning a random number, based on a seed. It would be good idea to make it available in (E)DCL. So a sugestion to Guy:

$ seed=(some value)
$ rand = f$random (seed)

What about that.

Willem

Re: More on Random Number

Antoniov. — Mon, 20 Jun 2005 06:56:06 GMT

John,
it's very intersting for your alternate using of f$unique()!
Congratulations.

Antonio Vigliotti

Re: More on Random Number

Jan van den Ende — Mon, 20 Jun 2005 07:35:41 GMT

Willem,

my only objection to any SEEDed procedure I have seen until now:
Once the seed is given, the whole sequence is entirely deterministic, and so, absolutely _NOT_ random. Ok, the pattern may be erratic, but it _IS_ deterministic.

One ugly aspect thereoff: there are only so many discreet values of seed, and the next seed is derived from the previous. So, after "some" time, depending on the domain size, it, and therefor the whole sequence, will be completely repeated!

Proost.

Have one on me.

jpe

Re: More on Random Number

Bojan Nemec — Mon, 20 Jun 2005 08:30:46 GMT

John,

Could you explain on which basis f$unique works?

Bojan

Re: More on Random Number

John Gillings — Tue, 21 Jun 2005 01:32:58 GMT

Jan,

>my only objection to any SEEDed
>procedure I have seen until now:
>Once the seed is given, the whole
>sequence is entirely deterministic,
>and so, absolutely _NOT_ random. Ok,
>the pattern may be erratic, but it
>_IS_ deterministic.

By definition, anything you generate using a mathematical algorithm will be, at best, "pseudo random". That is, the sequence is deterministic, but it has many of the properties of truly random numbers. The more statistical tests you can perform that FAIL to determine any patterns, the better your generator.

For most purposes, repeatability of the sequence is a FEATURE, as it allows (say) a simulation run to be repeated exactly.

About the only way you will get REALLY random numbers out of any deterministic machine is to add some kind of truly random component. For example, a small sample of radioactive material and a geiger counter type sensor counting decays per unit time, or if time isn't critical, something like a lotto ball selector you see on TV.

>Could you explain on which basis
>f$unique works?

F$UNIQUE returns a 32 byte HEX string. It has two requirements:
1) the value must be unique across a cluster for "all time".
2) the value should be monotonic increasing

It's implemented very simply by calling the system service $CREATE_UID and formatting the result as a HEX string.

"$CREATE_UID

Generates a universally unique identifier (UID).
Description
Generates a identifier that is unique across all computer systems."

If you want the exact details, you'll have to hunt through the source code, but it's some kind of combination of node ID, current time and some bits to make sure it's not a duplicate.

In fact the numbers generated by my one liner are decidedly NOT random, they have some very definite patterns, especially if called in a tight loop, or a loop with a constant execution interval. You might be able to do better by concatenating single low order digits. The only advantage over the other suggestions in this thread is it's small and fast.

Re: More on Random Number

Robert Atkinson — Mon, 11 Jul 2005 08:38:34 GMT

Just for reference, ICALC (http://vms.process.com/scripts/fileserv/fileserv.com?ICALC) has a random number genertor built in :-

ran2(0) random in 0.0 to 1.0
rand(0) random in 0 to 2^31-1

IC> rand(0)
1079132159
IC>
rand(0)
275634591
IC>
rand(0)
846631423

Rob.

Re: More on Random Number

Lawrence Czlapinski — Mon, 11 Jul 2005 11:10:11 GMT

jpe:
$ONE=F$CVTIME("",,"hundredth")
$WRITE SYS$OUTPUT one ! or writing to a disk gives an unpredictable value 00-99 which would probably be close to random if the numbers are not needed quicker than an IO.

For an application that does not need numbers quickly, this would probably work.
In a simulation, the numbers used for the simulation should be recorded. I believe most simulations use psuedo-random numbers so that the results can be rerun.
Lawrence

Re: More on Random Number

Lawrence Czlapinski — Mon, 11 Jul 2005 17:09:12 GMT

jpe: As we've often said, the problem you're trying to solve affects the answer. In this case whether a particular method of random number generation is adequate for the intended task.
Lawrence