16-bit/32-bit 65C816 random number generator

[gfoot]

After the discussion about a 24-bit PRNG in this thread I got motivated to do a better job of making a 16-bit random number generator than some other recent efforts which I won't share!

I had been looking back on this other thread where a number of generators were discussed, and I had been particularly impressed with the ones Arlet was posting as they were short and simple in structure but seemed to give good results. This evening I installed PractRand and had a go at making something based on Arlet's method, and I have ended up with this one which seems to do a very good job:

Code: Select all

        CLC
        LDA #$0081
        ADC state+0
        STA state+0
        ADC state+2
        STA state+2
        ADC state+4
        STA state+4
        ADC state+6
        STA state+6
        ADC state+8
        STA state+8
        ADC state+6
        ADC state+4
        STA state+6

This requires 10 bytes of state storage space and leaves a 16-bit result in the accumulator. I think in theory the period should be at least 2^48, and as I write this PractRand is still running - it has just completed 128GB of data and says at that point there was a "very suspicious" result. Prior to that there was just the occasional instance of an "unusual" test result (the lowest severity, I think).

So I think this RNG should be quite solid, at least for use cases that match the target platform! 128GB is way beyond the target I set myself at the start of the exercise. Given that it costs about 60 cycles to calculate the next 16-bit value, it would take a 20MHz computer over a day of continuous computation to get beyond 64GB of results.

The logic behind this structure - taken from what Arlet was doing in the other thread - is that the first few add/stores form a strict sequence that ensures those three words will cycle through every possible combination before repeating. On top of that two more words are used in a similar arrangement, but this time with feedback to shuffle up the results more - these form a kind of "output filter" on top of the underlying sequence. It's this bit that you basically experiment with to find combinations that do lead to good results.

I'm initialising the state vector to zero - I don't think the specific initial conditions will matter, so it should be fine to use any source you like to seed it.

I would highlight that I'm not an expert in this, I'm just following the patterns that Arlet established, and happy to see that it seems to lead to good results!

I will have a look at generating 32 bits as well - you could just pull one of the other state vector entries for the extra bits but they might not be random enough, so it's likely to work better if there are a few more stages of output filtering there, and at least one extra state vector. As Arlet noted, a big advantage to generating more at a time is efficiency - a few more adds can add a disproportionately large amount of extra random bits, reducing the overall cost per bit, and even if you don't need wider numbers out of it, you can use them to generate several narrower numbers at a time, so that you don't need to perform the main calculation as often.

[drogon]

gfoot wrote:

I will have a look at generating 32 bits as well - you could just pull one of the other state vector entries for the extra bits but they might not be random enough, so it's likely to work better if there are a few more stages of output filtering there, and at least one extra state vector. As Arlet noted, a big advantage to generating more at a time is efficiency - a few more adds can add a disproportionately large amount of extra random bits, reducing the overall cost per bit, and even if you don't need wider numbers out of it, you can use them to generate several narrower numbers at a time, so that you don't need to perform the main calculation as often.

Depending on how "good" you want, you might want to look at this:

Code: Select all

AND setseed (new) = VALOF
{
  LET old = ?

  IF state = 0 THEN
  {
    sawritef ("setting seed*n")
    state := getvec (3)
  }

  old := state!0

  state!0 := #xF1EA5EED
  state!1 := new
  state!2 := new
  state!3 := new
  FOR i = 0 TO 20 DO
    randno (1)

  RESULTIS old
}

AND rot (x,k) = (((x)<<(k))|((x)>>(32-(k))))

AND randno (upper) = VALOF
{
  LET e = ?

  e       := state!0 -   rot (state!1, 27)
  state!0 := state!1 XOR rot (state!2, 17)
  state!1 := state!2 +   state!3
  state!2 := state!3 +   e
  state!3 := e + state!0

  RESULTIS state!3 MOD upper + 1
}

Other than the final MOD operation there is no multiply or divides so it ought to work well as '816 native code.

It's from here: http://burtleburtle.net/bob/rand/smallprng.html

-Gordon

[gfoot]

Cool thanks, I'll try that and see how it fares too. The shift of 27 is slightly tricky of course, 3x more expensive than it looks. But I am also interested in similar algorithms for another processor that can do arbitrary bitshifts so it could easily come in handy there. (Edit - I see from the link:

Quote:

I used the shifts (27, 17). Others that achieve 8.8 bits of avalanche include (9,16), (9,24), (10,16), (10,24), (11,16), (11,24), (25,8), (25,16), (26,8), (26,16), (26,17), and (27,16).

So it might be possible to use 9,16, 9,24, or 25,8, which are cheaper to compute as it's only one single-step bitshift.)

Here is an extension of what I posted above, but with 32 bits of output. It uses a few more words of state, and is slightly longer (about 90 cycles I think). It has passed 128GB of PractRand testing so far without any warnings at all; it seems to be going at about 3.2GB/minute so it takes quite a while to test.

Code: Select all

        CLC
        LDA #0x0081
        ADC state+0
        STA state+0
        ADC state+2
        STA state+2
        ADC state+4
        STA state+4
        ADC state+6
        STA state+6

        ADC state+8
        STA state+8
        ADC state+10
        STA state+10
        ADC state+12
        STA state+12
        ADC state+4
        ADC state+8
        STA state+8
        ADC state+14
        STA state+14
        ADC state+6
        ADC state+10
        STA state+10

The result is taken from state+8 and state+10. I tried to get good results with less state but couldn't get above about 2GB until I added the eighth state word and tweaked things around.

[BigEd]

Interesting!

[dmsc]

Hi!

It is great that you are testing this properly!

gfoot wrote:

After the discussion about a 24-bit PRNG in this thread I got motivated to do a better job of making a 16-bit random number generator than some other recent efforts which I won't share!

I had been looking back on this other thread where a number of generators were discussed, and I had been particularly impressed with the ones Arlet was posting as they were short and simple in structure but seemed to give good results. This evening I installed PractRand and had a go at making something based on Arlet's method, and I have ended up with this one which seems to do a very good job:

Code: Select all

        CLC
        LDA #$0081
        ADC state+0
        STA state+0
        ADC state+2
        STA state+2
        ADC state+4
        STA state+4
        ADC state+6
        STA state+6
        ADC state+8
        STA state+8
        ADC state+6
        ADC state+4
        STA state+6

This requires 10 bytes of state storage space and leaves a 16-bit result in the accumulator. I think in theory the period should be at least 2^48, and as I write this PractRand is still running - it has just completed 128GB of data and says at that point there was a "very suspicious" result. Prior to that there was just the occasional instance of an "unusual" test result (the lowest severity, I think).

Yes, "unusual" is the lowest detection, the table is:

Code: Select all

 probability < 10^-999 : FAIL !!!!!!!!
 probability < 10^-325 : FAIL !!!!!!!
 probability < 10^-165 : FAIL !!!!!!
 probability < 10^- 85 : FAIL !!!!!
 probability < 10^- 45 : FAIL !!!!
 probability < 10^- 25 : FAIL !!!
 probability < 10^- 17 : FAIL !!
 probability < 10^- 12 : FAIL !
 probability < 10^-8.5 : FAIL
 probability < 10^-6.0 : VERY SUSPICIOUS
 probability < 10^-4.0 : very suspicious
 probability < 10^-3.0 : suspicious
 probability < 10^-2.0 : mildly suspicious
 probability < 10^-1.0 : unusual

So, "unusual" means that this result should happen less than once over ten runs - you can ignore the warning if it does not show it anymore as more data is tested. Tee "very suspicious" means less than onece in 10.000, so it is more important.

Quote:

So I think this RNG should be quite solid, at least for use cases that match the target platform! 128GB is way beyond the target I set myself at the start of the exercise. Given that it costs about 60 cycles to calculate the next 16-bit value, it would take a 20MHz computer over a day of continuous computation to get beyond 64GB of results.

The logic behind this structure - taken from what Arlet was doing in the other thread - is that the first few add/stores form a strict sequence that ensures those three words will cycle through every possible combination before repeating. On top of that two more words are used in a similar arrangement, but this time with feedback to shuffle up the results more - these form a kind of "output filter" on top of the underlying sequence. It's this bit that you basically experiment with to find combinations that do lead to good results.

I'm initialising the state vector to zero - I don't think the specific initial conditions will matter, so it should be fine to use any source you like to seed it.

IMHO, you should do a few tests with some random initial values just to confirm that the results are not too different.

Quote:

I would highlight that I'm not an expert in this, I'm just following the patterns that Arlet established, and happy to see that it seems to lead to good results!

Yes, the generators Arlet produced are really good for the simplicity. I'm baffled that so many people posts about LFSR generators as they were any good - thy are awful as PRNG, they use more memory, and are slower than other alternatives.

Have Fun!

[drogon]

dmsc wrote:

Quote:

I would highlight that I'm not an expert in this, I'm just following the patterns that Arlet established, and happy to see that it seems to lead to good results!

Yes, the generators Arlet produced are really good for the simplicity. I'm baffled that so many people posts about LFSR generators as they were any good - thy are awful as PRNG, they use more memory, and are slower than other alternatives.

Well, yes, ^^this^^

No-one is going to do any serious crypto today with the 6502/816 (maybe no-one should be doing...) So for out little systems and games, "good enough" is, well, good enough.

Back in the 32-bit world, one I've used for a very long time is:

Code: Select all

LET randno(upb) = VALOF  // Return a random number in the range 1 to upb
{
  randseed := randseed*2147001325 + 715136305
  // randseed cycles through all 2^32 possible values.
  RESULTIS (ABS(randseed/3)) MOD upb + 1
}

That is what Martin Richards uses in his BCPL implementation. Oddly, it's also what was given to me in the late 80s by someone who studied under him at Cambridge to use as a PRNG to use when I was writing memory test programs...

I implemented the one I posted earlier for no reason other than just because I could - in reality, even for the "big" 32-bit BCPL system it would never be used to its fullest potential.... At one point I was testing sorting routines in BCPL and got frustrated with the time it was taking to generate 100KB of random numbers to be sorted, so went back to the simple one as it was good enough for this purpose...

Coin flips is a very very crude test (also often in PRNGs the bottom bit just flips) but a few million runs (well, 32000 at a time with 16-bit loop counters!) give you more or less 50:50 ... So good enough for games. No-doubt people would reverse engineer it and work out winning seeds for whatever - which already happens for things like Minecraft and I'm sure others...

So quick and dirty FTW!

Quick & dirty test of the quick & dirty 16-bit Arlet one:

Code: Select all

>LIST                                                                                                                      
   10 REM Coin Flipping                                                                                                    
   20 PRINT "How many flips ";                                                                                             
   30 INPUT F                                                                                                              
   40 H = 0                                                                                                                
   50 FOR I = 1 TO F                                                                                                       
   60 IF RND % 2 = 0 THEN H = H + 1                                                                                        
   70 NEXT I                                                                                                               
   80 PRINT "Heads: ",H, " Tails: ", F-H                                                                                   
                                                                                                                           
>RUN                                                                                                                       
How many flips ?10000                                                                                                      
Heads: 4994 Tails: 5006                                                                                                    
                                                                                                                           
>RUN                                                                                                                       
How many flips ?10000                                                                                                      
Heads: 5008 Tails: 4992                                                                                                    
                                                                                                                           
>RUN                                                                                                                       
How many flips ?10000                                                                                                      
Heads: 4992 Tails: 5008

I'd suggest good enough for games but I'm sure someone could work out an "optimal" or even very sub-optimal seed if they cared...

-Gordon

[gfoot]

I thought it might be possible to reduce the amount of state space needed by using unaligned operations - I did manage to get the 16-bit version down to 8 bytes of state, with fewer instructions than before:

Code: Select all

        CLC
        LDA #0x0081
        ADC state+6
        STA state+6
        ADC state+4
        STA state+4

        ADC state+2
        STA state+2
        ADC state+3
        ADC state+0
        STA state+0
        ADC state+2
        STA state+2

Results were similar - despite this one only having 32 bits in the first stage, i.e. only guaranteeing a period of at least 2^32 samples - it actually lasts quite a bit longer than I expected:

Code: Select all

rng=RNG_stdin32, seed=unknown
length= 64 gigabytes (2^36 bytes), time= 618 seconds
  Test Name                         Raw       Processed     Evaluation
  DC6-9x1Bytes-1                    R= +10.3  p =  1.9e-4   mildly suspicious
  ...and 262 test result(s) without anomalies

rng=RNG_stdin32, seed=unknown
length= 128 gigabytes (2^37 bytes), time= 1233 seconds
  Test Name                         Raw       Processed     Evaluation
  DC6-9x1Bytes-1                    R= +20.9  p =  4.3e-8    VERY SUSPICIOUS
  ...and 272 test result(s) without anomalies

rng=RNG_stdin32, seed=unknown
length= 256 gigabytes (2^38 bytes), time= 2452 seconds
  Test Name                         Raw       Processed     Evaluation
  DC6-9x1Bytes-1                    R= +39.6  p =  1.4e-14    FAIL !
  ...and 283 test result(s) without anomalies

