Determining the pattern behind vb's "random" number generator?

[fenris]

I know that random numbers generally generated by a computer are psuedo in nature. The other day I was reading an article that peaked my interest. Basically the article was discussing ways to predict the output of random number generators. My question is how would one go about predicting the output from visual basic's random number generator? I am familar with university level math and stats so don't hold back on the interesting links and comments. Ultimately I would like to be able to develop a method that ranks random number generators on how random or difficult they are to predict.


Any help or suggestions are appreciated
Troy Williams B.Eng.
fenris@hotmail.com

 

[Alt255]

Troy, one of the reasons random number generators generate "psuedo-random" numbers is that the numbers are discreet (the have definate upper and lower boundries). To acheive anything approaching "randomness", the generated number set would have to be continuous (the numbers could represent any value and the probability of any value occuring at any point in a distribution would be zero).

Comparing different random number generators using simple criteria would be fairly easy, assuming we were willing to deal with discrete sets of discrete numbers and ignore any requirements for continuous distributions. The test would ask each system to generate a large sample of numbers in a given range and then evalute the samples by measures of dispersion. Hypothetically, the most "random" generator would create a number set with the highest variance and "flattest" distribution.

This would only be a beginning. Measures of dispersion wouldn't reveal the "pattern" artifacts you might hope to discover. Having never been a wiz in the calculus arena, I can only speculate on a mathematical method to prove the absence of fixed patterns. But, given my improvisational approach to finding "an" answer under pressure, if an employer wanted to know which of two random generators was better (and needed an answer before the end of the work day), I would provide an answer... right, wrong or moot. And I would cheat using all my skill and cunning.

Here's where you can start laughing. For each system, I would generate a few dozen samples, each containing a large set of "random" numbers. I would "draw" curvilinear trend lines through each number set (I would cheat by using the moving average method) and then compare the samples, looking for patterns. With absolutely no knowledge of a way to compare multiple sets of complex curves, but with an unwavering assumption that my intuition is superior to raw caculating power, I would "eyeball" the trends and pick the set of curves that seemed to have the fewest similarities.

This method wouldn't work very well in your case. I assume that you are trying to evaluate random generation systems to provide a sort of index of "randomization efficiency". I suppose this could be accomplished with a great deal of time, sweat and patience... but, as I noted, I wouldn't have a clue how you could reduce the concept to a simple number.

Keywords for your Internet search: Chaos Theory

Good luck!

Alt255@Vorpalcom.Intranets.com​

 

[MichaelRed]

Going a tiny step along Alt's path. Using his 'Samples", do a LaPlaz transform of each set. Comparing the frequency domains should show the similarities.

My references re random numbers primarily cite two sources for the measure of randomness:


Knuth D.E., 1981, Seminumerical Algorithims, 2ed., vol. 2 of the art of Computer Programming Addison-Wesley.

Bratley, P., Fox, B.L., and Schrage, E.L. 1983 A guide to Simulation Springer-Verlag.

I only regretfully 'publish" these references, as they are obvious indications of my advancing age, however I have had occassion to use both and find them quite helpful when attempting to re-new my acquaintance with some of the arcane trivia from the world of computer math.

I do applaud your interest in the concept, but also have to admit that I have never seen anyone interested in this on an 'academic' basis. The discussions of the topic will quickly plunge into some deep math - and as I recall - essientially never get past the first two or three canned answers.

Best of luck.





MichaelRed
redmsp@erols.com

There is never time to do it right but there is always time to do it over

 

[fenris]

Thank you for your detailed responses. The reason that I wanted to know how well visual basics RNG stacked up to other programming languages is that I am going to revist (and hopefully improve) my undergraduate thesis in a few weeks. It solved two very non-trivial problems using genetic algorithms. Genetic algorithms require a good RNG. I wrote my genetic algorithms in VB with the assumption that it's RNG was as good as any other languages. To this day, I have yet to find any impartial information on RNG comparisons.

I guess the reason is that it is a rather esoteric subject and probably 80% of programmers never delve into it.

Michel, the idea of using La Place transforms is intriguing but do you not need to know what the formula for the curve is first, or can you just fit a polynomial to the curve and la place the approximation? I have two years worth of university level calculus under my belt and I have never done anything with it that would be this practical, so I am unsure of how to proceed.

Again, I appreciate your time and willingness to provide your input into such a challenging question.
Troy Williams B.Eng.
fenris@hotmail.com

 

[MichaelRed]

fenris,

O.K. then use a Fourier analysis to get the frequency domains.

From what I can see, the more or less general practice is the same in most commercial language implementations. My references strongly suggest that the 'linear congruential generators' are the "Rnd()" of choice, and that for all but the MOST demanding allpications, this is appropiate - as long as the coefficients/constants are selected (or derived) appropiatly.

I have (briefly) implemented the si,plest of these , and found that VB's "Rnd" does not behave exactly according to the 'rule' set forth in at least ONE of the references - although the variation permits a recurring sequence. The reference implementation in VB DOES - at least at first glance - apprar to be a 'good' random number generator. I will implement at least on additional one of the reference implementations and attempt to see if I can compare them - at least briefly ("just for "fun" on a rainy Saturday).


MichaelRed
redmsp@erols.com

There is never time to do it right but there is always time to do it over

 

[MichaelRed]

O.K. I do not have the resources to do a significant test of the various Rnd's. I A very simplistic test, it APPEARS that the vb intrinsic function goes through about 16.7e 6 itterations before repeating. Neither of the two I programmed appeared to repeat for over 28.1e 6. Unless, of course, I have screwed up the whole process again.

fenris,

I do not know how many random values you need for your thesis, but if even approaches the 16e 6, you should probably be looking for something better. Otherwise, I think - based on my results - that the 'native' VB thing is quite reasonable.


MichaelRed
redmsp@erols.com

There is never time to do it right but there is always time to do it over

 

[fenris]

Thank you for taking the time to help me out Michael, it is greatly appreciated. I hope to finish some of my investigations very shortly. If the results are significantly different from yours I will post them here....

Anyway, thanks again
Troy Williams B.Eng.
fenris@hotmail.com