Random-list generator code

[Yulquen74]

My next little project is to bring to life a code-snip that does the following:Given an input number X (max 16 bits large unsigned number), and the program should generate a list of numbers from 0 to X, in random sequence.The generator should put the numbers into a buffer as 16bit binary entries.The seed can be taken from scan line position or another hardware register which changes a lot. I would like suggestions / algorithms to how the random number generator itself could be designed, for maximum speed when generating a big list.I don't mind wasting lots of memory or using a large data table(s) instead of using costly instructions like mulu or divu to lower execution time. Target is MC68000.

[alkis]

That's shuffling, isn't it?

https://en.wikipedia.org/wiki/Fisher...3Yates_shuffle

[a/b]

Look up xorshift for a very fast and high quality 2^N rng. For arbitratry X:
Y= (smallest 2^N that's larger than X)-1;
rnd &= Y; if (rnd > X) rnd -= X;

If you need a not-high quality rng, this is what I use (also 2^N) when I need speed:

; d6=const modifer, d7=seed/rnd (both should be very large numbers, use all 32 bits)
  add.l d6,d7
  eor.l d6,d7
;  swap d7   ; highest speed, lowest accuracy (depends *heavily* on selection of modifier/seed), use rol instead if you need better accuracy
  rol.l #R,d7  ; pick R based on your speed/accuracy requirements (odds are better)
; rnd = extract lowest N bits from d7

Or do a search on EAB, there are older threads on this topic where you can find other people's quick&dirty alogrithms etc.

[Yulquen74]

Thanks both, will check it out.

[Thomas Richter]

Random number generators should not be picked at random. You find a good collection at Knuth "The Art of Programming, Volume 2: Numerical and Seminumerical Algorithms". Lots of things are known and are provable on the algorithms listed there, and I would recommend against picking some "hardware register" for it as its contents are all but random. You can use a date or so as random seed initializer. Is there a particular reason why this needs to be "so fast"? How often is it called, and how many random numbers do you need?For the random permutation problem, there is already an algorithm cited for Wikipedia that works on random exchange. It requires a random generator underneath. See the reference above for a good collection of well-studied algorithms.

[Thorham]

Originally Posted by Thomas Richter

Random number generators should not be picked at random.

Indeed.

Originally Posted by Thomas Richter

You find a good collection at Knuth "The Art of Programming, Volume 2: Numerical and Seminumerical Algorithms".

These are quite old. Current state of the art are Pcg and Xoshiro and some others.

Originally Posted by Thomas Richter

I would recommend against picking some "hardware register" for it as its contents are all but random

Indeed. Couldn't be worse if you tried.

Xoshiro128++: https://prng.di.unimi.it/xoshiro128plusplus.c

Alternatively, there's Xorshift: https://en.wikipedia.org/wiki/Xorshift

[Olaf Barthel]

Originally Posted by Thorham

Indeed.

These are quite old.

Yes, but they are also quite well-documented and well-tested. They won't let you down when it comes to randomness and sequence cycle lengths, but the integer arithmetics performed do not necessarily amount to well-spent CPU time.

Current state of the art are Pcg and Xoshiro and some others.

Xoshiro128++: https://prng.di.unimi.it/xoshiro128plusplus.c

Alternatively, there's Xorshift: https://en.wikipedia.org/wiki/Xorshift

Thank you for mentioning the Xorshift algorithms. In spite of how much functionality they deliver with very little code involved, they seem to be criminally overlooked. The Roadshow TCP/IP stack used to make use of Knuth's pseudo-random number generation algorithm for generating initial TCP sequence numbers, and this is still the case. I added an alternative algorithm based upon Xorshift in Roadshow 1.15. It can be enabled upon request.

[meynaf]

Originally Posted by Thomas Richter

I would recommend against picking some "hardware register" for it as its contents are all but random.

Some evolve relative fast with time and as such they are a good source of extra entropy. Just don't use them alone as they show obvious patterns.

Originally Posted by Olaf Barthel

Thank you for mentioning the Xorshift algorithms. In spite of how much functionality they deliver with very little code involved, they seem to be criminally overlooked. The Roadshow TCP/IP stack used to make use of Knuth's pseudo-random number generation algorithm for generating initial TCP sequence numbers, and this is still the case. I added an alternative algorithm based upon Xorshift in Roadshow 1.15. It can be enabled upon request.

Beware, as xorshifts are completely insecure. They fail linear complexity tests quite miserably. For normal Amiga programs it's not an issue but i would advise against using them in a TCP stack.

[a/b]

That's why there are variations of xorshift (*, +, shiro, ...). And that's why I said "look up" and not "use" ;P. Assess your speed vs. accuracy requirements and choose accordingly.
If speed is a lot more important, improvise (like I did above with a simplified xorshift).

[alkis]

Originally Posted by a/b

...
...
...
; rnd = extract lowest N bits from d7

This is tricky as well. OP said 0...X, where x is variable. I've seen many times that the lowest N bits are the "least" random. (I can easily admit that I don't know the behavior of xorshift on the matter though)

