Since I have typed this from scratch too many times, here is the readme from my Chaos Game Test program.

This program is an application of the Chaos Game. A Chaos Game can be used as a mathematical tool for evaluating how chaotic a stream of data is. In this application of the game, it takes data from a Pseudo Random Number Generator (PRNG).

How It Works:/
Start with some vertices. For example, the points of a triangle or a square.
Starting from some postion, move halfway to a randomly selected point. Repeat this procedure many times.
If you certain parts of the image are more clear than others, this means that there is bias for certain sequences. For example, if the sequence of vertices jumped to for a triangle is {0,1,2,1,1,1,0,1,0,1,2,2,0,1...} it appears that every 0 is followed by a 1. This will cause a higher density of points lying in the region between vertices 0 and 1.
If certain parts of the image never get filled in (the parts that are supposed to be) then there are certain sequences that are avoided by the sequence.
If very specific clusters of points are formed, it is strong bias toward a very specific, small period sequence. For example, well defined lines traversing the shape indicate specific patterns repeated.
As a note, using a triangle will never get filled in. Instead, it makes a Sierpinski's Triangle. Larger degree polygons should be filled in.

How To Use This Program:/
Send chaos.8xp to your calculator.
Select Asm( from the Catalog menu ([2nd][0])
Find CHAOS in the [prgm] menu.
Run the program
Press [CLEAR] or [ON] to exit.

This program can only do a triangle and a square because those were the easiest shapes to code. I doubt I will add in the ability for custom shapes, but it is an idea that I have thought of, using list input for vertex coordinates.
To change the PRNG or shape used, open the source and in the first few lines you should see the variables 'rand', 'shape', and 'update' . 'shape' should be 3 or 4. There are 7 built in PRNGs to test:
rand = 0, rand = 1 are simple Linear Feedback Shift Registers (LFSRs) (credit: Iambian, Geekboy)
rand = 2 is an 8-bit Multiple Linear Congruential Generator (MLCG) (I made this)
rand = 3 is a 24-bit MLCG (I made this)
rand = 4 is the ION random routine
rand = 5, rand = 6 are the LCGs used in (3)

You can add your own, too, they just need to be named 'Random' and output in L.
The 'update' variable can be 1 or 256. 256 is advised against as it is slower and less efficient.
update = 256 will update the LCD every 256 pixels plotted. It uses the OS sysroutine and it is slow. I don't even know why I still have it here. It saves 1 byte, but at the cost of hundreds of thousands of t-states (10ths upon 10ths of seconds).
update = 1 will interleave LCD updating for every pixel drawn. This saves many, many t-states (about, 575 per iteration, over thousands of iterations adds up pretty quickly). Also, you get to see the game unfold live, not every 256 frames.

The code is designed for the Brass assembler, but it should be easily ported to use with other assemblers.

There are 3 included PRNGs that I am not the author of:
- The ION routine is easily accessible via the many ION-supporting shells. I only tweaked it to get rid of non-essential bytes (push/pop HL and DE) and to make output in L.
- The two LFSRs are from CaDan, and offered by Geekboy and Iambian. At the time of this writing, it is without a license and free to use, but if they do make a license for it, it will be one of the 'just remember to credit us' ones. That is just proper manners and courtesy. It is a very fast routine and they deserve that credit.
- The rest of the routines (rand = 2,3,5,6) are ones that I made. 2 is crappy, 5 is okay, 6 is good and fast and provides 8-bit results, 3 is excellent and provides up to 24 bits with a very large period. Feel free to use them. Credit would be nice, at least in the source code.

Final Analysis/
All of routines pass the 3-vertex test with rand0 and rand1 showing slight bias toward some patterns. This means they are all excellent if you perform mod_3 on the output to select between 3 actions. rand0 and rand1 are the fastest, smallest routines and an excellent choice.
rand0 and rand1 have strong bias for the 4-vertex test. They exhibit the same pattern with a very short periodicity. This means these are bad choices if strongly chaotic data is needed between 4 choices (and other powers of 2, unfortunately).
rand2 is weakly biased in the 4-vertex test. There are much better faster, smaller routines.
rand4 can show strong bias or be excellent. In general, for situations that use peripheral inputs from humans (using a keypad for example) or chaotic device (randomly sending data to the i/o port that grabs the main loop's attention when certain lines are high/low) will produce excellent results. This is due to its use of the R register.
rand5 has some weak bias (much better than rand2, though) for the 4-vertex test.
rand6 is great in the 4-vertex test (it fills in the square), it is fast, and has a period of 65521.
rand3 is excellent in the 4-vertex test, quickly filling in the square. It is the slowest routine, but comparable to the OS Random routine. It takes less than 1600 t-states making it over 100 times faster than the OS routine. It has a period of 4292870399.

All but rand4 (the ION routine) can be seeded. rand3 is probably the best for statistical use, rand6 and rand4 for many games, rand0 and rand1 are best where high speed is necessary, such as with CaDan (a 'bullet hell' game) or fire animation.

Hopefully this answers one of KermM's questions on how good the ionRandom routine is Smile (It is quite good, especially if there is user input.)
Thanks for finally answering this question, Xeda! I'm impressed that you took the time to come up with an answer to this long-standing question, and I'm also interested to see the statistical and speed performance of the several PRNGs you built yourself. As you point out, in practice iRandom works well in games, because most include in-game user input that serves to add chaos into the mix.

One small correction: rand4 (iRandom) can easily be seeded, and the memory location to use for the seed is well-defined in the code for Ion (and to my knowledge, kept the same in Ion-compatible shells.
Hmm when I say seeded, I mean that given a seed, it will always produce the same sequence. I feel as if there would be some trouble with that as the R register is used. In CaDan for example, Iambian and Geekboy wanted to be able to record battles. What they would have to do, then, is just record player keypresses and instead of saving every random number generated for bullets or enemy actions they just save the seed. On replay they seed the PRNG and the same sequence will be generated, cutting down on the record size.

EDIT: As for speed, the two MLCGs are less than 800 and 1600 t-states for the worst case, respectively (I forgot the exact timings). For the individual LCGs used to make up the 24-bit PRNG, I have not timed them, but they will be significantly faster than 1600 t-states. The 1600 t-state calculation includes the 2 LCGs, a 16x16->32 multiplication, and a 24-bit modulo operation.
EDIT:2 The speed of the last routine (the better of the two LCGs) is between 402 and 418 t-states. There are only two branches in the routine, the first adding a potential 6 t-states, the second adding a potential 10 t-states to the base 402 t-states.

The last one performs seed*251+43 mod 65521 -> seed, and you should use the lower byte.

EDIT3: Analyzing the ION routine, it takes 145+24b t-states, where B is the input range. If B were to be 16, for example, it would take 529 t-states, versus at most 429 (since [0,15] allows for an easy bit-mask on the output).
Xeda112358 wrote:
Hmm when I say seeded, I mean that given a seed, it will always produce the same sequence. I feel as if there would be some trouble with that as the R register is used. In CaDan for example, Iambian and Geekboy wanted to be able to record battles. What they would have to do, then, is just record player keypresses and instead of saving every random number generated for bullets or enemy actions they just save the seed. On replay they seed the PRNG and the same sequence will be generated, cutting down on the record size.
Maybe a little offtopic, but this is what Doom does with it's replay files. It has a 256 (I think) element array that is the "random numbers", and the seed is just which element in the array to start on. So when it starts a game, it picks an index and that's the start, so when recording/playing back a replay, it just needs to store the index.

Edit: This is also good for network play, because then the two machines just need to agree on the seed, and it's guaranteed to generate the same numbers (unless someone changes it Razz).
I am working on updating it to allow custom inputs for vertices. It Currently allows input as a real list in the form of {y1,x1,y2,x2,...} or a complex list where each component is {y1+ix1,y2+ix2,...}.

However, for quick testing it will probably be a lot easier to simply pass a number and have the program generate a regular polygon with the given number of vertices. So should I add this? The program is currently small-ish at 210 bytes plus the RNG to test.

Also, I was thinking of having it be able to take input in a string as "nn,filename" where nn is the number of vertices and filename is the variable that has a data stream to directly test.

I updated the file. It has changed to now allow manual entry of the vertices (through a list in Ans) or by passing a number and having the program generate the given number of vertices. I also tried to make it easy-ish to test other PRNGs.

Also, the 2-byte LFSR written by Iambian is actually really good. This new version of the program takes input in HL instead of L and it turns out I was supposed to be using the upper 8 bits of that before where I used the lower.

EDIT: Oops, screenshots:

I want to try the data streaming at some point, too.
Ooooh, beautiful screenshots! Thanks for sharing these updates with us, and congratulations for a well-written LFSR must go to Iambian as well. Glad to hear it was better than you thought once you got the arguments as he intended. Wink
Register to Join the Conversation
Have your own thoughts to add to this or any other topic? Want to ask a question, offer a suggestion, share your own programs and projects, upload a file to the file archives, get help with calculator and computer programming, or simply chat with like-minded coders and tech and calculator enthusiasts via the site-wide AJAX SAX widget? Registration for a free Cemetech account only takes a minute.

» Go to Registration page
Page 1 of 1
» All times are UTC - 5 Hours
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum