Testing those Assembly 8bit Random Number Generators

[reidrac]

This example of code would make a nice alternative for producing 8bit numbers if you don't mind having it posted on the Wiki, I could probably just alter myA to Seed I guess?

I agree, this is a very nice example (being myA the seed). I've used a similar approach in my current project instead the more code-lengthy SDCC approach and it works great!

[Singaja]

This example of code would make a nice alternative for producing 8bit numbers if you don't mind having it posted on the Wiki, I could probably just alter myA to Seed I guess?

I will be delighted

[AMSDOS]

I will be delighted

Done 

[ronaldo]

I'm sorry to tell you that the functions you are creating are not so random as your tests say. You are ploting pixels with colors ranging from 0 to 15. Therefore, you are testing randomness for last 4 bits only, not for the full 8 bits. If you test the full 8-bits, results are different. I made a testing program using 2 different graphs: a color stream graph (similar to graphs you were using, but using 8 bits to plot instead of 4), and a 2D spare points plot (most useful to test randomness). Here is the code:

Code Select Expand


#include <cpctelera.h>

#define VMEM (u8*)0xC000

typedef u8(*TRandFunction)(void);
typedef void(*TDrawFunction)(TRandFunction);

///////////////////////////////////////////////////////////////////
/// Singaja's Random generator 1
u8 randgen() __naked {
   __asm
      ld a,r
      ld b,a
      ld a,(seed)
      xor b
      add a
      xor b
      ld  (seed),a
      ld  l, a
      ret
    seed: .db 0x55
   __endasm;
}

///////////////////////////////////////////////////////////////////
/// Singaja's Random generator 2
u8 randgen2() __naked {
   __asm
      ld a,r
      ld b,a
      ld a,(seed2)
      add b
      add b
      add b
      add a
      ld (seed2),a
      ld  l, a
      ret
    seed2: .db 0x55
   __endasm;
}

///////////////////////////////////////////////////////////////////
/// Initialization for CPCtelera's random generators
void initializeRandomGenerators() {
   cpct_setRandomSeedUniform_u8(0x55);
   cpct_setSeed_glfsr16(0x1120);
   cpct_setTaps_glfsr16(GLFSR16_TAPSET_0512);
}

///////////////////////////////////////////////////////////////////
/// CPCtelera's mixed random number generator
u8 mixedRandomGenerator() {
   return cpct_getRandomUniform_u8_f( cpct_getRandomu8_glfsr16() );
}

///////////////////////////////////////////////////////////////////
/// CPCtelera's wrapper for simple Random Uniform Generator
u8 getRandomUniform_u8() {
   return cpct_getRandomUniform_u8_f(0); 
}

///////////////////////////////////////////////////////////////////
/// Put a pixel in Mode 2
void putpixel_m2(u16 x, u8 y, u8 val) {
   u8* vram = cpct_getScreenPtr(VMEM, x >> 3, y + 8);
   u8  byte = *vram;
   u8  pen  = val << (7 - (x & 7));
   *vram = byte & (pen ^ 0xFF) | pen;
}

///////////////////////////////////////////////////////////////////
/// Fill up the screen with random bytes
void fillUpScreen_colors(TRandFunction randfunc) {
   u8* mem = (u8*) 0xC000;

   cpct_setVideoMode(0);
   cpct_clearScreen(0);
   while(mem < (u8*)0xFFFF) {
      *mem = randfunc();
      ++mem;
   } 
}

///////////////////////////////////////////////////////////////////
/// Fill up the screen with a 2D-pixel plot
void fillUpScreen_pixels(TRandFunction randfunc) {
   u16 i;
   u8 last_y = 0;

   cpct_setVideoMode(2);
   cpct_clearScreen(0);
   for(i=0; i < 32000; i++) {
      u8 y = randfunc();
      putpixel_m2(last_y, y>>1, 1);
      last_y = y;

      cpct_scanKeyboard();
      if (cpct_isAnyKeyPressed())
         break;
   } 
}

///////////////////////////////////////////////////////////////////
/// Main function for testing
void main(void) {
   TDrawFunction draw = fillUpScreen_colors;
   
   cpct_disableFirmware();
   cpct_setVideoMode(0);
   initializeRandomGenerators();

   // Loop forever
   while(1) { 
      cpct_scanKeyboard();
      if      (cpct_isKeyPressed(Key_1)) draw(randgen);
      else if (cpct_isKeyPressed(Key_2)) draw(randgen2);
      else if (cpct_isKeyPressed(Key_3)) draw(cpct_getRandomu8_glfsr16);
      else if (cpct_isKeyPressed(Key_4)) draw(getRandomUniform_u8);
      else if (cpct_isKeyPressed(Key_5)) draw(mixedRandomGenerator);
      else if (cpct_isKeyPressed(Key_C)) draw=fillUpScreen_colors;
      else if (cpct_isKeyPressed(Key_P)) draw=fillUpScreen_pixels;
   }
}

