Finally getting back into programming after a long hiatus.
Here's a little project: a random-number display utility that lets you see how good a random-number generator is. It puts dots in a display window using a series of random numbers. So if you're looking at a certain RNG, you can see, to a first approximation, just how random it is.
The project uses the Lehman RNG function, something I found described on Micro$oft's "Learn" repository. It seems to be a pretty good generator, using a call to QueryPerformanceCounter() to seed the RNG. You can run it over and over and see what kinds of patterns you get. You can also adjust the "density" (the total number of dots).
Substitute your choice of RNG and see what kind of results you get.
Have fun with it.
Quote from: NoCforMe on August 07, 2024, 03:50:59 PMYou can run it over and over and see what kinds of patterns you get.
Seems that any sort of discernible patterns means that the 'randomness' is not very random. There is a similar function on the forum somewhere that used a similar approach (random pixel placement) to determine randomness. Some prng's showed definite repeating patterns, showing that the algo under test was not very random.
This is a different thread (works a bit different than yours) and seems to determine "randomness over time".
https://masm32.com/board/index.php?topic=1302.0 (https://masm32.com/board/index.php?topic=1302.0). You will see that certain random generators indeed show definite patterns. In that post, there are 4 prngs under test in their own executable test beds.
There was a similar thread to that one (that I cannot find) that I had the code for, at one time. Apparently I had errantly discarded that code during housekeeping, but the testbed in use in that linked thread is very similar in operation. Just another simple tool for testing randomness of prng's you can add to your toolbox.
Right. So technically it's a scatter plot.
When I run my program I do see instances of what look like clumping of dots, but it's hard to tell in any quantitative way how this actually affects randomness; you'd need to do some kind of numerical analysis to determine that.
Like I said, it's a rough-cut first-order test of randomness. Actually, to my eye, the Lehmer function looks pretty good. I'd be curious to see what kind of results others get if they substitute different RNGs. Maybe we should race them to see who's the most random ...
After further reflection: I'm not sure you can say that seeing "clumping" in the scatter plot is necessarily evidence of non-randomness. Think about it: let's say you have a random point plotted. What are the chances that any subsequent point isn't going to be right next to that point? I'd say it's as good as any other point on the plot. That's why unless there's really obvious visual evidence that the RNG isn't that random, the only way to really determine randomness is numerical analysis.
Quote from: zedd151 on August 08, 2024, 12:42:04 AMSeems that any sort of discernible patterns means that the 'randomness' is not very random.
So would you rather see this
(https://i.postimg.cc/YvBtF8wS/Notrandom.jpg) (https://postimg.cc/YvBtF8wS)
than this?
(https://i.postimg.cc/BXH0JD1f/random.jpg) (https://postimg.cc/BXH0JD1f)
No, of course not. The first one is a perfect distribution with no "clumping" or other artifacts, but it is 100% non-random.
Which raises a question: what exactly is the figure of merit that measures randomness in a set of numbers? and how is this figure calculated? Need to hear from some folks who actually know math here. (I did take, in another lifetime, a class in statistics where we learned about stuff like Poisson distributions and ANOVA and variance and all that, but it was long ago and I've forgotten ~98% of it. However, I still have my textbook; maybe I'll have a peek at it to see if I can answer my own question.)
I'm sorry I asked that question. It's a goddamn can of worms.
Apparently the measure of randomness is called "entropy", but not always, and not by everybody.
There are basic philosophical questions about what constitutes "randomness" to start with, let alone methods for measuring it.
I found a site (http://www.cacert.at/random/) that invites anyone to submit a file of supposedly random #s (12 MB minimum), but the idiots don't even tell you what size the numbers (binary) are supposed to be!
Yes it's a can of worms. :biggrin:
I have no clue how to calculate entropy properly. I have seen some mathematical formulas for doing so, but it's literally all Greek to me. :tongue:
As far as visual inspection of data, how big of a data set and what minimum/maximum values, there is also a question of periodicity. A small data set might seem random at first glance, but patterns may emerge much further out if a much larger data set is tested.
To me, if no discernible patterns are found during normal operation no matter how many times it is done - ought to be 'good enough' for most uses.
Consider shuffling a deck of 52 cards. Shuffle x amount of times, recording card order after each shuffle for instance.
Of course you will always have to start with a different seed each time. Some precanned prng's always start with the same seed, leading to predictability.
I have actually given up on testing various prng's against each other myself. The random generator in the Masm32 SDK works fine for everything I have used it for so far. But I always start with a different seed value.
Get the seed from the "high-performance" timer. Easy-peasy and gives a different seed each time:
.data?
QPCvalue LABEL DWORD
RandomSeed LABEL DWORD ;Same as low part of counter.
QPClow DD ?
QPChigh DD ?
;====================================================================
; LehmerRandInit()
;
; Sets up RNG for use by getting initial seed from hi-res timer.
;====================================================================
.code
LehmerRandInit PROC
; Seed the RNG from a time value:
INVOKE QueryPerformanceCounter, OFFSET QPCvalue
AND QPClow, 7FFFFFFFH ;Make sure seed doesn't overflow signed INT.
MOV LehmerInitFlag, TRUE
RET
LehmerRandInit ENDP
I found this tool (https://www.fourmilab.ch/random/) that gives some idea of how random a collection of byte values (in a file) is, along with a pretty good explanation of how it works.
Quote from: NoCforMe on August 09, 2024, 01:38:42 PMthis tool
Quote from: jj2007 on July 30, 2017, 06:50:11 PMThis code was assembled with ml64 in 64-bit format
It is ultrafast, and randomness is excellent, as tested with the Diehard and ENT suites.
Over 7 years ago ;-)
Quote from: jj2007 on August 09, 2024, 04:17:12 PMOver 7 years ago ;-)
So? Has it expired? exceeded its "sell by" date?
Quote from: jack on August 09, 2024, 11:34:26 PMQuote from: NoCforMe on August 09, 2024, 04:30:53 PMQuote from: jj2007 on August 09, 2024, 04:17:12 PMOver 7 years ago ;-)
So? Has it expired? exceeded its "sell by" date?
:rofl:
Quote from: NoCforMe on August 09, 2024, 01:38:42 PMI found this tool (https://www.fourmilab.ch/random/) that gives some idea of how random a collection of byte values (in a file) is, along with a pretty good explanation of how it works.
John Walker, January 28, 2008. :biggrin:
A little more than 7 years old. :tongue:
At first glance, it seems to be a very useful tool. Will take a more in-depth look at it later.
Quote from: zedd151 on August 08, 2024, 12:42:04 AMQuote from: NoCforMe on August 07, 2024, 03:50:59 PMYou can run it over and over and see what kinds of patterns you get.
Seems that any sort of discernible patterns means that the 'randomness' is not very random. There is a similar function on the forum somewhere that used a similar approach (random pixel placement) to determine randomness. Some prng's showed definite repeating patterns, showing that the algo under test was not very random.
This is a different thread (works a bit different than yours) and seems to determine "randomness over time".
https://masm32.com/board/index.php?topic=1302.0 (https://masm32.com/board/index.php?topic=1302.0). You will see that certain random generators indeed show definite patterns. In that post, there are 4 prngs under test in their own executable test beds.
The first computer generated texture aka Perlin noise, choose to use random generators with not very random and each shows definite patterns on purpose, uses 8 prng that is scaled 128,64,32,16,8,4,2,1 and adds together those and use cosine curve between to make it smooth.
My fast 128 bit low quality print is actually 4 x32 bit prng in parallel, using different seeds, pi, sqrt(2), natural exponent e.
Quote from: NoCforMe on August 09, 2024, 04:30:53 PMQuote from: jj2007 on August 09, 2024, 04:17:12 PMOver 7 years ago ;-)
So? Has it expired? exceeded its "sell by" date?
Certainly not. Use the forum search for
Diehard to find similar stuff.
Hi,
Quote from: zedd151 on August 09, 2024, 12:03:44 PMI have no clue how to calculate entropy properly. I have seen some mathematical formulas for doing so, but it's literally all Greek to me.
I have written some 16-bit code based on a formula
from a Wikipedia article. I could do a tutorial kind of
thing if that sounds useful? Rather simple stuff though.
Cheers,
Steve N.
How 'bout starting by just 'splaining it to us? How it works, without too many gory details.
When I made program for simt challenge with instead 128 bit SIMD prng, I also made .inc file with prime number lut for prime numbers between 0-65535
I downloaded ent and tried also test entropy on that prime numbers out and got highest entropy = uniqueness
That suggests that random shuffle prime numbers would become highest entropy prng but probably not useful if you want random numbers between 0-1000
What about the prng that's included in masm32 package ?
I used it in my unfinished labyrinth game for random generated treasure found in treasure chests, random amount of coin, the deeper level of labyrinth : level 1,2,3,4 = 1 ,2,,3,4 digits of coin and better quality of items found and more items
I use random numbemrs to point to strings size of 8 chars describes what kind of item you get + another string material its made of
For example sword, shield, armour, axe, ring, helmet + combined with wood, bronze, iron, steel, mythril , silver, gold, platinum = shows what quality item is
Message box pops up with all that info when you open treasure chest
I created a couple random # files with a tool I created and ran them through that utility I linked to above (which I renamed
randtest.exe). Here are the results:
1,000 random #s:Entropy = 7.840096 bits per byte.
Optimum compression would reduce the size
of this 1000 byte file by 1 percent.
Chi square distribution for 1000 samples is 213.95, and randomly
would exceed this value 97.10 percent of the times.
Arithmetic mean value of data bytes is 129.8050 (127.5 = random).
Monte Carlo value for Pi is 3.036144578 (error 3.36 percent).
Serial correlation coefficient is 0.051742 (totally uncorrelated = 0.0).
1,000,000 random #s:Entropy = 7.999793 bits per byte.
Optimum compression would reduce the size
of this 1000000 byte file by 0 percent.
Chi square distribution for 1000000 samples is 287.07, and randomly
would exceed this value 8.17 percent of the times.
Arithmetic mean value of data bytes is 127.4709 (127.5 = random).
Monte Carlo value for Pi is 3.143628575 (error 0.06 percent).
Serial correlation coefficient is -0.001882 (totally uncorrelated = 0.0).
I still don't really understand what all those numbers mean; perhaps someone here could explain that. I assume "entropy" is a rough measure of randomness, the closer it is to 8 (bits/byte), the better?
The larger file seems to do better than the smaller one.
I included my random-# generating tool,
RandFile.exe. Usage is
randfile n:<# of random #s> f:<name of file to write>
(don't include the angle brackets) It writes 1-byte numbers between 0-255 to the file, using the Lehmer function.
Entropy is good for testing if your own prng get better or worse result
Vcpp directive
#windowe lean and mean
Mean has to do with arithmetic mean or something else ?
Does it mean compromise among library include files ?
ITYM WIN32_LEAN_AND_MEAN.