One other thing I experimented with a bit - it is really important that these operations are add-with-carry, not just plain adds. Clearing the carry before any of the adds invariably makes things worse. I thought it was interesting that that mattered so much. For the initial phase where we are ensuring a long cycle you can do the maths and see why it is important (it removes the guarantee of a long base cycle length), but for the shuffling stage I thought there would be more leeway.

[BigDumbDinosaur]

gfoot wrote:

Code: Select all

          LDA #0x0081

What’s the significance of $81 (expressed as 16 bits, I presume) as a starting value?  Suppose instead that that number came from some other source that produced quasi-random 16-bit values, e.g., a free-running hardware timer?  Would your algorithm continue to perform as it does using a fixed value?

Code: Select all

        CLC
        LDA #0x0081
        ADC state+6
        STA state+6
        ADC state+4
        STA state+4
        ADC state+2
        STA state+2
        ADC state+3   <——— ???
        ADC state+0
        STA state+0
        ADC state+2
        STA state+2

Is the operand of the arrowed instruction a typo or intentional?

[gfoot]

BigDumbDinosaur wrote:

What’s the significance of $81 (expressed as 16 bits, I presume) as a starting value?  Suppose instead that that number came from some other source that produced quasi-random 16-bit values, e.g., a free-running hardware timer?  Would your algorithm continue to perform as it does using a fixed value?

It needs to be a constant that's coprime with the register width (i.e. 16 bits, 65536) - so it needs to be odd at least. Arlet used $41 and $45 in his ones, I moved the top bit up a bit in case it helped since the overall calculation width here is wider - but I didn't check whether it was necessary. I kept it in the bottom 8 bits because I wanted the generator to work on another architecture that can't load 16-bit immediates. I have also tried $1081 and that didn't perform any better or worse than $0081. I also tried 1 and it passed tests up to 8GB but then failed a test at 16GB - so there are good and bad choices here.

It does have to be constant - this guarantees that the first couple of add statements, which are not affected by later feedback, cause at least a certain length of period in the output - state locations 4-7 will loop through all possible combinations of their values before repeating. Anything that upsets this has a big detrimental effect on the quality of the results.

You could try adding more noise to the second half of the algorithm though, as there the purpose is to take this non-repeating sequence and derive something more complex from it. Statements like the "ADC state+6", the extra "ADC state+2", and the "ADC state+3" in the example below are inserted experimentally to inject more entropy, but they often make things worse, it is a process of trial and error. It's hard to predict whether adding external randomness could similarly make things better or worse, you'd need to try it and see really.

Quote:

Code: Select all

        ADC state+3   <——— ???

Is the operand of the arrowed instruction a typo or intentional?

It's intentional - I realised that although these numbers are all calculated as 16-bit, there's no need to constrain myself to picking even offsets for these statements which are just there to add more entropy to the cascaded adds and stores, and in some cases odd numbers work better. It is quite fragile - with so little state space there is a delicate balance between over-reliance on the same piece of entropy, and using terms that don't have enough entropy. state+3 includes one byte that is guaranteed to have at least a specific long period (2^32) before its sequence repeats, and another byte that has high randomness (as it's one of the result bytes) and it seemed to work quite well.

Here is a 32-bit version with still only 8 bytes of state, and I think it costs 73 cycles overall. It passed tests up to 128GB and failed spectacularly at 256GB so I think the sequence probably started to repeat at that point. That means it's not as good as the 32-bit one I posted above, which passed 256GB, but this one is cheaper and requires less state space. The output is the bottom four bytes of the state vector.

Code: Select all

        CLC
        LDA #0x0081
        ADC state+6
        STA state+6
        ADC state+4
        STA state+4

        ADC state+2
        STA state+2
        ADC state+6
        ADC state+0
        STA state+0
        ADC state+2
        STA state+2
        ADC state+2
        ADC state+0
        STA state+0
        ADC state+3
        ADC state+2
        STA state+2

[BigDumbDinosaur]

gfoot wrote:

BigDumbDinosaur wrote:

What’s the significance of $81...as a starting value? ...

It needs to be a constant that's coprime with the register width (i.e. 16 bits, 65536) - so it needs to be odd at least...

¡Muy interesante! as they would say in Barcelona.

You mentioned you were setting the “state vector” to zero prior to the first pass through the routine.  I’m assuming you are referring to the state variables.  Assuming those locations haven’t been zeroed or otherwise accessed by any other code prior to the first call to your routine, they will have unpredictable quantities from initial system power-on in the case of a system with static RAM (dynamic RAM, on the other hand, tends to power up with a predictable pattern).  That would, in theory, add an element of randomness, as SRAM seems to contain different “garbage” with each power-on sequence, at least as observed in my POC units.  That, I would think, would result in a completely unpredictable result following the very first pass through your routine, as opposed to what would be produced if all state is zeroed.  Am I correct?