You can compile it with CPCtelera.

These are the results:
[attach=2]
[attach=3]

Algorithms used, from left to right:

   
• Singaja's XOR-based random generator
• Singaja's ADD-based random generator
• CPCtelera's implementation of Galois Linear-Feedback Shift Register
• CPCtelera's basic random uniform
• CPCtelera's mixed random generator

Attached you have the full CPCtelera project, including DSK and CDT. Keys are: 1-5 to test one of these algorithms, P for 2D point graph, C for Color Stream Graph.

[reidrac]

Coincidentally I need less than 4 bits (get a random block from 7 available).

Singaja's XOR-based random generator is just tiny, if I needed properly randomness I would use SDCC's code. rand is like crypto: it is a very bad idea to make your own, so... don't do it!

EDIT: also, Singaja's code depends on R, that may change more than in these tests depending on how you use the function. In my game there's some variability because user input, but I need from 7 to 16 random numbers in a row (with little R change between them). That might mean I need a slightly better generator

ANOTHER EDIT: I probably need to run my own tests for my use case, but looks like Singaja's code (or the variation I was using) can be useful if I want to provide different difficulty levels. Worst random numbers allow more repeated blocks in a row, which makes easier to "match 3".

Btw, slightly off-topic: why is cpctelera not using stdint.h? (u8 instead uint8_t, part of Standard C)

[AMSDOS]

I'm sorry to tell you that the functions you are creating are not so random as your tests say.

Well your more than welcome to submit your Random Number Generator onto the Wiki.

[ronaldo]

@AMSDOS, @reidrac: I may have explained myself bad. I'm not critizising @Singaja, nor anyone contributing with different ideas to this community. Even the most minimum of the ideas is always worthy. It wasn't my intention to bother anyone of you. Sorry about that.

What I'm telling you is that the method used for measuring randomness is not valid for 8-bit integers. It doesn't have anything to be with special cases. I'm just trying to highlight this part, as I think it is important for this conversation.  I think it is important to correctly measure randomness, to fairly compare different methods and have better understanding of them.

@Singaja's methods may be useful in many contexts. But the user has to be conscious of the properties of the algorithm in order to properly use it; The same argument is valid for any other method. @reidrac: If you are councious of the way it works and it is fine for you, that's nice. The point is not about you, it is about all of us having better understanding of the algorithms and their properties.

Off-topic: CPCtelera does not use stdint.h because it has been conceived independent and centred only on the CPC: It doesn't have to support different platforms (at least, right now). However, it's always up to the user: CPCtelera doesn't prevent the user from including stdint.h and using it. Anyway, if you want to discuss these matters, I think it's preferably to use CPCtelera's main thread.

[Singaja]

Oi m8s    I'm really happy ronaldo you did properly evaluate my 2 last approaches and keep an eye on not giving false confidence in what is generated. I didn't have proper time yet to grasp the idea of this plot with one color dots but it seems a really reliable measure of randomness. Anyway I'm glad your evaluation is consistent with mine measurements that the xor-variant is much better than the add-variant I made. Clearly it's not trivial, but I hope there's still room for improvement so I'll dive into it in the evening CET (I hope). Since my xor-variant seems to work mostly on 4 least significant bits (if I got that correct) throwing in some bit shifts might improve it.

[AMSDOS]

@AMSDOS, @reidrac: I may have explained myself bad. I'm not critizising @Singaja, nor anyone contributing with different ideas to this community. Even the most minimum of the ideas is always worthy. It wasn't my intention to bother anyone of you. Sorry about that.

Critizise? Wasn't suggesting you critizise on the Wiki, though any corrected errors or Random Number Generators that could be included on that page would be great.
You'll need to Register to be able to Edit I think, talk to @Gryzor if you need help.

[reidrac]

@reidrac: If you are councious of the way it works and it is fine for you, that's nice. The point is not about you, it is about all of us having better understanding of the algorithms and their properties.

I didn't think you were making a point about me  That's clear enough! I shared my use case because it might be useful, not as a counter-example of your evaluation.

Relevant: Dilbert Comic Strip on 2001-10-25 | Dilbert by Scott Adams

Off-topic: CPCtelera does not use stdint.h because it has been conceived independent and centred only on the CPC: It doesn't have to support different platforms (at least, right now). However, it's always up to the user: CPCtelera doesn't prevent the user from including stdint.h and using it. Anyway, if you want to discuss these matters, I think it's preferably to use CPCtelera's main thread.

It was just curiosity, thanks. I thought I could learn something specific about SDCC

[Singaja]

I found this one written by Joe Wingbermuehle here: http://wikiti.brandonw.net/index.php?title=Z80_Routines:Math:Random

Code Select Expand



;-----> Generate a random number
; ouput a=answer 0<=a<=255
; all registers are preserved except: af
random:
        push    hl
        push    de
        ld      hl,(randData)
        ld      a,r
        ld      d,a
        ld      e,(hl)
        add     hl,de
        add     a,l
        xor     h
        ld      (randData),hl
        pop     de
        pop     hl
        ret

Seems much better than the xor-one.

[ronaldo]

I've added it to the test.
As they say in their webpage, it's simple and fast, but randomness is worse than yours, as you'll easily see here:

[attachimg=1][attachimg=2]

Attached you'll find the updated CPCtelera project to test all algorithms.

EDIT: I made a mistake and wasn't correctly returning the genarated value. I've fixed it and randomness is far better than expected. It may be improved, but it is really good for such a small sized algorithm. However, as you see in the 2D-scatter plot, there are some clear square patterns. Depending on the use, that should be taken into account.
Attached file is now updated.

[Alcoholics Anonymous]

Oi m8s    I'm really happy ronaldo you did properly evaluate my 2 last approaches and keep an eye on not giving false confidence in what is generated. I didn't have proper time yet to grasp the idea of this plot with one color dots but it seems a really reliable measure of randomness. Anyway I'm glad your evaluation is consistent with mine measurements that the xor-variant is much better than the add-variant I made. Clearly it's not trivial, but I hope there's still room for improvement so I'll dive into it in the evening CET (I hope). Since my xor-variant seems to work mostly on 4 least significant bits (if I got that correct) throwing in some bit shifts might improve it.

Creating a high quality random number generator is not a trivial matter.  The proper test for checking quality is the diehard test for randomness, which runs a battery of statistical programs looking for correlations in the numbers generated.  You can grab a copy on the web if you're really interested in this.  Using the R register will tie the sequence to time between calls modulo 128 cycles and this itself can create patterns in the numbers generated.  But there can be such a thing as "good enough" and maybe that's the argument here.

SDCC provides an LCG-type random number generator copied out of the C standard.  It's ok but it's very expensive in computation involving a 32-bit multiply.  There are better alternatives:  the marsaglia xor generators and a very high quality cmwc generator both of which have already been implemented on the z80.  These are designed by the mathematical community and surprisingly have short and fast implementations on the z80.  They were mentioned already in another thread but here are some links again:

CMWC
http://z88dk.cvs.sourceforge.net/viewvc/z88dk/z88dk/libsrc/_DEVELOPMENT/stdlib/z80/random/asm_random_uniform_cmwc_8.asm?revision=1.2&content-type=text%2Fplain

Marsaglia XOR
http://z88dk.cvs.sourceforge.net/viewvc/z88dk/z88dk/libsrc/_DEVELOPMENT/stdlib/z80/random/asm_random_uniform_xor_32.asm?revision=1.2&content-type=text%2Fplain

[reidrac]

Relevant: TIFU by using Math.random() — Medium

[AMSDOS]

But there can be such a thing as "good enough" and maybe that's the argument here.

The argument here initially, was the 8bit random number generators posted on the Wiki, were coming back with lovely Patterns 

[Bryce]

All these screenshots keeps reminding me that I still have a old TV that I need to fix for someone!

Looks like analogue hardware is better at doing random than software

Bryce.

[ronaldo]

@Alcoholics Anonymous: Oh man! You've spoiled the fun . All the algorithms considered here won't pass a single Marsaglia test (diehard tests were created by him). These algorithms have difficulties to pass a simple congruential-sequence test (like 2D-scatter plots), so no need to consider more serius tests. However, I assume that algorithms here are to be used on simple games and similar applications, and they should be "just right" for those tasks. Of course, any serious application will have to consider diehard tests firsts.

However, one of the interesting things here is that really small and fast algorithms may give a "just right" random output for non-critical applications. Marsaglia's CMWC is wonderful and not very expensive, but these algorithms are smaller and cheaper, so they could be consireded for games.

Anyway, if someone wants to know results from Marsaglia test, they are easy to perform using R.

[Alcoholics Anonymous]

@Alcoholics Anonymous: Oh man! You've spoiled the fun . All the algorithms considered here won't pass a single Marsaglia test (diehard tests were created by him). These algorithms have difficulties to pass a simple congruential-sequence test (like 2D-scatter plots), so no need to consider more serius tests. However, I assume that algorithms here are to be used on simple games and similar applications, and they should be "just right" for those tasks. Of course, any serious application will have to consider diehard tests firsts.

