News:

Masm32 SDK description, downloads and other helpful links
Message to All Guests
NB: Posting URL's See here: Posted URL Change

Main Menu

Random number visualization tool

Started by NoCforMe, August 07, 2024, 03:50:59 PM

Previous topic - Next topic

NoCforMe

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.
Assembly language programming should be fun. That's why I do it.

zedd151

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. 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.

NoCforMe

#2
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.
Assembly language programming should be fun. That's why I do it.

NoCforMe

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

than this?

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.)
Assembly language programming should be fun. That's why I do it.

NoCforMe

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 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!
Assembly language programming should be fun. That's why I do it.

zedd151

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.

NoCforMe

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
Assembly language programming should be fun. That's why I do it.

NoCforMe

I found this tool 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.
Assembly language programming should be fun. That's why I do it.

jj2007

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

NoCforMe

Assembly language programming should be fun. That's why I do it.


zedd151

Quote from: jack on August 09, 2024, 11:34:26 PM
Quote from: NoCforMe on August 09, 2024, 04:30:53 PM
Quote 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 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.

daydreamer

#12
Quote from: zedd151 on August 08, 2024, 12:42:04 AM
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. 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.
my none asm creations
https://masm32.com/board/index.php?topic=6937.msg74303#msg74303
I am an Invoker
"An Invoker is a mage who specializes in the manipulation of raw and elemental energies."
Like SIMD coding

jj2007

Quote from: NoCforMe on August 09, 2024, 04:30:53 PM
Quote 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.

FORTRANS

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.