Quote:

You could try adding more noise to the second half of the algorithm though, as there the purpose is to take this non-repeating sequence and derive something more complex from it.

Is the “second half” the part of the code following the blank line?

BTW, my questions are emanating from never having done much with randomness in computing.  When I finally get around to writing the kernel for my 65C816 operating system, I want to include a PRNG call in the API that has a low level of predictability.  So I have been on the lookout for ways and means to do so.

[gfoot]

BigDumbDinosaur wrote:

You mentioned you were setting the “state vector” to zero prior to the first pass through the routine.  I’m assuming you are referring to the state variables.  Assuming those locations haven’t been zeroed or otherwise accessed by any other code prior to the first call to your routine, they will have unpredictable quantities from initial system power-on in the case of a system with static RAM (dynamic RAM, on the other hand, tends to power up with a predictable pattern).  That would, in theory, add an element of randomness, as SRAM seems to contain different “garbage” with each power-on sequence, at least as observed in my POC units.  That, I would think, would result in a completely unpredictable result following the very first pass through your routine, as opposed to what would be produced if all state is zeroed.  Am I correct?

Yes, I think "state vector" is the term used in cryptographic hashing algorithms, it seemed appropriate here too.

I am zeroing the state initially, but yes you could initialise it to anything - it's effectively a 64-bit seed. I don't think there are any theoretically bad values, though it's also fairly common to warm up a RNG by executing it a few times after seeding it, in case there's any residual effect from the seed in the first few values. Some RNGs have truly bad seed values that can act as "stationary points" where the state gets stuck, but the way these are constructed should prevent that.

Quote:

Quote:

You could try adding more noise to the second half of the algorithm though, as there the purpose is to take this non-repeating sequence and derive something more complex from it.

Is the “second half” the part of the code following the blank line?

Exactly - the bit before the blank line in each of these is a sequence of chained ADCs and STAs that forces the words involved to cycle through every possible combination of values before repeating, guaranteeing a certain minimum output sequence length - but the sequence itself is not very random, it is essentially a linear-congruential sequence and these have poor behaviour especially if you do things like only look at the low bits. The calculations after the blank line are there to scramble things up more (and they also increase the period further, but not in a way that you can easily prove). They are similar in general form, but with extra terms included sometimes (like adding in a value taken from earlier in the state vector) and feedback (e.g. overwriting state+2 a second time at the end, which creates a feedback loop a bit like in an LFSR generator).

Quote:

BTW, my questions are emanating from never having done much with randomness in computing.  When I finally get around to writing the kernel for my 65C816 operating system, I want to include a PRNG call in the API that has a low level of predictability.  So I have been on the lookout for ways and means to do so.

True entropy is certainly hard to find, we always hope our systems are deterministic! Some other sources could be the low bits of a VIA timer when user input is received, or a serial transfer completes, or a disk access completes - and if you have a few of these things you can add them all together to get the value you'll use as the seed. Or if you have a real-time clock, the current time value from that will ensure that every run is different.

As they stand I think these algorithms are not suitable for situations like cryptography where you don't want somebody who observes part of the sequence to be able to predict the rest - as the returned values are coming directly from the state. If somebody observed enough values in a row they may be able to piece together the exact values for all of the state entries, and then know exactly what is coming next. This is something that makes some algorithms unsuitable for use in cryptography for example, even if they are very suitable for things like statistical sampling.

Here's the C program I've been using to test these algorithms, in case you want to play with it - I just run it and pipe the output into PractRand's RNG_test program:

Code: Select all

#include <stdint.h>
#include <stdio.h>
#include <string.h>


int a;
int c;

uint8_t state[16];

#define CLC c = 0;
#define LDAi(imm) a = imm & 0xffff;
#define ADC(x) a = a + c + state[x] + (state[x+1] << 8); c = a > 0xffff; a &= 0xffff;
#define STA(x) state[x] = a; state[x+1] = a >> 8;
#define LDA(x) a = state[x] + (state[x+1] << 8);
#define EOR(x) a ^= state[x] + (state[x+1] << 8);


#define SIZE 128
uint16_t data[SIZE];

void generate()
{
    for (size_t i = 0; i < SIZE; i+=1)
    {
        CLC
        LDAi(0x0081)
        ADC(6)
        STA(6)
        ADC(4)
        STA(4)

        ADC(2)
        STA(2)
        ADC(3)
        ADC(0)
        STA(0)
        ADC(2)
        STA(2)

        data[i] = a;
    }
}