Heh heh yeah sorry   The point is the proper generators are in fact very fast and very small.  When Patrik looked into this a few years ago I think we were all very surprised at how small and fast the z80 implementations turned out to be.  Up to that point the reason for settling on using R or sequences of bytes in the ROM to generate numbers was that games didn't need anything high quality whereas they did need something small and fast.  Now there is something high quality that also happens to be small and fast

The R generator that Singaja posted above is similar to what a lot of people have been using.  It is definitely fast and small -- 76 (z80) cycles not including register preservation and 15 bytes including seed.  Compare that to the high quality 8-bit CMWC:  146 cycles and 42 bytes.  The Marsaglia XOR comes to 165 cycles and 44 bytes.  There's not much between those in terms of speed and size but there is a huge difference in the quality of numbers generated.  If you do write a program that does nothing but generate random numbers, Singaja's version will be twice as fast but then the program will be generating streams of numbers that don't look very random anyway   OTH if you really need to save those 30 bytes well maybe Singaja's version makes sense if you can get away with using it.  And I'm not being facetious here -- desperately searching for a few bytes at the end of a project is quite a common problem.

The Marsaglia XOR generator gets a mention in the article reidrac posted; apparently if you multiply its output by a constant it can pass hard tests for randomness.

[Singaja]

I proudly present Joe Wingbermuehle's and my own "xor and xor" hybrid:

Code Select Expand



      ;-----> Generate a random number
      ; ouput a=answer 0<=a<=255
      ld      hl,(seed_ion)
      ld      a,r
      ld      d,a
      ld      e,a
      add     hl,de
      xor     l
      add     a
      xor     h
      ld      l,a
      ld      (seed_ion),hl
      ret
   seed_ion: .dw 0x0


[ronaldo]

@Alcoholics Anonymous: Yes, man. I completely agree with you. I've been myself reading Marsaglia's works and I'm definitely including several versions of his algorithms in CPCtelera. I'm also looking for some other small generators to include, to let the user select the one that best fits concrete project needs (Mainly some simple LCG, a G-LFSR and some R generator like Singaja's). I think most people will prefer "just right" random quality if they save some bytes and cycles. It is also interesting to consider combinations of them for some applications (like a R-generator with an initial entropy source for seeding CMWC, for instance).

In any case, thank you very much for your considerations and contribution to this discussion. I think we all have the opportunity to learn a lot in this matter .

[ronaldo]

@Singaja: Don't know exactly what happens, or where is the difference, but your last proposal shows a much different pattern on my tests:
(Note: This test is using 0x5555 as seed. Using 0x0000 as seed results are worse).
EDIT: Fixed typo in my code. It now works perfectly . Updated attached ZIP file.

Attached you'll find this latest implementation. I've also added some new characteristics to the tests:

   
• Now 2D scatter plots draw 65000 points instead of 32000.
• There is a nice progress bar down the plot that may be hidden (O = progress bar ON, F = progressbar OFF).

It is interesting that, as pointed out previously, with different intermediate code, R-based algorithms behave differently. Up to now, best behaving one is the first version of Ion algorithm. It turns out to improve its quality in this version of the code, when progress bar is drawn. The additional code affects the period of the sequence, that seems to traverse greater part of the space.
I have also run some diehard tests. As expected, none of these algoritms pass a single diehard test. Only G-LFSR does pass 2 out of 64 tests, which is not a big deal though. So, conclusion remains the same: for good randomness quality, other algorithms like CMWC should be considered.

[Singaja]

I'm using WinApe for testing and the result is reproducible. My modified Ion function is under 6.
Btw I noticed you have a typo in your code and in one place you're using seed and in the other seed2.

Seed 0 is fine.

[ronaldo]

You're right. I didn't change that value and it was using incorrect values. Now my test show similar results as yours. In fact, these results seem really better than Ion. Haven't passed diehard tests yet (it probably won't pass, like the others), but this result seems really useful for general needs in games. Nice work
[attachimg=1]

[Grim]

Be very, very careful with R-based RNG. Since R follows the number of opcodes executed, its "randomness" solely depends on the context it is used (no matter the amount of bit-shuffling applied to it). It gets somewhat better when the program often go through many different execution paths. But your tight test loop is actually the worst case usage scenario: R will very quickly follow an equally short pattern and the randomness won't be any better than in the Dilbert strip :)

As mentioned before, R is best used once, eg. to generate the seed of a proper PRNG. Finally, it should be noted that one of the best source of entropy, are human input events. Works especially well in games.

[TFM]

... Finally, it should be noted that one of the best source of entropy, are human input events. Works especially well in games.

Isn't is fascinating that the highest degree of order (biological life) can be the source of perfect chaos.