I think in the general form you can't avoid the division.

int r = xorshift32(&rng) / (RAND_MAX / x + 1);

something like that.

[Don_Adan]

Originally Posted by a/b

Look up xorshift for a very fast and high quality 2^N rng. For arbitratry X:
Y= (smallest 2^N that's larger than X)-1;
rnd &= Y; if (rnd > X) rnd -= X;

If you need a not-high quality rng, this is what I use (also 2^N) when I need speed:

; d6=const modifer, d7=seed/rnd (both should be very large numbers, use all 32 bits)
  add.l d6,d7
  eor.l d6,d7
;  swap d7   ; highest speed, lowest accuracy (depends *heavily* on selection of modifier/seed), use rol instead if you need better accuracy
  rol.l #R,d7  ; pick R based on your speed/accuracy requirements (odds are better)
; rnd = extract lowest N bits from d7

Or do a search on EAB, there are older threads on this topic where you can find other people's quick&dirty alogrithms etc.

Im not random routines expert, but why not use at end of random routine something like this:

add.l A0,D7
or
add.l (A0),D7
or
add.l (A0)+,D7

?

[meynaf]

Originally Posted by alkis

I've seen many times that the lowest N bits are the "least" random. (I can easily admit that I don't know the behavior of xorshift on the matter though)

This is a property of LCG, i don't think xorshift is affected.
However, another issue of xorshift is that it does not have good avalanche effect (i.e. a seed with few 1 will lead to a number with few 1).

Originally Posted by alkis

I think in the general form you can't avoid the division.

It is possible if you consider the result as a fixed-point number between 0 and 1, and simply multiply.

[a/b]

The idea was to avoid a very slow division (due to X != 2^N), so instead I'd use a bitwise and to extract a sufficient number of bits (so their value is now lower than 2*X), and then cap them to X with a simple compare/sub. I don't think that position of those bits matters, but yeah, you could ultimately extract from the top, or at 16+ (swap), etc.

[a/b]

Originally Posted by Don_Adan

Im not random routines expert, but why not use at end of random routine something like this:

add.l A0,D7
or
add.l (A0),D7
or
add.l (A0)+,D7

?

Not sure if I fully understand your question. General workflow is:
- d6 = modifier; d7 = seed;
- repeat: d7 = rol((d6+d7)^d6,R); rnd = d7&1023; // for example
- store d7 if you want to continue from the same rnd afterwards

There's no need for additional external data (add (a0)+?), modifier and seed should be chosen "carefully" (don't use small or simple numbers) and you can keep going for a long while.
Now if you're suggesting to use output address (a0?) as a modifier, the problem with that is if you are using non-absolute addresses, every time you start your code you will get a different series of random numbers. And we want pseudo-random, so you can easily repeat the series on demand by using the same seed.

[Don_Adan]

No, my idea is/was to add total unknown value to generated result.

[Thorham]

Originally Posted by Don_Adan

Im not random routines expert, but why not use at end of random routine something like this:

add.l A0,D7
or
add.l (A0),D7
or
add.l (A0)+,D7

?

This is a very bad idea. What if A0 points to a custom chip register? Or, what if A0 is uneven on a 68000?

[Thorham]

Originally Posted by meynaf

Beware, as xorshifts are completely insecure. They fail linear complexity tests quite miserably.

They're also easy to reverse.

[Don_Adan]

Originally Posted by Thorham

This is a very bad idea. What if A0 points to a custom chip register? Or, what if A0 is uneven on a 68000?

Then add.l A0,D7 must be enough.

[meynaf]

Originally Posted by Don_Adan

No, my idea is/was to add total unknown value to generated result.

This is similar to what i'm doing for my random number generator - use value in D1 coming from the OS at program startup (this is some dos handle).
I'm doing that at initial seeding step only, though. Else it may be constant during the program and not useful.

[paraj]

Is this just an academic exercise (which is fine of course!) or do you have an intended use case?
As is noted on previously linked Wikipedia page on Fisher-Yates shuffle, you actually need a very large internal RNG state even for very small N if you want to be able to generate all possible permutations. The example for a deck of cards (N=52) requiring > 225 bits of internal state is quite instructive.
Presumably this is not an issue, and you won't be using an A500 to host an online casino.

I ask, because having a concrete instance can usually bring forth interesting discussion / new ideas. For example the also mentioned xor-shift PRNG is based on LFSRs (https://en.wikipedia.org/wiki/Linear...shift_register), and for the case where N is some 2**M-1, and you just want some random looking permutation, a Galois LFSR can be extremely fast (~20 cycles/number). The "fizzlefade" screen in Wolfenstein is one such example (https://fabiensanglard.net/fizzlefade/).
Obviously not useful for say a card game, but for some usecases (like a demo) it might come in handy as you can easily calculate the next value without having to store a big array in memory.