int main(int argc, char *argv[])
{
    memset(data, 0, sizeof data);
    memset(state, 0, sizeof state);

    do
    {
        generate();
        fwrite(data, sizeof data, 1, stdout);
    } while(1);

    return 0;
}

[BigDumbDinosaur]

gfoot wrote:

I am zeroing the state initially, but yes you could initialise it to anything - it's effectively a 64-bit seed...

Since I have a free-running, 16-bit hardware timer counting down from $FFFF to $0000 at the rate of ~57,000 times per second, it seems I could read the timer, write it to state+0, read the timer with a check that it has changed since the previous read, write to state+2, and repeat until state+6 is initialized.  I think a little more entropy could be introduced by inserting a WAI instruction between successive timer reads.

Quote:

As they stand I think these algorithms are not suitable for situations like cryptography...

...for which the 65C816 is not well-suited if performance really matters.  However, a reasonably good PRNG is useful for a lot of non-crypto applications, I’d think.

[gfoot]

BigDumbDinosaur wrote:

Since I have a free-running, 16-bit hardware timer counting down from $FFFF to $0000 at the rate of ~57,000 times per second, it seems I could read the timer, write it to state+0, read the timer with a check that it has changed since the previous read, write to state+2, and repeat until state+6 is initialized.  I think a little more entropy could be introduced by inserting a WAI instruction between successive timer reads.

That's one of those sequences where while it feels like you're adding entropy, in reality there might not be much. In particular the values you're writing to state+2,state+4,state+6 aren't contributing any additional entropy, because they're each just going to be one lower than the value you wrote to state+0.

So the sequence of random numbers you'd get would depend only on the counter's value at time of RNG initialisation, and depending what your system does before this point, that counter value could be rather consistent. On the other hand, if something like reading data from the serial port or disk is involved, those operations will add some variance to the time it takes your system to reach this point and hence the counter value, and that's good, the more of that sort of thing the better!

It would be even better if you had a faster counter available, e.g. T1 on a 6522 which counts down at the rate of the system clock. The low bits of this will be more sensitive to minor changes in elapsed time, amplifying any variance to span a wider range of seed values.

WAI itself is not inherently a source of entropy unless you have other hardware interrupts that fire at different moments each time you boot your system. If you do then absolutely, you can use this, but ultimately what you're depending on is the thing that generates the interrupt, and how variable its timing is, and that's really the crux of all of this.

I mentioned disks before because you are using SCSI - if they are physical disks then something like the time taken to seek from the lowest to the highest track, or the time taken to read a sector, may well have enough variance that with a high-resolution timer you'd get quite a range of different counter values out, and maybe you can also repeat these operations and reasonably expect to get different seek times each time, so it could be an easy way to get plenty of entropy. Then again, after reading a sector once, if you read the same sector again on a 7200RPM disk you'd probably just be waiting for one revolution, and the entropy you're reading is then just some variance in disk's rotation speed. If the drive's speed controller is very good, there might not be a great deal of variance there.

Whatever entropy you're able to find, if the range of likely values spans less than 16 bits I think it would be best to manipulate it a bit before writing it into the state, to ensure that the variant bits are having effects across the whole of the word. Something like x + (x<<4) + (x<<8) + (x<<12) perhaps. Then run the RNG maybe 16 times (discarding the results) to further propagate these bits around the whole state vector. These actions don't add any more entropy - the next value returned still depends exactly on whatever the input was - but they make that dependence less obvious, so that the next sample returned will have a good spread of values.

BigDumbDinosaur wrote:

Quote:

As they stand I think these algorithms are not suitable for situations like cryptography...

...for which the 65C816 is not well-suited if performance really matters.  However, a reasonably good PRNG is useful for a lot of non-crypto applications, I’d think.

Another case is something like a poker game, where you don't want somebody to be able to predict in advance what cards will be dealt. Or a guess-my-number game where the actual numbers coming from the RNG would be openly displayed to the user! I agree it doesn't matter much for the kinds of things we do with our systems, but these are the kinds of concerns that can apply.

[BigEd]

I think it might be better to XOR any extra source bytes, rather than to STO them, to mix in the new with the existing. Or ADC might be similar in effect.

[BigEd]

I do believe latency of spinning disks is a good source of entropy - it's affected by turbulence in the air layer. (Helium filled drives presumably just a little less good.)